• Concise refutation of halting problem proofs V41 [ persistent misconcep

    From olcott@21:1/5 to All on Thu Dec 16 09:44:35 2021
    XPost: comp.theory, sci.logic, sci.math

    *The nature of the misconception of the halting problem*

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
    if Ĥ applied to ⟨Ĥ⟩ halts, and

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
    if Ĥ applied to ⟨Ĥ⟩ does not halt<<<
    (Linz:1990:320) adapted with clearer notational conventions.

    [Linz 315-320](https://www.liarparadox.org/Peter_Linz_HP_315-320.pdf)

    We begin with the premise that the Linz H is a simulating halt decider.

    H has been embedded in Ĥ at state Ĥ.qx. The H.qy path has been disabled
    in Ĥ by appending an infinite loop.

    The H.qn path of the original H that is embedded at Ĥ.qx is be named
    [HALF OF COMPUTABLE FUNCTION H]:HOCFH

    Now we get to the misconception about the halting problem:
    Linz and everyone else believes that the condition of this Ĥ.qn path is
    if Ĥ applied to ⟨Ĥ⟩ does not halt<<< as if Ĥ was reporting on whether
    or not itself halts. This is incorrect.

    HOCFH does not transition to Ĥ.qn: >>>if Ĥ applied to <Ĥ> does not halt<<<

    HOCFH transitions to Ĥ.qn when its simulation of <Ĥ> applied to <Ĥ>
    never reaches the final state of <Ĥ> applied to <Ĥ>.

    The input to HOCFH is ⟨Ĥ⟩ ⟨Ĥ⟩.
    The input to HOCFH is not Ĥ ⟨Ĥ⟩.

    HOCFH does not compute whether or not >>>Ĥ applied to <Ĥ> does not
    halt<<< because an actual Turing machine cannot be input to any
    computable function.





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