• =?UTF-8?Q?What_final_state_does_simplified_Linz_=c4=a4_applied_to_?= =?

    From olcott@21:1/5 to All on Sat Dec 25 21:50:22 2021
    XPost: comp.theory, sci.logic, sci.math

    The following is the exact Linz Ĥ applied to its own Turing machine description except that the infinite loop appended to the Ĥ.qy path has
    been removed.

    Ḧq0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qy
    Ḧq0 ⟨Ḧ⟩ ⊢* Ḧ.qx ⟨Ḧ⟩ ⟨Ḧ⟩ ⊢* Ḧ.qn

    As the Linz text says a copy of the Linz H is at Ḧ.qx above.

    It is known that the UTM simulation of a Turing machine description is computationally equivalent to the direct execution of the same machine.
    This allows the copy of the Linz H to base its halt status decision on
    the behavior of the UTM simulation of its input.

    Ben's notational convention
    H.q0 wM w ⊢* H.qy // iff UTM(wM, w) halts
    H.q0 wM w ⊢* H.qn // iff UTM(wM, w) does not halt

    The copy of H at Ḧ.qx computes the mapping from ⟨Ḧ⟩ ⟨Ḧ⟩ to final states
    Ḧ.qy or Ḧ.qn on the basis of the behavior of the UTM simulation of these inputs.

    The embedded copy of H performs a UTM simulation of its input until:
    (a) Its input halts on its own, then it transitions to Ḧ.qy.

    (b) It determines that the UTM simulation of its input would never halt
    on its own, then it aborts its simulation and transitions to Ḧ.qn.

    https://www.liarparadox.org/Peter_Linz_HP_315-320.pdf
    Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)



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