The Halting Problem

Here is a sketch of a proof that the halting program is uncomputable; that is, there does not exist a program which takes another program as input (or as the initial value of a string variable) and correctly outputs whether or not it halts. Always. (A program which sometimes correctly outputs this information is possible.)

This proof is usually formulated by encoding the text of a computer program into a single huge integer, using an encoding known as "Gödel numbers", which involves using the character or token values as exponents of the prime numbers and multiplying it all together. There is a unique factorization theorem which says that you can unambiguously retrieve the original exponents, if all of the bases were prime numbers.

These days, I think that string values work just as well, so long as we're happy to allow extremely long string variables. So the presentation here is in terms of strings, not encoded numbers. It doesn't actually change very much in the proof.

To accommodate input to a computer program, we allow the execution context to specify initial values of variables. If you like, you could consider this to be a parameterized function, or just a program fragment.

Theorem: There does not exist a program which correctly computes whether or not an arbitrary program terminates (the "halting problem").

Proof:

Definition: We will say that a program is self-terminating if it eventually halts when run with the string variable x initialized to the program's own text, all other string variables initialized to the empty string, and all numeric variables initialized to 0.

Let halt(x) be the string "yes" if the program represented by the string x is self-terminating and the string "no" if it is not.

We now prove that "halt(x)" is not computable, as follows.

Suppose that halt(x) is computable.
Then there exists a program which computes "x := halt(x)".

Let PROBLEM be the program:

(insert that program which computes "x := halt(x)" here)
while (x == "yes") {
}

Now:
Either PROBLEM is self-terminating or it is not.

If PROBLEM is self-terminating, then halt(PROBLEM) = "yes".
Consider an execution of PROBLEM with x initialized to the text of PROBLEM.
Upon entering the while loop, x will be "yes", so the program will not terminate.
Thus PROBLEM is not self-terminating.
This is a contradiction; so it can't be that PROBLEM is self-terminating.

If PROBLEM is not self-terminating, then halt(PROBLEM) = "no".
Again consider an execution of PROBLEM with x initialized to the text of PROBLEM.
Upon entering the while loop, x will be "no", so the program will terminate.
Thus PROBLEM is self-terminating.
This is a contradiction; so it can't be that PROBLEM is not self-terminating.

So in either case, the assumption that halt(x) is computable yields a contradiction.
Thus halt(x) is not computable.

If we had a program which solved the halting problem, we could use it to implement this halt(x) function.
Thus the halting problem is unsolvable.