XPost: comp.theory, sci.lang, sci.logic

On 9/19/2021 7:15 AM, Richard Damon wrote:

On 9/19/21 7:09 AM, olcott wrote:

On 9/19/2021 4:30 AM, Malcolm McLean wrote:

On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:

This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.

This would mean that my use of static local variables has no detrimental >>>> effect on the applicability of my partial halt decider to the halting
problem.

u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;

To qualify as a decider, the halt decider must calculate a
(mathematical) function.
That is, for each possible input, there must be one and only one
output, that
is always the same for each input.

How a piece of computer code achieves that is not important, and
details vary
from language to language. In some primitive languages (or high-level
scripting
languages) it may not be possible to declare local variables, for
instance.

That is great. If this truly is the case then this completes the essence
of my system.

This enables a decidability decider that refutes Rice's theorem:

u32 PSR_Olcott_2004(u32 P)
{
  return H1(P,P) != H(P,P);
}

int main()
{
  Output("Pathological Self-Reference(Olcott 2004) = ",
          PSR_Olcott_2004((u32) P));
}

And what is the Semantic Property of P that this is deciding?

As André aptly reminded me (that I said before)

On 9/9/2021 10:25 AM, olcott wrote:

It is the case that this inconsistency
defines a decidability decider that correctly
rejects P on the basis that P has the
pathological self-reference(Olcott 2004) error.

u32 PSR_Olcott_2004(u32 P) is a decidability decider.

What about my counter example of P = H2_Hat, which this seems to say
isn't Pathological but is the exact same 'code' (to use your term) as
H_Hat (Which you have called P) and H1_Hat?

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

u32 PSR_Olcott_2004(u32 P)
{
return H1(P,P) != H(P,P);
}

H1(P,P) correctly decides that its input halts because H1(P,P) does not
have the pathological self-reference error (Olcott 2004)
Whereas H(P,P) does have this error.

int main()
{
Output("Input_Halts = ", H1((u32)P, (u32)P));
}

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ halts, and

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt

H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly transitions to H.qy
Because H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does not have the pathological self-reference error (Olcott 2004)

Whereas Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does have this error.

H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
is a decidability decider rejecting ⟨Ĥ⟩ ⟨Ĥ⟩ as undecidable for Ĥ.qx

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)