XPost: comp.theory, sci.logic, sci.math
Showing how the Linz Ĥ can be correctly decided as non-halting
Revised Linz H halt deciding criteria (My criteria Ben's notation)
H.q0 wM w ⊢* H.qy iff UTM(wM, w) halts
H.q0 wM w ⊢* H.qn iff UTM(wM, w) does not halt
For simplicity we will refer to the copy of Linz H at Ĥ.qx embedded_H. embedded_H correctly determines that its input ⟨Ĥ⟩ ⟨Ĥ⟩ never halts.
Simplified syntax adapted from bottom of page 319:
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If embedded_H would never stop simulating its input ⟨Ĥ⟩ ⟨Ĥ⟩
this input would never reach a final state and stop running.
These steps would keep repeating:
Ĥ copies its input ⟨Ĥ⟩ to ⟨Ĥ⟩ then embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩...
computation that halts
...the Turing machine will halt whenever it enters a final state (Linz:1990:234)
That the pure simulation of an input would never reaches its final state conclusively proves that this input specifies a non-halting computation.
This proves that the input ⟨Ĥ⟩ ⟨Ĥ⟩ to embedded_H maps to Ĥ.qn
Peter Linz HP Proof
https://www.liarparadox.org/Peter_Linz_HP_315-320.pdf
--
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)