XPost: comp.theory, sci.logic, sci.math

I show the details of constructing the "impossible" H

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 function named H continues to simulate its input using an x86
emulator until this input halts on its own or H detects that it will
never halt on its own. The technical computer science term "halt" means
that a program will reach its last instruction technically called its
final state. For P this would be its machine address [000009f0].

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
...[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.

Thus H(P,P)==false is necessarily correct, refuting the claim that:
No H can exist that handles this case.




--
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)