XPost: comp.theory, sci.logic
Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]
The x86utm operating system was created so that every detail of the conventional halting problem counter example could be fully specified in
C/x86.
In computability theory, the halting problem is the
problem of determining, from a description of an
arbitrary computer program and an input, whether the
program will finish running, or continue to run forever...
For any program f that might determine if programs halt,
a "pathological" program g, called with some input, can
pass its own source and its input to f and then specifically
do the opposite of what f predicts g will do. No f can exist
that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
This exact same relationship of f(g,g) was created as H(P,P), shown below.
This is the overview of the method for proving that this analysis is
correct:
(a) Verify that the execution trace of P by H is correct by comparing
this execution trace to the ax86 source-code of P.
(b) Verify that this execution trace shows that P is stuck in infinitely
nested simulation (a non-halting behavior).
This proof can only be understood only by those having sufficient
technical competence in:
(a) software engineering (recognizing infinite recursion in C and x86 code)
(b) the x86 programming language
(c) the C programming language and
(d) the details of how C is translated into x86 by the Microsoft C
compilers.
#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
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx
[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]
_main()
[00001372](01) 55 push ebp
[00001373](02) 8bec mov ebp,esp
[00001375](05) 6852130000 push 00001352 // push P
[0000137a](05) 6852130000 push 00001352 // push P
[0000137f](05) e81efeffff call 000011a2 // call H
[00001384](03) 83c408 add esp,+08
[00001387](01) 50 push eax
[00001388](05) 6823040000 push 00000423 // "Input_Halts = " [0000138d](05) e8e0f0ffff call 00000472 // call Output
[00001392](03) 83c408 add esp,+08
[00001395](02) 33c0 xor eax,eax
[00001397](01) 5d pop ebp
[00001398](01) c3 ret
Size in bytes:(0039) [00001398]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= ...[00001372][0010229e][00000000] 55 push ebp ...[00001373][0010229e][00000000] 8bec mov ebp,esp ...[00001375][0010229a][00001352] 6852130000 push 00001352 // push P ...[0000137a][00102296][00001352] 6852130000 push 00001352 // push P ...[0000137f][00102292][00001384] e81efeffff call 000011a2 // call H
Begin Local Halt Decider Simulation Execution Trace Stored at:212352 ...[00001352][0021233e][00212342] 55 push ebp // enter P ...[00001353][0021233e][00212342] 8bec mov ebp,esp ...[00001355][0021233e][00212342] 8b4508 mov eax,[ebp+08] ...[00001358][0021233a][00001352] 50 push eax // push P ...[00001359][0021233a][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][00212336][00001352] 51 push ecx // push P ...[0000135d][00212332][00001362] e840feffff call 000011a2 // call H ...[00001352][0025cd66][0025cd6a] 55 push ebp // enter P ...[00001353][0025cd66][0025cd6a] 8bec mov ebp,esp ...[00001355][0025cd66][0025cd6a] 8b4508 mov eax,[ebp+08] ...[00001358][0025cd62][00001352] 50 push eax // push P ...[00001359][0025cd62][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][0025cd5e][00001352] 51 push ecx // push P ...[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
H sees that P is calling the same function from the same machine address
with identical parameters, twice in sequence. This is the infinite
recursion (infinitely nested simulation) non-halting behavior pattern.
...[00001384][0010229e][00000000] 83c408 add esp,+08 ...[00001387][0010229a][00000000] 50 push eax ...[00001388][00102296][00000423] 6823040000 push 00000423 //
"Input_Halts = "
---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 // call Output Input_Halts = 0
...[00001392][0010229e][00000000] 83c408 add esp,+08 ...[00001395][0010229e][00000000] 33c0 xor eax,eax ...[00001397][001022a2][00100000] 5d pop ebp ...[00001398][001022a6][00000004] c3 ret
Number of Instructions Executed(15892) lines = 237 pages
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)