• Concise refutation of halting problem proofs V16

    From olcott@21:1/5 to All on Wed Nov 17 09:24:46 2021
    XPost: comp.theory, sci.logic, sci.math

    #include <stdint.h>
    typedef void (*ptr)();

    int H(ptr x, ptr y)
    {
    x(y); // direct execution of P(P)
    return 1;
    }

    // Minimal essence of Linz(1990) Ĥ
    // and Strachey(1965) P
    int P(ptr x)
    {
    H(x, x);
    return 1;
    }

    int main(void)
    {
    H(P, P);
    }

    We can determine the behavior of the input to H(P,P) for an infinite set
    of different definitions of H by using categorically exhaustively
    complete reasoning. There are only four categories of possible
    definitions for H:

    (1) H(P,P) simply executes its input: main() calls H(P,P) that calls
    P(P) that calls H(P,P)...
    (2) H(P,P) simulates its input.
    (3) H(P,P) executes its input** and aborts this execution at some point.
    **(a debugger could be used).
    (4) H(P,P) simulates its input and aborts this simulation at some point.

    Case (1) (complete source code is provided above) shows that P never
    reaches its last instruction.
    Case (2) a correct simulation of the input to H(P,P) must have
    equivalent behavior to case (1).
    Case (3) and (4) any sub-sequence of (1) and (2) can't have instructions
    not included in (1) or (2).
    Thus for cases (1)(2)(3)(4) P never reaches its last instruction.

    For every H that
    simulates or
    executes its input and
    aborts or
    does not abort its input
    P never reaches its last instruction.

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