XPost: comp.theory, sci.logic, sci.math
On 3/25/2022 3:13 PM, Ben Bacarisse wrote:
Which Ĥ is this?
A Simulating Halt Decider (SHD) computes the mapping from its input to
its own accept or reject state based on whether or not the pure
simulation of its input could reach the final state of this input in a
finite number of simulated steps.
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 ∞
If the pure simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H would reach its final state.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the pure simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H would never reach its final state.
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩...
The above shows that the simulated input to embedded_H never reaches its
own final state whether or not its simulation is aborted.
(a) If the simulation is not aborted the above sequence never ends.
(b) If the simulation is aborted the entire chain of recursive
simulations immediately stops.
In no case does the simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ ever reach its final state
⟨Ĥ⟩.qn thus never meets the Linz definition of halting:
computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234) Thus if embedded_H rejects its input it
is necessarily correct.
Because all halt deciders are deciders they compute the mapping from
their input finite strings inputs to their own accept or reject state.
Halt deciders (because they are deciders) do not compute any mappings
from non-finite string non-inputs.
No halt decider ever determines the halt status of the computation that contains its actual self thus embedded_H does not compute the mapping
from Ĥ ⟨Ĥ⟩ because it is neither an input nor a finite string.
Even Linz was confused by this. embedded_H is not supposed to report on
itself or the computation that it is contained within.
As long as it is verified that the simulated input to embedded_H cannot
reach its final state then we know that this simulated input cannot meet
the Linz definition of halting.
As long as we know that this simulated input cannot meet the Linz
definition of halting we know that this input specifies a non-halting
sequence of configurations.
As long as we know that this input specifies a non-halting sequence of configurations then we know that embedded_H would be correct to reject
this input.
Halting problem undecidability and infinitely nested simulation (V4)
https://www.researchgate.net/publication/359349179_Halting_problem_undecidability_and_infinitely_nested_simulation_V4
--
Copyright 2022 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)