XPost: comp.theory, sci.math, sci.logic

#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.
∀H ∊ PSR_set ∀P ∊ PSR_set (Input_Never_Halts(H(P,P)))

[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 ⊆ PSR_set ∀H ∊ PSR_Subset (Halts(H(P,P)))

[PSR_subset + P(P)_set] Appending the computation int main(void) { P(P);
} to the PSR_subset we derive another set having the exact same H/P
pairs. In this set the input to H(P,P) never halts and P(P) halts. This
proves that no contradiction is formed.
∃H ∊ [PSR_subset + P(P)_set] ∃P ∊ [PSR_subset + P(P)_set] ((Input_Never_Halts(H(P,P))) ∧ Halts(P(P)))

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

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.
H is a correct decider and H has a correct halt deciding 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.

See Page 3 of:
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)