Re: It is known that a correct halt decider must return false (in this case)

[olcott]

On 11/20/2020 9:30 PM, Mike Terry wrote:
> On 21/11/2020 02:45, olcott wrote:
>> (1) It is known that the UTM simulation of a machine's Turing machine
>> description is equivalent to directly executing it.
>
> UTM simulation enumerates the steps of the TM calculation.
> So, yes, in that sense.
>
>>
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = Halts(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   Halts(P, P);
>>   HALT;
>> }
>>
>> (2) It is known that the above code is infinitely recursive if Halts()
>> acts like a UTM and simulates its input returning true if and only if
>> its input halts.
>
> Yes, we have infinite "recursive emulation".
>
>>
>> (3) On the basis of (1) and (2) It is known that a correct halt decider
>> must return false.
>
> There is no such thing as a "correct halt decider" for all inputs, but
> input (H_Hat,H_Hat) is non-halting, assuming your Halts() is as
> described.  This is all baby stuff.  [So the correct halting decision
> for the input is non-halting].
>
> [Just in case you're considering this - of course if you change your
> spec for Halts to make a new function Halts2, then that also changes the
> H_Hat machine to H_Hat2, and the *new* input (H_Hat2,H_Hat2) might be
> halting or non-halting, depending on the change.  This is also baby
> stuff...]
>
>
> Regards,
> Mike.
>

Machines of the pattern of H_Hat can be generally decided to be
infinitely recursive whenever they invoke the same function from the
same machine address and there are no intervening condition branch
instructions in-between that would break this cycle of infinite recursion:

// call to Halts from H_Hat
[00000503](05) e86ffeffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx

// call to Halts from H_Hat
[00000503](05) e86ffeffff call 00000377

All of the details of this analysis are shown here:

On Sunday, November 22, 2020 at 7:24:48 PM UTC-6, olcott wrote:
[It is known that a correct halt decider must return false (in this
case)[V4](Linz)]
https://groups.google.com/g/comp.theory/c/aiXoRwqxJgE/m/2GlNMjitAAAJ

--
Copyright 2020 Pete Olcott

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