Concise refutation of halting problem proofs V30 [ finally mathematical
From
olcott@21:1/5 to
All on Wed Nov 24 11:49:54 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);
}
PSR set: 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.
We can think of the combinations of (H,P) as an enumerated sequence of
finite strings of C source-code. The above source code specifies the
H0(P0,P0) first element of this sequence.
Computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)
PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of N
steps of its input this input still never reaches its last instruction
and Hn(Pn, Pn) halts.
PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of N
steps of its input this input still never reaches its last instruction
and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns 0
the returned halt status corresponds to the actual behavior of the input
to Hn(Pn, Pn).
PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns 0
on the basis that this input matches the infinite recursion behavior
pattern. Hn(Pn, Pn) detects that its input is calling H again with the
same input that it was called with. This makes Hn a correct halt decider
of this input.
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.
--
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)