My research seems to be the first time that anyone fully analyzed
applying a simulating halt decider (SHD) to the halting problem's
pathological inputs.
Prior to this no one was aware that when a halt decider correctly
simulates its input that the behavior of this simulated input could
possibly diverge from the behavior of the direct execution of this same
input. This only occurs when a pathological relationship exists between
a halt decider and its input.
When H(P,P) performs a correct x86 emulation of its input the behavior
of this emulated input is entirely different than the behavior of the
directly executed P(P). Until this is empirically validated by provably
correct execution traces this may seem to be impossible.
In fact all of my reviewers rejected the provably correct execution
traces in favor of their intuition. When we carefully examine the actual
facts (provided by the provably correct execution traces) we find that
this intuition is incorrect.
Since no one has ever fully examined applying a simulating halt decider
(SHD) to the Halting Problem's pathological inputs ever before no one
ever noticed that the behavior of a correctly simulated input would
diverge from the behavior of the directly executed input.
Because no one was previously aware of this divergence textbook authors
simply refer to the behavior of the directly executed input as the
criterion measure for a halt decider.
When we know that a halt decider must compute the mapping from its
inputs to an accept or reject state on the basis of the actual behavior
that is actually specified by these inputs then it becomes clear that
these textbook authors merely based their criterion measure on a false
assumption.
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
int main()
{
P(P);
}
_P()
[000012e7](01) 55 push ebp
[000012e8](02) 8bec mov ebp,esp
[000012ea](03) 8b4508 mov eax,[ebp+08]
[000012ed](01) 50 push eax
[000012ee](03) 8b4d08 mov ecx,[ebp+08]
[000012f1](01) 51 push ecx
[000012f2](05) e880feffff call 00001177 // call H
[000012f7](03) 83c408 add esp,+08
[000012fa](02) 85c0 test eax,eax
[000012fc](02) 7402 jz 00001300
[000012fe](02) ebfe jmp 000012fe
[00001300](01) 5d pop ebp
[00001301](01) c3 ret
Size in bytes:(0027) [00001301]
_main()
[00001307](01) 55 push ebp
[00001308](02) 8bec mov ebp,esp
[0000130a](05) 68e7120000 push 000012e7 // push P
[0000130f](05) e8d3ffffff call 000012e7 // call P
[00001314](03) 83c404 add esp,+04
[00001317](02) 33c0 xor eax,eax
[00001319](01) 5d pop ebp
[0000131a](01) c3 ret
Size in bytes:(0020) [0000131a]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001307][00102190][00000000] 55 push ebp
[00001308][00102190][00000000] 8bec mov ebp,esp
[0000130a][0010218c][000012e7] 68e7120000 push 000012e7 // push P
[0000130f][00102188][00001314] e8d3ffffff call 000012e7 // call P
[000012e7][00102184][00102190] 55 push ebp // enter executed P
[000012e8][00102184][00102190] 8bec mov ebp,esp
[000012ea][00102184][00102190] 8b4508 mov eax,[ebp+08]
[000012ed][00102180][000012e7] 50 push eax // push P
[000012ee][00102180][000012e7] 8b4d08 mov ecx,[ebp+08]
[000012f1][0010217c][000012e7] 51 push ecx // push P
[000012f2][00102178][000012f7] e880feffff call 00001177 // call H
Begin Local Halt Decider Simulation Execution Trace Stored at:212244
[000012e7][00212230][00212234] 55 push ebp // enter emulated P
[000012e8][00212230][00212234] 8bec mov ebp,esp
[000012ea][00212230][00212234] 8b4508 mov eax,[ebp+08]
[000012ed][0021222c][000012e7] 50 push eax // push P
[000012ee][0021222c][000012e7] 8b4d08 mov ecx,[ebp+08]
[000012f1][00212228][000012e7] 51 push ecx // push P
[000012f2][00212224][000012f7] e880feffff call 00001177 // call H
[000012e7][0025cc58][0025cc5c] 55 push ebp // enter emulated P
[000012e8][0025cc58][0025cc5c] 8bec mov ebp,esp
[000012ea][0025cc58][0025cc5c] 8b4508 mov eax,[ebp+08]
[000012ed][0025cc54][000012e7] 50 push eax // push P
[000012ee][0025cc54][000012e7] 8b4d08 mov ecx,[ebp+08]
[000012f1][0025cc50][000012e7] 51 push ecx // push P
[000012f2][0025cc4c][000012f7] e880feffff call 00001177 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
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 of P repeats this process we know with
complete certainty that the correct and complete emulation of P by H
would never reach the final “ret” instruction of P, thus never halt.
[000012f7][00102184][00102190] 83c408 add esp,+08
[000012fa][00102184][00102190] 85c0 test eax,eax
[000012fc][00102184][00102190] 7402 jz 00001300
[00001300][00102188][00001314] 5d pop ebp
[00001301][0010218c][000012e7] c3 ret // executed P halts
[00001314][00102190][00000000] 83c404 add esp,+04
[00001317][00102190][00000000] 33c0 xor eax,eax
[00001319][00102194][00100000] 5d pop ebp
[0000131a][00102198][00000000] c3 ret // main() halts
Number of Instructions Executed(15900) 237 pages
When P(P) is executed its behavior depends on the return value of H.
When H(P,P) is executed the correctly emulated P cannot possibly reach
the point where its behavior depends on H. This makes the behavior of
P(P) diverge from the behavior of the input to H(P,P).
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