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

typedef void (*ptr)();

int H(ptr x, ptr y)
{
x(y); // direct execution of P(P)
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
int P(ptr x)
{
H(x, x);
return 1; // Give P a last instruction at the "c" level
}

int main(void)
{
H(P, P);
}

computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)

Combinations of H/P having pathological self-reference (PSR set)
For every possible H of H(P,P) invoked from main() where P(P) calls this
same H(P,P) and H simulates or executes its input and aborts or does not
abort its input P never reaches its last instruction.

One element of the above (PSR set) Hz simply simulates 100 steps of Pz
and returns.

This provides a specific concrete example where the input to H(P,P)
never halts and P(P) halts thus conclusively proving that such an
example exists.

Instead of simply simulating the first 100 instructions of P halt
decider H might abort the simulation of its input on the basis of the
behavior of this input. It is still the case that the input to H(P,P)
never halts and P(P) halts.

When H sees that P calls H(P,P) with the same parameters that it was
called with this gives H its correct (infinite recursion) halt deciding
basis. H(P,P) then aborts the simulation of its input and returns 0.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
The reasoning applied to H(P,P) and P(P) equally applies to Linz Ĥ.qx
⟨Ĥ⟩ ⟨Ĥ⟩ and Ĥ ⟨Ĥ⟩

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2



--
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)