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.

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

<rewrite>
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.
</rewrite>

The sequence of 1 to N configurations specified by the input to H(X, Y)
cannot be correctly construed as anything other than the sequence of 1
to N steps of the (direct execution, x86 emulation or UTM simulation of
this input by H.

When H directly executes 1 to N steps of its actual input this
conclusively proves that this is the correct direct execution basis for
the halt decider's halt status decision. The simulation of this same
input derives the exact same sequence of steps.

The point in the sequence of 1 to 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.

When P(P) calls H(P,P) reaches the above point in its simulation it
returns 0 to P.

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