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);
}
PSR set (pathological self-reference) 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,P4) 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).
Neither H1 nor H2 return any value. H3 or H4 may return some integer
value or not.
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)