Concise refutation of halting problem proofs V16
From
olcott@21:1/5 to
All on Wed Nov 17 09:24:46 2021
XPost: comp.theory, sci.logic, sci.math
#include <stdint.h>
typedef void (*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;
}
int main(void)
{
H(P, P);
}
We can determine the behavior of the input to H(P,P) for an infinite set
of different definitions of H by using categorically exhaustively
complete reasoning. There are only four categories of possible
definitions for H:
(1) H(P,P) simply executes its input: main() calls H(P,P) that calls
P(P) that calls H(P,P)...
(2) H(P,P) simulates its input.
(3) H(P,P) executes its input** and aborts this execution at some point.
**(a debugger could be used).
(4) H(P,P) simulates its input and aborts this simulation at some point.
Case (1) (complete source code is provided above) shows that P never
reaches its last instruction.
Case (2) a correct simulation of the input to H(P,P) must have
equivalent behavior to case (1).
Case (3) and (4) any sub-sequence of (1) and (2) can't have instructions
not included in (1) or (2).
Thus for cases (1)(2)(3)(4) P never reaches its last instruction.
For every H that
simulates or
executes its input and
aborts or
does not abort its input
P never reaches its last instruction.
--
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)