Oh Hey There

The Fucking Halting Problem

Or rather a variation of it called “the acceptance problem”. Suppose we have a program P and we want to know that P accepts or correctly computes some input i. Let H(P,i) be a program that tells us whether a program P accepts input i. Thus:

H(P,i) returns true when when P accepts i.
H(P,i) returns false when when P does not accept i.

Let be [P] be an encoding of program P (that is, the “code” of P). Running H(P,[P]) tells us whether P accepts itself as input.

Next, let D([P]) be a program that runs H(P,[P]) as a subroutine but returns the opposite of H. Thus, D returns false when P accepts its encoding [P] as input and returns true when P does not accept itself as input.

Now, Run D([D])—that is, run D with its encoding as input:

D([D]) returns true when H(D,[D]) returns false and H(D,[D]) returns false when D([D]) returns false.
- So, D([D]) returns true when D([D]) returns false.
D([D]) returns false when H(D,[D]) returns true and H(D,[D]) returns true when D([D]) returns true.
- So, D([D]) returns false when D([D]) returns true.