This is an explanation of a key new insight into the halting problem
provided in the language of software engineering. Technical computer
science terms are explained using software engineering terms. No
knowledge of the halting problem is required.
It is based on fully operational software executed in the x86utm
operating system. The x86utm operating system (based on an excellent
open source x86 emulator) was created to study the details of the
halting problem proof counter-examples at the much higher level of
abstraction of C/x86.
typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider
void P(ptr x)
int Halt_Status = H(x, x);
HERE: goto HERE;
Output("Input_Halts = ", H(P, P));
When simulating halt decider H(P,P) simulates its input we can see that:
(1) Function H() is called from P().
(2) With the same arguments to H().
(3) With no instructions in P preceding its invocation of H(P,P).
The above shows that the simulated P cannot possibly terminate normally.
Because H can see the same (1)(2)(3) that we see H aborts its simulation
of P and rejects P as non-halting.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or continue
to run forever. Alan Turing proved in 1936 that a general
algorithm to solve the halting problem for all possible program-
input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts P will do. No H can exist that handles this case.
H and P implement the exact pathological relationship to each other as
described above. Because H(P,P) does handle this case the above halting
problem undecidable input template has been refuted.
*When this halt deciding principle understood to be correct*
A halt decider must compute the mapping from its inputs to an accept or
reject state on the basis of the actual behavior that is actually
specified by these inputs.
*Then (by logical necessity) this implements that principle*
Every simulating halt decider that correctly simulates its input until
it correctly predicts that this simulated input would never terminate
normally, correctly rejects this input as non-halting.
*H is a Pure function*
thus implements a *Computable function*
Thus H is Turing computable.
*Halting problem proofs refuted on the basis of software engineering*
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."