Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]

[olcott]

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