The following H and P have the above specified pathological relationship to each other.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.
https://en.wikipedia.org/wiki/Halting_problem
Simulating halt decider H detects that its simulated input is essentially calling H in infinite recursion. H aborts its simulation on this basis and rejects this input as non-halting.typedef void (*ptr)();
int H(ptr p, ptr i);
void P(ptr x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
int main()
{
Output("Input_Halts = ", H(P, P));
}
Once this halt deciding principle is accepted
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 is understood to implement that
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.
The execution trace of function P() simulated by function H() shows:
(1) Function H() is called from P().
(2) With the same parameters to H().
(3) With no instructions in P() that could possibly escape this infinitely recursive simulation.
This proves that H(P,P) correctly predicts that its correctly simulated input would never terminate normally.