Re: Refutation of the Peter Linz Halting Problem proof 2024-03-05 --partial agreement--

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

On 06/03/2024 23:59, immibis wrote:

On 7/03/24 00:55, olcott wrote:

Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.Hqn
Correctly reports that Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ must abort its simulation.
>
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Correctly reports that H ⟨Ĥ⟩ ⟨Ĥ⟩ need not abort its simulation.

What are the exact steps which the exact same program with the exact same
input uses to get two different results?
I saw x86utm. In x86utm there is a mistake because Ĥ.H is not defined to
do exactly the same steps as H, which means you failed to do the Linz
procedure.

>
Not sure if we're discussing a general H here, or PO's H/Ĥ under his
x86utm.  (Ĥ is called D under x86utm.)
>
Under x86utm, Ĥ.H is implemented as a call to H from D, whilst H in
implemented as a call to H from main.  So we would expect stack addresses
to differ, but for that not to affect the computation.
>
In both cases, H:
-  simulates D(D) computation
-  spots PO's unsound "infinite recursion" pattern
-  announces it has encountered infinite recursion
-  returns 0  [non-halting]
>
So Ĥ.H does exactly the same steps as H, and reports the same result, as
required for Linz proof. And just as Linz proof proves, the result reported
by H is incorrect, since D(D) halts.  I have compared the instructions
executed by both H/Ĥ and THEY ARE EXACTLY THE SAME.  (In the region of 1000
or so machine instructions, including the handful of simulated
instructions.  Obviously stack addresses differ.  If required I could post
the output log but its quite long.]
>
So... in this case the exact same program is given the exact same input and
gets the exact same result as Linz logic requires, and the outcome is
exactly what Linz says.  There is really no mystery here that needs
explaining by faulty coding/cheating with simulations on PO's part.

Yes, this was the crystal clear case that led PO to answer:
| do you still assert that H(P,P) == false is the "correct" answer even
| though P(P) halts?
PO: Yes that is the correct answer even though P(P) halts.
I think your analysis of the traces was a key part of getting that clear
statement from him.

The HH/DD case is different, as that coding is completely broken by misuse
of global variables to divert the course of the code under the simulator.
But since EVEN WHEN THINGS WORK EXACTLY AS PO WANTS his results are in
AGREEMENT with Linz, it seems to me that arguing that his problem is
relating to cheating with the simulation is kind of missing the point.  Um,
not to say there's much point arguing with PO even if making perfectly
"on-point" arguments!  It all makes no difference to PO... :)

The irony here is that if one cheats it's possible to have H(D,D) (in
main, say) return 1 and yet have D(D) halt.  This can be done with D
constructed as usual.  It's only H that needs the cheat.  So to his
credit, he is not cheating, just totally at sea.
--
Ben.