XPost: comp.theory, sci.logic, sci.math
Halting problem undecidability and infinitely nested simulation (V3)
Linz H is defined as simulating halt decider that bases its halt status decision on whether or not its correct simulation of its input could
ever reach the final state of this simulated input. H determines this on
the basis of matching infinite behavior patterns. When an infinite
behavior pattern is matched H aborts its simulation and transitions to
its final reject state. Otherwise H transitions to its accept state when
its simulation ends.
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
Can the correct simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H possibly transition
to ⟨Ĥ⟩.qn ?
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Then these steps would keep repeating:
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩
Ĥ3 copies its input ⟨Ĥ4⟩ to ⟨Ĥ5⟩ then embedded_H simulates ⟨Ĥ4⟩ ⟨Ĥ5⟩...
The above shows that the correctly simulated (as if Ĥ.qx was a UTM)
input to embedded_H would never reach its final state of ⟨Ĥ⟩.qn conclusively proving that this simulated input never halts. This enables embedded_H to abort its simulation and correctly transition to Ĥ.qn.
Because all simulating halt deciders are deciders they are only
accountable for computing the mapping from their input finite strings to
an accept or reject state on the basis of whether or not their correctly simulated input could ever reach its final state.
embedded_H is only accountable for the behavior of its input ⟨Ĥ⟩ applied to ⟨Ĥ⟩. embedded_H is not accountable for the behavior of the
computation that it is contained within: Ĥ applied to ⟨Ĥ⟩.
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)