Re: Why does Olcott care about simulation, anyway? --- Mikes Review

On 6/2/2024 10:28 PM, Mike Terry wrote:

On 03/06/2024 01:16, immibis wrote:

The halting problem says you can't find a Turing machine that tells whether executing each other Turing machine will halt. Simulation has nothing to do with the question.

>
Background:
>
PO claims to have refuted the common HP proof, e.g. as covered in the Linz book "An Introduction to Formal Languages and Automata".  PO occasionally posts a link to a PDF containing an extract of the 5 or so pages of the book containing the proof, but I expect you have access to this or equivalent.
>
In a nutshell, the proof goes:
-  Suppose H is a TM Halt decider that decides for any input <P><I> whether
    TM P run with input I on its input tape halts.
    [<P> is the string representation of the actual TM P, and
     <I> is the string representation of input tape I]
-  Construct from H a new TM H^ using the mechanical process described in the proof.
    If H exists, then its corresponding H^ also exists.
-  Show that the construction of H^ ensures that:
    -  if H decides input <H^><H^> (representing H^ running with input <H^>) halts,
       then that implies that H^ running with input <H^> never halts
    -  if H decides input <H^><H^> never halts,
       then that implies H^ running with input <H^> halts
    I.e. either way, H decides the specific input <H^><H^> incorrectly, contradicting
    the initial assumption that H is a halt decider.
-  So no halt decider exists.  (Every proposed halt decider decides at least one input case
    incorrectly, viz input <H^><H^>.)
>
PO basically claimed he had a fully coded TM H, which CORRECTLY decides its "nemesis" input <H^><H^>, contradicting the logic of the Linz proof [without pointing out any actual mistake in the Linz proof].  Given most people here understand the Linz proof well enough to see it is basically sound, people were sceptical!
>
It turned out PO was lying about the fully coded TM, and in fact what he actually had was the idea behind a C program which would "prove" his idea.  A couple of years(?) later he actually completed his C program and his x86utm.exe which would simulate the x86 code of his H and H^ to "prove" his claim.  His equivalent of Linz H is his C function H or HH, and his equivalent of Linz H^ is his D or DD respectively.  (They run under x86utm.exe and are not Windows/Unix executables.)
>
H/HH use PARTIAL simulation of their input to decide halting/non-halting, returning
0 or 1 to communicate their decision.  As you correctly point out, to the HP proof simulation is quite irrelevant, being just one kind of data manipulation that H may perform on its input string <P><I> before it decides the halting status.  So the Linz HP proof covers such H, no problem.
[I put PARTIAL in caps, just because there seems to be some confusion in recent threads as to what PO means by "simulation".  He doesn't say it explicitly, despite suggestions to this effect, but he always means what might be called /partial/ simulation.]
>
PO believes that by (partially) simulating the computation corresponding to the input <P><I> [i.e. calculating the successive x86 instruction steps of the computation P(I)] and monitoring the progress of virtual x86 state changes (like instruction address and op-code and so on) H could spot some pattern that reveals whether computation P(I) halts or not.  At this point in the partial simulation, his H would stop simulating (aka "abort" the simulation) and return the appropriate halt status for input <P><I>.
>
Nothing remarkable so far!  Clearly a tight-loop in P /can/ be detected in this fashion, so /some/ <P><I> inputs /can/ be correctly determined like this.  The PO claim however is that the specific input <H^><H^> is correctly decided by his H.  In C terms those correspond to H(D,D) correctly returning the halt status of computation D(D).  [PO would probably dispute this, because he doesn't properly understand halting or the HP generally, or in fact pretty much /any abstract concept/ ]
>

 [ignored repost of already debunked nonsense]