The Halting Problem
Ever woken up in the middle of the night, drenched with sweat, panting, with the sheets on the floor and thought, “But what about The Halting Problem!” Me neither. But if you have, Good Math, Bad Math has the most crisp description of the halting problem that I’ve read (memories of spending rainy undergrad afternoons trying to read Boolos and Jeffrey’s Computability and Logic come to mind here…) :
Fundamentally, what Turing did was prove that there are things that cannot be computed. He did that two ways: first, by defining an easy to understand problem which cannot be solved by any mechanical device; and second, by showing how common non-computable things are.
The first of Turing’s two proofs is commonly known as the Halting problem. The simplest version of the halting problem is the following. Suppose you have a computing machine M, and some program, P which can be run on M. Can you write a program which can by looking at P can determine whether or running P will eventually stop?
I actually find the more formalized presentation to be clearer. Take a computing machine, which we’ll call φ. (Don’t ask why φ, it’s just tradition!) Now, suppose we have a program P for φ which computes some function on its input. We’ll call that function φP. So φP(i) is the result of running the program P on the input i using the machine φ.
So the halting problem is really the question: given a machine φ, is there a program H where φH(P,i) = YES if and only if φP(i) will halt, and will return “NO” if φP(i) would not halt. The program H is called a halting oracle – so the question is, is it possible to write a halting oracle?
The answer is no. You can’t write a program like that – no such program can possibly exist. And it’s actually really quite easy to show you why – because if there were a halting oracle H, it’s very easy to write a program for which H is guaranteed to get the wrong answer.
Take the halting oracle program H. Write a program T which includes H, and which does the following:
If φH(T,i)=YES (meaning that the halting oracle says that T will halt on input I), then T will run an endless loop, thus never halting.
If φH(T,i)=NO (meaning that the halting oracle says that T will not halt on input i), then T will immediately halt.
So T completely defeats the Halting oracle. No matter what you do, for any program that claims to be able to tell whether other programs halt, there are programs for which they can’t get the right answer.