Re: Mike's big mistake about DD simulated by HHH

On 5/16/2025 3:03 PM, Fred. Zwarts wrote:

Op 16.mei.2025 om 04:39 schreef olcott:

On 5/14/2025 7:36 PM, Mike Terry wrote:

On 14/05/2025 22:31, Keith Thompson wrote:

olcott <polcott333@gmail.com> writes:

>
I doubt that Sipser would be using your interpretation, relying on a false premise as a clever kind of logical loop-hole to basically fob someone off.
>
There is a natural (and correct) statement that Sipser is far more likely (I'd say) to have agreed to.
>
First you should understand the basic idea behind a "Simulating Halt Decider" (*SHD*) that /partially/ simulates its input, while observing each simulation step looking for certain halting/non- halting patterns in the simulation.  A simple (working) example here is an input which goes into a tight loop.  Going back to x86 world for this example, say the input (program to be decided) contains
>
   Input Code
   Address     Instruction
   ...
   00400000    push ebp
   00400001    mov ebp,esp
   00400003    sub esp,+24
   00400006    jmp 00400006    ; <===   jump to this instruction
   00400008    mov eax,[ebp+20]
   0040000b    mov ecx,[eax]
   ...
>
and during simulation, the SHD traces the computation steps, which reach the jmp instruction.  The observed simulated instruction trace might be something like:
>
   Inst.Ptr    Instruction
   00400000    push ebp
   00400001    mov ebp,esp
   00400003    sub esp,+24
   00400006    jmp 00400006       [A]
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   ...
>
Clearly the SHD, observing the above, already has enough information after seeing step [A] to conclude that its target is going into a tight loop, and is never going to halt.  It can stop simulating and correctly decide "non-halting".
>
That is a valid design for a (partial) halt decider, and it is how an SHD works.  Sipser would be aware of this sort of approach, though likely under some name other than "SHD".
>
Now when we look at PO's Sipser quote:
>
--------- Sipser quote -----
   If simulating halt decider H correctly simulates its input D until H
   correctly determines that its simulated D would never stop running
   unless aborted then H can abort its simulation of D and correctly
   report that D specifies a non-halting sequence of configurations.
----------------------------
>
we can easily interpret that as saying exactly what I said a SHD does above.  It tells PO that in the tight loop example, H correctly simulates as far as [A], at which point it correctly determines that "its simulated input would never stop running unless aborted", so it can decide "non-halting".
>
All correct and natural, and no deliberately false premises to mislead PO.
>

>
That is exactly correct.
I was very shocked that you could make the
mistake you made below. Your other analysis
of every other aspect of my work was brilliant.
>

PO's problem is his misinterpretation of "its simulated input would never stop running unless aborted".  In the case of his HHH/DD, the simulated input (DD) /does/ stop running if simulated far enough,

*I do trust that you are honest*
It did take me three days to see it is impossible
for HHH to simulate DD long enough so that DD halts.
>
The bottom line is that the directly executed HHH sees
one more execution trace than any nested emulation.
>
This means that unless this outer HHH aborts
then none of the do because they all have the exact
same code at the exact same machine address.
>

 You miss the fact that no change of input is allowed.

I have already fully addressed this too many times.
Look above and see how Mike corrects your error.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer