XPost: comp.theory, sci.logic, sci.math

Halting problem undecidability and infinitely nested simulation (V3)

We define Linz H to base its halt status decision on the behavior of its
pure simulation of N steps of its input. N is either the number of steps
that it takes for its simulated input to reach its final state or the
number of steps required for H to match an infinite behavior pattern
proving that the simulated input would never reach its own final state.
In this case H aborts the simulation of this input and transitions to H.qn.

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

Because it is known that the UTM simulation of a machine is
computationally equivalent to the direct execution of this same machine
H can always form its halt status decision on the basis of what the
behavior of the UTM simulation of its inputs would be.

When Ĥ applied to ⟨Ĥ⟩ has embedded_H simulate ⟨Ĥ⟩ ⟨Ĥ⟩ 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)

This shows that the simulated input to embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ would never reach its final state conclusively proving that this simulated input
never halts. This enables embedded_H to abort the simulation of its
input and correctly transition to Ĥ.qn.

if embedded_H does correctly recognize an infinitely repeating behavior
pattern in the behavior of its simulated input: ⟨Ĥ⟩ applied to ⟨Ĥ⟩ then
embedded_H is necessarily correct to abort the simulation of its input
and transition to Ĥ.qn.

Because a halt decider is a decider embedded_H is only accountable for computing the mapping from ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn on the basis of the
behavior specified by these inputs. embedded_H is not accountable for
the behavior of the computation that it is contained within: Ĥ applied
to ⟨Ĥ⟩ because this is not an actual input to embedded_H.




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)