• Concise refutation of halting problem proofs V21 [ precisely defined se

    From olcott@21:1/5 to All on Sat Nov 20 11:40:47 2021
    XPost: comp.theory, sci.logic, sci.math

    #include <stdint.h>
    #include <stdio.h>
    typedef int (*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; // Give P a last instruction at the "c" level
    }

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

    Computation that halts
    a computation is said to halt whenever it enters a final state.
    (Linz:1990:234)

    PSR set: Combinations of H/P having pathological self-reference
    For every possible H of H(P,P) invoked from main() where P(P) calls this
    same H(P,P) and H simulates or executes its input and aborts or does not
    abort its input P never reaches its last instruction.

    PSR subset: Because we know that the input to H(P,P) never halts for the
    whole PSR set and a subset of these H/P combinations aborts the
    execution or simulation of its input then we know that for this entire
    subset the input to H(P,P) never halts and H(P,P) halts.

    When int main(void) { P(P); } is invoked on H/P elements of the above
    PSR subset, then we have a cases where the input to H(P,P) never halts
    and P(P) halts.

    The above cases conclusively prove that when the input to H(P,P) never
    halts and the same P(P) does halt that this does not form any
    contradiction.

    Decidable_PSR subset: The subset of the PSR subset where H returns 0 on
    the basis that H correctly detects that P specifies infinite recursion
    defines the decidable domain of function H.

    H is a function that correctly maps every element of its domain to {0,1}
    on the basis of whether or not these elements reach their final state
    and halt. On this basis H is a halt decider.

    The above H could detect that its simulated P is calling H(P,P) with the
    same parameters that it was called with, thus specifying infinite
    recursion.


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