#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

On 11/25/21 1:15 PM, olcott wrote:
> #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.

Yes, for THIS H that doesn't abort its processing of its input.

It isn't for any H that does abort its processing of its input. PERIOD.

FAIL.

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

Yes, For THIS H, it is clear that ITS P will be non-halting.

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

WRONG. Executing N steps does NOT show behavior for any machine that
takes more then N steps to reach its final state (it could halt in M
states with M > N, or it might be non-halting and NEVER reach such a
halting state)

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

But, since it is KNOWN by the behavior being defined for the outer H,
that the inner H will NOT not run infinitely, so the conclusion is
incorrect.

If Hn will abort its simulation in N steps, then Pn(n) wiil halt in N+k
steps, where k is the small number of steps needs to go from the entry
of P(P) to its call to H(P,P) plus the number of steps from the return
from H to the return of P.

Thus we know that since H(P,P) has been defined to execute no more than
N steps, a call to H with ANY parameters can not be itself non-halting
behavior. You can't have non-halting behavior in only N steps.

H's aborting lets P be Halting. PERIOD.

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

Right, and P then Halts, showing the 0 was the WRONG answer for H to
return if it is a Halting Decider.

Maybe it is a correct POOP decider, but it isn't a Halt Decider.

Remember, BY DEFINITION, the correct answer for H(p,i) is the behavior
of p(i) as an independent computation.

Since you just agreed that P(P) will halt when run that way, then the
right answer for H(P,P) can only be 1, thus 0 is wrong.

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