Code: Select all
void Infinite_Loop()
{
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H0(Infinite_Loop));
}
_Infinite_Loop()
[00001342](01) 55 push ebp
[00001343](02) 8bec mov ebp,esp
[00001345](02) ebfe jmp 00001345
[00001347](01) 5d pop ebp
[00001348](01) c3 ret
Size in bytes:(0007) [00001348]
Begin Local Halt Decider Simulation
[00001342][00212333][00212337] 55 push ebp
[00001343][00212333][00212337] 8bec mov ebp,esp
[00001345][00212333][00212337] ebfe jmp 00001345
[00001345][00212333][00212337] ebfe jmp 00001345
Local Halt Decider: Infinite Loop Detected Simulation Stopped
The relationship between the C functions H and P shown below were defined to exactly match the above halting problem relationship.For any program H that might determine if programs halt, a "pathological" program P,
called with some input, can pass its own source and its input to H and then specifically
do the opposite of what H predicts P will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
H determines the halt status of its input by watching the behavior of this input when it is correctly simulated by H using an x86 emulator. When H correctly matches an infinite behavior pattern it aborts the emulation of this input and returns 0.
Code: Select all
#include <stdint.h>
#define u32 uint32_t
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P
[0000135d](05) e840feffff call 000011a2 // call H
[00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]
The paper has been rewritten to make it more clear and has a new Appendix I
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publicatio ... ulation_V5