Re: Black box halt decider is NOT a partial decider [ Ĥ.qx(⟨Ĥ⟩,⟨Ĥ⟩) == Ĥ.qn ] [ succinct ]

[olcott]

On 8/1/2021 7:12 AM, Malcolm McLean wrote:
> On Sunday, 1 August 2021 at 11:54:57 UTC+1, Ben Bacarisse wrote:
>>
>> Here we can see that Ĥ applied to ⟨Ĥ⟩ halts. You can call your Ĥ's
>> behaviour "correct". You can call it anything you like. But it's not
>> "as in Linz". It does not say anything about Linz's proof. It does not
>> do anything people would call impossible or even interesting.
>>
> It seems to be established that H(H_Hat, H_Hat) returns "non-halting"
> whilst H_Hat(H_Hat) halts. So all is as Linz says it must be and no
> theorems are refuted. Which you would expect. If results were consistent
> it would have to be some cheap trick.

Since both answers are correct:

(a) The input to H(P,P) really is a non-halting computation:
It can't possibly ever reach its final state whether or not H aborts its
simulation.

(b) The P of int main(){ P(); } does reach its final state.

Therefore (b) does not prove that H(P,P)==0 is incorrect.

These are two different instances of P at two different points in the
execution trace and the first P would never halt unless the second P was
aborted thus proving that int main(){ P(); } does specify the first
element of an infinite chain of function calls. P was only allowed to
halt only because it was not an input to the halt decider. This is like
a guy that gets away with a crime only because no one is watching.

// H and H2 are partial halt deciders
u32 PSR_Decider(u32 P, u32 I)
{
u32 Input_Halts1 = H((u32)P, (u32)I);
u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)I);
Output("Input_Halts1 = ", Input_Halts1);
Output("Input_Halts2 = ", Input_Halts2);
if (Input_Halts1 != Input_Halts2)
return 1;
return 0;
}

Since u32 PSR_Decider(u32 P, u32 I) recognizes all and only these cases
Rice is refuted.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

> However the reasons PO's halt decider fails on H_Hat(H_Hat) have got
> nothing to do with the invert step of Linz' proof. This is maybe interesting,
> but in a small way, it's not a revolutionary result which will turn computer
> science upside down. But it's maybe worth mentioning.
>


--
Copyright 2021 Pete Olcott

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