XPost: comp.theory, sci.logic, sci.math
#include <stdint.h>
#include <stdio.h>
typedef int (*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);
}
The above program is obviously infinitely recursive. It is self evident
that when 0 to ∞ steps of the input to H(P,P) are directly executed or correctly simulated that the input to H(P,P) never reaches its final instruction.
computation that halts a computation halts whenever it enters a final
state (Linz:1990:234) thus none of the simulated or executed 0 to ∞
steps of the input to H(P,P) ever halt.
PSR set (pathological self-reference)
H1(P1,P1) Is the above code.
H2(P2,P2) Is the above code where H2 simulates rather than directly
executes its input.
H3(P3,P3) Is the execution of N steps of the input of H1(P1,P1).
H4(P4,P4) Is the simulation of N steps of the input of H2(P2,P2).
Every Hn(Px,Py) that returns a value returns 1 except for instances of
{H3, H4} that determine whether or not to return {0,1} on the basis of
the behavior of their input.
The correct pure simulation of N steps of the input to H(P,P) by H is
always a correct halt deciding basis where P has reached its final state
or H has correctly detected that P would never reach its final state.
The point in the sequence of N steps where the execution trace of the simulation of P shows that P is about to call H(P,P) again with the same
input that H was called with provides conclusive proof that P would be infinitely recursive unless H aborted its simulation.
*In this H4(P4,P4)==0 computation P4 is dependent on H4 altering the
behavior of P4.*
When directly executed P(P) calls H(P,P) and the simulated P(P) reaches
the point where it would call H(P,P) with the same parameters that H was
called with H returns 0 to this directly executed P.
*In this H1(P4,P4)==1 computation P4 is independent of H1.*
H is a computable function that accepts or rejects inputs in its domain
on the basis that these inputs specify a sequence of configurations that
reach their final state.
Halting problem undecidability and infinitely nested simulation (V2)
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)