Concise refutation of halting problem proofs V5
From
olcott@21:1/5 to
All on Tue Nov 9 08:52:48 2021
XPost: comp.theory, sci.logic, sci.math
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]
Begin Local Halt Decider Simulation at Machine Address:c36
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
Because P calls H(P,P) P specifies infinitely nested simulation to every simulating halt decider H.
This has been verified with the execution trace of a correct pure
simulation of P.
Whether or not H aborts its simulation P never reaches its final state therefore the simulated P never halts.
If the simulated P never halts then H(P,P)==0 is always correct for
every simulating halt decider H.
To refute the claim that the direct execution of P(P) halts thus its
simulation is incorrect H(P,P) directly executes its input instead of simulating it. The result is the infinitely nested simulation becomes
infinite recursion.
In no case does the following directly executed P ever reach its final
state of c50.
// call void P(I);
int H(u32 P, u32 I)
{
if (!Halts(P,I)
return 0;
((void(*)(int))P)(I);
return 1;
}
int main()
{
H((u32)P, (u32)P);
}
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)