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 <[email protected]> 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. The HHH that
aborts after one cycle, needs two cycles of simulation to reach this
end. That HHH is unable to reach this reachable end is an error in HHH,
which skips the most important part of the input. This is specified in
the input, but HHH is blind for this specification.
If you change the simulator to simulate one more cycle, but do not
change the input, so that it still aborts after one cycle, you will see
that the correct simulation will reach a natural end.
You confuse yourself by the way you constructed your simulation, so that
you miss the verifiable fact that when you change HHH, you are also
changing the input. But we should look at one input at a time and leave
it unchanged, when you change the simulators.

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