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

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

[PSR set] Combinations of H/P having pathological self-reference
Every 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.

[PSR subset] Because we know that the input to H(P,P) never halts for
the whole PSR set and a subset of these H/P combinations aborts the
execution or simulation of its input then we know that for this entire
PSR subset the input to H(P,P) never halts and H(P,P) halts.

[PSR subset + P(P) set] Appending the computation int main(void) { P(P);
} to the PSR subset on the basis of the exact same H/P pairs that are in
this subset we find that this P(P) halts while the input to its
corresponding H(P,P) never halts.

[Decidable_PSR subset] The subset of the PSR subset where H returns 0 on
the basis that H correctly detects that P specifies infinite recursion
defines the decidable domain of function H.

(a) Math function H: maps specified sequences of configurations in its
domain to {0,1}
(b) int H(ptr x, ptr y) maps sequences of configurations specified by
(x,y) to {0,1}.
(c) TM H maps sequences of configurations specified on its tape to H.qn
and H.qy.
on the basis of whether or not this sequence of configurations reaches
its final state.

Because there is no way to separately distinguish the independent
computation P(P) from a UTM simulation of (P,P) to any math function C
function or TM decider the simulation of the input to H must always be a correct basis.

The above H could detect that its simulated P is calling H(P,P) with the
same parameters that it was called with, thus specifying infinite
recursion.



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