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 it “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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)