Computer Science › Section M · Theory of computation › Topic M.4
A noncomputable function: the halting problem
Wouldn't it be useful to have a tool that checks any program and tells you whether it will ever stop? This topic proves that no such tool can exist, on any computer, now or in the future: the halting problem has no algorithmic solution.
A tool that cannot exist
Programs that hang in an endless loop are a familiar kind of bug. A tool that inspected any program, together with its input, and reported whether it would eventually stop would catch every one of them before release. The question of whether a given program halts on a given input is called the halting problem. In 1936 Alan Turing proved a result of this kind for his machines; the name "halting problem" came into use later. This topic gives the argument in full, using the notation from section F.
The halting problem
The question is: given a program P and an input I, does P halt when it runs on I? The halting function answers it: h(P, I) = 1 if P halts on I, and h(P, I) = 0 if it runs forever. This function is perfectly well defined, because every run either stops or does not, so each pair (P, I) has one definite answer. What we want to know is whether h is computable: is there a single algorithm that, for every program and every input, finishes and gives the correct answer?
Worked example: deciding particular programs
Here are three Tally programs from "Universal programming languages". 1. while X != 0: dec X; dec X. This always halts: each pass lowers X by 2, or to 0 when X = 1, because dec stops at 0, so X must reach zero. 2. while X != 0: dec X; dec Y, followed by while Y != 0: inc Y. After the first loop Y has dropped by X, stopping at 0; if anything is left, the second loop runs forever. So it halts exactly when Y ≤ X. 3. inc Y, followed by while Y != 0: dec X. This never halts, since Y is now at least 1 and the loop never changes it. Check: each answer relied on an insight about that one program. The halting problem asks for one method that works for every program.
Why running it is not enough
The obvious method is to run P on I and watch. If it halts, the answer is yes. But suppose it is still running after a million steps, or a billion. It might halt at the very next step, or it might never halt, and no amount of waiting can tell those apart. So running a program can confirm a yes answer eventually, but can never confirm a no. Studying the code instead, as in the worked example, settles many programs, but the proof below shows that no method of any kind settles them all.
Programs as inputs
A program is a text, and a text is data, so programs can be inputs to other programs. Compilers, interpreters and virus scanners take programs as input every day. A program can even be given its own text as input. This self-reference is the key to the proof. It works like the sentence "This sentence is false": if the sentence is true then it is false, and if it is false then it is true. The proof builds a program whose behaviour on its own text contradicts any prediction made about it.
The assumption and the trap
Suppose, hoping for a contradiction, that someone has written a function Halts(P, I) that, for every program text P and every input I, always finishes and returns True if P halts on I and False if it does not. Using it, write this program:
Trouble asks what P would do when given its own text, then does the opposite: it loops forever if P would halt, and halts if P would not. If Halts is a genuine program, Trouble is one too, since it uses only Halts, an if and a loop.
Worked example: the contradiction
Let T be the text of Trouble, and consider running Trouble(T). 1. This run either halts or it does not; there is no third possibility. 2. Suppose it halts. Halts is always correct, so Halts(T, T) returns True. Then Trouble takes the if branch and loops forever, so it does not halt. Contradiction. 3. Suppose it does not halt. Halts always finishes and is always correct, so Halts(T, T) returns False. Then Trouble takes the else branch and returns at once, so it halts. Contradiction. 4. Both possibilities are impossible, so the assumption was false. Conclusion: no program Halts with the stated property can exist, and the halting function is noncomputable.
What the proof does and does not say
The proof says that every proposed halting checker fails on at least one pair, answering wrongly or not at all: whoever offers a candidate, Trouble built from it defeats it. It does not say particular programs cannot be analysed; the three in the worked example were easy. Nor is it about speed: no faster computer, no extra time and no cleverer language helps. Since every universal language can express Trouble, no program in any of them computes the halting function, and by the Church–Turing thesis no algorithm does. The textbook makes the same argument with Bare Bones programs run on their own encoding.
More undecidable problems
Once one problem is known to be undecidable, others follow. Could a tool decide whether any program ever prints hello? To check whether P halts on I, build a program Q that runs P on I with P's own output switched off, and then prints hello. Q prints hello exactly when P halts on I, so a hello-detector would solve the halting problem, and therefore none exists. In the early 1950s Henry Rice generalised this: every non-trivial question about a program's input-output behaviour, meaning one that some programs pass and others fail, is undecidable. That includes "do these two programs always give the same output?" and "does this program halt on every input?"
Living with the limit
Undecidability does not make program checking useless. Compilers and analysis tools spot many infinite loops and other bugs, but each such tool must sometimes give a wrong answer, or reply "don't know", and well-designed tools choose the second. Systems that cannot afford to hang use timeouts, stopping any task that runs too long. For important code, programmers prove termination program by program, as "Efficiency and correctness" did with a loop that moves steadily towards its end.
Common mistakes to avoid
First, thinking the halting problem means no one can tell whether any program halts; many programs are easy to settle. Second, believing a faster computer or more patience would solve it; the proof involves no time limit. Third, "run it and see", which can never confirm that a program runs forever. Fourth, objecting that Trouble cheats: it is a legitimate program whenever Halts is. Fifth, forgetting that Halts must always finish; a checker that may run forever is not a solution. Sixth, confusing halting on one input with halting on every input.
Key takeaways
The halting problem asks whether program P halts on input I. Its function is well defined but noncomputable. Assume a program Halts always answers correctly; Trouble(P) does the opposite of what Halts predicts for P on its own text; running Trouble on its own text contradicts both possible answers, so Halts cannot exist. Every candidate checker fails on some input, though many single programs are easy to settle. Problems whose solution would solve the halting problem, such as detecting a printed hello, are undecidable too, and Rice's theorem extends this to every non-trivial question about what programs compute.
Flashcards
Flashcard
Given program P and input I, does P halt on I?
Test your understanding
Question 1 of 5
The Tally program while X != 0: (dec X; dec Y), followed by while Y != 0: inc Y, starts with X = 2 and Y = 5. What happens?
Question 2 of 5
Why does running P on I and waiting not solve the halting problem?
Question 3 of 5
In the proof, suppose Trouble(T), where T is Trouble's own text, halts. What follows?
Question 4 of 5
What does the halting-problem proof actually establish?
Question 5 of 5
A company claims its tool can decide, for any program, whether it ever prints hello. Why must the claim be false?
