XPost: comp.theory, sci.logic, sci.math
Halting problem undecidability and infinitely nested simulation (V4)
When a halt decider bases its halt status decision on the behavior of
its simulated input then all of the conventional halting problem counter example inputs would be determined to be non-halting.
A copy of Linz H is embedded at Ĥ.qx as a simulating halt decider (SHD).
Ĥ.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.
*By these two principles this proof is validated*
(1) A halt decider (because it is a decider) must report on the behavior specified by its finite string input. A decider computes the mapping
from its input finite strings to an accept or reject state.
(2) The behavior specified by this input is the actual behavior of this
input when it is correctly simulated by its simulating halt decider
(SHD) that contains a full UTM.
The key point that that everyone (including Peter Linz) has an
impossibly difficult time with is that embedded_H can correctly
transition to Ĥ.qn indicting that its input does not halt.
Everyone (including Peter Linz) incorrectly believes that this is contradictory.
Everyone assumes the the behavior of the executed Ĥ applied ⟨Ĥ⟩ must be the same as the input ⟨Ĥ⟩ ⟨Ĥ⟩ simulated by embedded_H or it is wrong.
We can easily verify that the correct behavior of Ĥ applied ⟨Ĥ⟩ is not the same as the correct behavior as the input ⟨Ĥ⟩ ⟨Ĥ⟩ simulated by embedded_H.
No one ever bothers to do this because of their deep religious
conviction that they must either be the same or be incorrect.
https://www.researchgate.net/publication/359349179_Halting_problem_undecidability_and_infinitely_nested_simulation_V4
--
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)