• Halting problem undecidability and infinitely nested simulation [ Simpl

    From olcott@21:1/5 to All on Mon Apr 18 19:54:37 2022
    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)