No it does not as I prove right here:
Example 05: P(P) halts because H(P,P) correctly determines that its
input never halts
This conclusively proves that H(P,P) correctly simulates its input and
that the behavior of the correctly simulated P is very different than
the directly executed P(P).
The correctly simulated P cannot possibly terminate normally by reaching
its own "return" instruction. The executed P does terminate normally and
reaches its own "return" instruction.
If you are not an expert in the x86 language then you lack the basis to
determine that the input to H(P,P) is not simulated correctly. The
strongest claim that you can make is that on the basis that you do not
understand the x86 language you do not understand the proof.
typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider
void P(ptr x)
{
int Halt_Status = H(x, x);
if (Halt_Status)
HERE: goto HERE;
return;
}
int main()
{
P(P);
}
_P()
[0000143b](01) 55 push ebp
[0000143c](02) 8bec mov ebp,esp
[0000143e](01) 51 push ecx
[0000143f](03) 8b4508 mov eax,[ebp+08]
[00001442](01) 50 push eax
[00001443](03) 8b4d08 mov ecx,[ebp+08]
[00001446](01) 51 push ecx
[00001447](05) e8affcffff call 000010fb
[0000144c](03) 83c408 add esp,+08
[0000144f](03) 8945fc mov [ebp-04],eax
[00001452](04) 837dfc00 cmp dword [ebp-04],+00
[00001456](02) 7402 jz 0000145a
[00001458](02) ebfe jmp 00001458
[0000145a](02) 8be5 mov esp,ebp
[0000145c](01) 5d pop ebp
[0000145d](01) c3 ret
Size in bytes:(0035) [0000145d]
_main()
[0000146b](01) 55 push ebp
[0000146c](02) 8bec mov ebp,esp
[0000146e](05) 683b140000 push 0000143b
[00001473](05) e8c3ffffff call 0000143b
[00001478](03) 83c404 add esp,+04
[0000147b](02) 33c0 xor eax,eax
[0000147d](01) 5d pop ebp
[0000147e](01) c3 ret
Size in bytes:(0020) [0000147e]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[0000146b][00102428][00000000] 55 push ebp
[0000146c][00102428][00000000] 8bec mov ebp,esp
[0000146e][00102424][0000143b] 683b140000 push 0000143b // push P
[00001473][00102420][00001478] e8c3ffffff call 0000143b // call P
with argument on stack
[0000143b][0010241c][00102428] 55 push ebp // enter
executed P
[0000143c][0010241c][00102428] 8bec mov ebp,esp
[0000143e][00102418][00000000] 51 push ecx
[0000143f][00102418][00000000] 8b4508 mov eax,[ebp+08] // load eax
with argument to P
[00001442][00102414][0000143b] 50 push eax // push P
from eax
[00001443][00102414][0000143b] 8b4d08 mov ecx,[ebp+08] // load ecx
with argument to P
[00001446][00102410][0000143b] 51 push ecx // push P
from ecx
[00001447][0010240c][0000144c] e8affcffff call 000010fb // call
executed H with arguments on stack
H: Begin Simulation Execution Trace Stored at:1124d4
Address_of_H:10fb
[0000143b][001124c0][001124c4] 55 push ebp // enter
emulated P
[0000143c][001124c0][001124c4] 8bec mov ebp,esp
[0000143e][001124bc][00102490] 51 push ecx
[0000143f][001124bc][00102490] 8b4508 mov eax,[ebp+08] // load eax
with argument to P
[00001442][001124b8][0000143b] 50 push eax // push P
from eax
[00001443][001124b8][0000143b] 8b4d08 mov ecx,[ebp+08] // load ecx
with argument to P
[00001446][001124b4][0000143b] 51 push ecx // push P
from ecx
[00001447][001124b0][0000144c] e8affcffff call 000010fb // call
emulated H with arguments on stack
H: Infinitely Recursive Simulation Detected Simulation Stopped
When simulating halt decider H(P,P) simulates its input it can see that:
(1) Function H() is called from P().
(2) With the same arguments to H().
(3) With no instructions in P preceding its invocation of H(P,P) that
could escape repeated simulations.
The above shows that the simulated P cannot possibly (reachs its
“return” instruction and) terminate normally.
H(P,P) simulates its input then P calls H(P,P) to simulate itself again.
When H sees that this otherwise infinitely
nested simulation would never end it aborts its simulation of P and
rejects P as non-halting.
[0000144c][00102418][00000000] 83c408 add esp,+08 //
return to executed P
[0000144f][00102418][00000000] 8945fc mov [ebp-04],eax // load
Halt_Status with return value
[00001452][00102418][00000000] 837dfc00 cmp dword [ebp-04],+00 // if
Halt_Status == 0
[00001456][00102418][00000000] 7402 jz 0000145a // goto
0000145a
[0000145a][0010241c][00102428] 8be5 mov esp,ebp
[0000145c][00102420][00001478] 5d pop ebp
[0000145d][00102424][0000143b] c3 ret //
return from executed P to main
[00001478][00102428][00000000] 83c404 add esp,+04
[0000147b][00102428][00000000] 33c0 xor eax,eax // set
eax to 0
[0000147d][0010242c][00000018] 5d pop ebp
[0000147e][00102430][00000000] c3 ret //
return from main to operating system
Number of Instructions Executed(998) == 15 Pages
The correctly simulated input to H(P,P) calls H(P,P) in infinite
recursion thus H never returns to P and P never reaches its own "return"
statement. The directly executed P(P) calls H(P,P) *not* in infinite
recursion thus H(P,P) returns to P.