Concise refutation of halting problem proofs V21 [ precisely defined se
From
olcott@21:1/5 to
All on Sat Nov 20 11:40:47 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);
}
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
For every possible 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
subset the input to H(P,P) never halts and H(P,P) halts.
When int main(void) { P(P); } is invoked on H/P elements of the above
PSR subset, then we have a cases where the input to H(P,P) never halts
and P(P) halts.
The above cases conclusively prove that when the input to H(P,P) never
halts and the same P(P) does halt that this does not form any
contradiction.
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 function that correctly maps every element of its domain to {0,1}
on the basis of whether or not these elements reach their final state
and halt. On this basis H is a halt decider.
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)