XPost: comp.theory, sci.logic, sci.math
Let ⟨M⟩ describe a Turing machine M = (Q, Σ, Γ, δ, q₀, □, F), and let w
be any element of Σ⁺, A solution of the halting problem is a Turing
machine H, which for any ⟨M⟩ and w, performs the computation (Linz 1990:317)
H.q₀ ⟨M⟩ w ⊢* H.qy iff UTM( ⟨M⟩, w ) reaches the final state of M
H.q₀ ⟨M⟩ w ⊢* H.qn iff UTM( ⟨M⟩, w ) would never reach the final
state of M
RHS is a paraphrase of Ben Bacarisse encoding of my halt status
criterion measure.
This halt status criteria correctly determines the halt status of inputs
with pathological self-reference (Olcott 2004). Simulating halt decider
H performs a pure simulation of its input as if it was a UTM unless and
until it detects an infinitely repeating pattern. Then it aborts the
simulation of its input and transitions to its final reject state.
The following simplifies the syntax for the definition of the Linz
Turing machine Ĥ, it is now a single machine with a single start state.
A copy of Linz H is embedded at Ĥ.qx.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
Ĥ ⟨Ĥ⟩ ⊢* Ĥ.qn on the basis that embedded_H detects that it must abort its simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ because UTM( ⟨Ĥ⟩ ⟨Ĥ⟩ ) at Ĥ.qx would never
reach ⟨Ĥ⟩.qn.
Halting problem undecidability and infinitely nested simulation (V3)
https://www.researchgate.net/publication/358009319_Halting_problem_undecidability_and_infinitely_nested_simulation_V3
--
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)