All of my reviewers expect H(P,P) to compute the halt status of P(P),
yet the behavior specified by the input to H(P,P) is not the same as the
behavior specified by P(P).
Anyone that is an expert in the C programming language, the x86
programming language, exactly how C translates into x86 and what an x86
processor emulator is can easily verify that the correctly simulated
input to H(P,P) by H specifies a non-halting sequence of configurations.
Since my reviewers expect the halt decider to compute the halt status of
P(P) yet the input to H(P,P) specifies a different halt status my
reviewers expect H to read their mind so that it can compute different
behavior than the behavior that the input actually specifies.
The function named H continues to simulate its input using an x86
emulator until this input either halts on its own or H detects that it
would never halt. If its input halts H returns 1. If H detects that its
input would never halt H returns 0.
#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()
[000009d6](01) 55 push ebp
[000009d7](02) 8bec mov ebp,esp
[000009d9](03) 8b4508 mov eax,[ebp+08]
[000009dc](01) 50 push eax // push P
[000009dd](03) 8b4d08 mov ecx,[ebp+08]
[000009e0](01) 51 push ecx // push P
[000009e1](05) e840feffff call 00000826 // call H
[000009e6](03) 83c408 add esp,+08
[000009e9](02) 85c0 test eax,eax
[000009eb](02) 7402 jz 000009ef
[000009ed](02) ebfe jmp 000009ed
[000009ef](01) 5d pop ebp
[000009f0](01) c3 ret // Final state
Size in bytes:(0027) [000009f0]
The simulated input to H(P,P) cannot possibly reach its own final state
of [000009f0] it keeps repeating [000009d6] to [000009e1] until aborted.
Begin Local Halt Decider Simulation
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
...[000009d6][00211368][0021136c] 55 push ebp // enter P
...[000009d7][00211368][0021136c] 8bec mov ebp,esp
...[000009d9][00211368][0021136c] 8b4508 mov eax,[ebp+08]
...[000009dc][00211364][000009d6] 50 push eax // Push P
...[000009dd][00211364][000009d6] 8b4d08 mov ecx,[ebp+08]
...[000009e0][00211360][000009d6] 51 push ecx // Push P
...[000009e1][0021135c][000009e6] e840feffff call 00000826 // Call H
...[000009d6][0025bd90][0025bd94] 55 push ebp // enter P
...[000009d7][0025bd90][0025bd94] 8bec mov ebp,esp
...[000009d9][0025bd90][0025bd94] 8b4508 mov eax,[ebp+08]
...[000009dc][0025bd8c][000009d6] 50 push eax // Push P
...[000009dd][0025bd8c][000009d6] 8b4d08 mov ecx,[ebp+08]
...[000009e0][0025bd88][000009d6] 51 push ecx // Push P
...[000009e1][0025bd84][000009e6] e840feffff call 00000826 // Call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
Because the correctly simulated input to H(P,P) cannot possibly reach
its own final state at [000009f0] it is necessarily correct for H to
reject this input as non-halting.
The correctly simulated 27 bytes of machine code at [000009d6] would
never reach its own final state at [000009f0] when correctly simulated
by the simulating halt decider (SHD) at machine address [00000826].
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer