Code: Select all
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
To eliminate the pathological self-reference(Olcott 2004) from the halting problem such that there is no feedback loop between what the halt decider decides and how the input behaves the simulating halt decider simply watches what the input does without interfering at all.
As soon as the simulating halt decider determines that the simulation of the input on its input would never reach its own final state (whether or not this simulation is aborted) it aborts the simulation of this input and reports that its input does not halt.
Here it is in an adaption of the Peter Linz notation: Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ never reaches its final state (whether or not this simulation is aborted) then when Ĥ.qx transitions to Ĥ.qn it is necessarily correct.
My new paper: Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publicatio ... simulation
Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (315-320)
https://www.liarparadox.org/Peter_Linz_ ... 5-320).pdf