Concise refutation of halting problem proofs V23
From
olcott@21:1/5 to
All on Sun Nov 21 16:29:23 2021
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);
}
*H is a computable function that correctly decides whether or not
elements in its domain reach their final state*
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.
When we analyize the computation int main(void) { P(P); } as if it was
in 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.
--
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)