Philosophy Now Forum

Posted: **Sat Jun 04, 2022 11:14 pm**

The x86utm operating system was created so that every single detail of the halting problem could be completely examined at the high level of abstraction of C/x86.

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

It is clear that H0(Infinite_Loop) does correctly determine that its input would never halt.

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

The relationship between the C functions H and P shown below were defined to exactly match the above halting problem relationship.

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]

It is completely obvious that when H(P,P) correctly emulates its input that it must emulate the first seven instructions of P. Because the seventh instruction repeats this process we can know with complete certainty that the emulated P never reaches its final “ret” instruction, thus never halts.

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

Philosophy Now Forum

Can you see that halt decider H(P,P)==0 is correct?

Can you see that halt decider H(P,P)==0 is correct?