How is H(P,P)==0 correct even though P(P) stops running?
(a) The reason that P of int main(){ P(P); } it is construed as halting
is that it reaches its final state.
(b) The reason that it reaches its final state is that H(P,P) returns zero.
(c) The reason that H(P,P) returns zero is that the correct pure
simulation of its input can't possibly reach its final state.
(d) When the pure simulation of an input can't possibly ever reach its
final state then this input never halts.
∴ The only reason that P of int main(){ P(P); } halts is because H(P,P)
correctly decided that its input never halts.
We can easily verify that the simulation of P(P) is correct by comparing
the execution trace of this simulation to the x86 source-code of P shown
below.
(c) is proved in that when P calls H and H acts as a pure simulator of
P(P) it is very obvious that P(P) is stuck in infinitely nested
simulation when we examine the execution trace of the simulation of P(P)
shown below:
// Strachey(1965) "An impossible program"
// CPL translated to C
//
https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
P((u32)P);
}
_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]
_main()
[00000c45](01) 55 push ebp
[00000c46](02) 8bec mov ebp,esp
[00000c48](05) 68250c0000 push 00000c25 // push P
[00000c4d](05) e8d3ffffff call 00000c25 // call P
[00000c52](03) 83c404 add esp,+04
[00000c55](02) 33c0 xor eax,eax
[00000c57](01) 5d pop ebp
[00000c58](01) c3 ret
Size in bytes:(0020) [00000c58]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00000c45][001016d6][00000000] 55 push ebp
[00000c46][001016d6][00000000] 8bec mov ebp,esp
[00000c48][001016d2][00000c25] 68250c0000 push 00000c25 // push P
[00000c4d][001016ce][00000c52] e8d3ffffff call 00000c25 // call P0
[00000c25][001016ca][001016d6] 55 push ebp // P0 begins
[00000c26][001016ca][001016d6] 8bec mov ebp,esp
[00000c28][001016ca][001016d6] 8b4508 mov eax,[ebp+08]
[00000c2b][001016c6][00000c25] 50 push eax // push P
[00000c2c][001016c6][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][001016c2][00000c25] 51 push ecx // push P
[00000c30][001016be][00000c35] e820fdffff call 00000955 // call H0
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P1 begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H1
[00000c25][0025c19e][0025c1a2] 55 push ebp // P2 begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
In the above computation (zero based addressing) H0 aborts P1.
[00000c35][001016ca][001016d6] 83c408 add esp,+08
[00000c38][001016ca][001016d6] 85c0 test eax,eax
[00000c3a][001016ca][001016d6] 7402 jz 00000c3e
[00000c3e][001016ce][00000c52] 5d pop ebp
[00000c3f][001016d2][00000c25] c3 ret
[00000c52][001016d6][00000000] 83c404 add esp,+04
[00000c55][001016d6][00000000] 33c0 xor eax,eax
[00000c57][001016da][00100000] 5d pop ebp
[00000c58][001016de][00000084] c3 ret
Number_of_User_Instructions(34)
Number of Instructions Executed(23729)
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein