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)