The halting problem, explained with Turing’s proof

The problem

Some programs obviously stop: print("hi"). Some obviously don’t: while true: pass. Many are hard to judge by eye. Here is a short one:

def collatz(n):
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1

Started at 27 it stops after 111 steps, and at 97 after 118. Every starting value ever tried stops, but nobody has proved that every one does: whether this four-line loop halts for all positive $n$ is the Collatz conjecture, open since 1937. A general halting tester would settle it, and countless other open problems, at once.

The halting problem

Given the source code of a program $P$ and an input $x$ , decide whether $P$ eventually stops when run on $x$ .

A decider for it would be a program $H$ that always stops and answers correctly: $H(P, x) = \text{halts}$ if $P(x)$ stops, and $H(P, x) = \text{loops}$ if it runs forever.

The claim is not that halting is hard to decide, or slow. It is that no program at all, however clever and however much time it is allowed for each answer, gives the right answer for every program and input. Problems like this are called undecidable.

Turing’s proof, step by step

The proof is by contradiction: assume a decider exists, and use it to build a program that it must get wrong.

Theorem: the halting problem is undecidable

No program $H$ decides, for every program $P$ and input $x$ , whether $P(x)$ halts.

Suppose, for contradiction, that $H(P, x)$ exists: it always stops, and answers “halts” or “loops” correctly.
Programs are text, so a program can be given its own source code as input. Using $H$ as a subroutine, write this program $D$ :
```
def D(P):
    if H(P, P) == "halts":
        while True: pass     # loop forever
    else:
        return               # stop at once
```
$D$ asks whether $P$ halts when fed itself, then does the opposite.
Now run $D$ on its own source code. $H(D, D)$ must return one of its two answers.
If $H(D, D)$ says “halts”, then $D(D)$ takes the first branch and loops forever. So $D(D)$ does not halt, and $H$ was wrong.
If $H(D, D)$ says “loops”, then $D(D)$ takes the second branch and stops. So $D(D)$ halts, and $H$ was wrong again.
Either way $H$ gives a wrong answer on the input $(D, D)$ , contradicting the assumption that it is always right. So no such $H$ exists. $\blacksquare$

Nothing in the argument depends on how $H$ works inside. Whatever program you propose as a halting decider, the construction produces a specific input on which it fails.

Why it is called a diagonal argument

List every program as $P_1, P_2, P_3, \dots$ (programs are finite strings, so they can be listed). Make a table whose cell in row $i$ , column $j$ says whether $P_i$ halts on input $P_j$ . The program $D$ reads the diagonal and flips it: on input $P_i$ it does the opposite of what $P_i$ does on $P_i$ . So $D$ differs from every $P_i$ at the $i$ -th column and cannot be any row of the table. But $D$ is a program, so it must be a row. The contradiction shows the table cannot be computed. This is the same trick Cantor used in 1891 to show that the real numbers cannot be listed.

Try to build a halting decider

1. The diagonal table

Row = program, column = the input it is given. Suppose a decider H filled in every cell correctly. Click any cell to change H’s answer; D is built from the diagonal by flipping it.

Program	on P₁	on P₂	on P₃	on P₄	on P₅
P₁
P₂
P₃
P₄
P₅
D

2. Ask H about D running on itself

D(x) asks H whether x halts on x, then does the opposite. What should H answer for D(D)?

What “program” means here

Turing made “program” precise with his machines: a finite control reading and writing symbols on an unbounded tape. The result holds for any model of computation that is as powerful, which includes every general-purpose programming language with unbounded memory. By the Church–Turing thesis, anything we would call an algorithm can be written as such a machine, so the halting problem has no algorithmic solution, full stop.

The unbounded memory matters. A finite-state machine, or a real computer with a fixed amount of memory, has finitely many configurations. Run it long enough and it either stops or repeats a configuration, after which it loops forever. So halting is decidable for finite machines in principle; the catch is that a machine with a gigabyte of memory has $2^{8 \times 2^{30}}$ configurations, and waiting for a repeat is hopeless in practice.

Rice’s theorem: almost everything is undecidable

Once one problem is known to be undecidable, others follow by reduction: if a decider for problem $B$ could be used to decide halting, then $B$ is undecidable too. For example, “does $P$ ever print the word done?” is undecidable: given $P$ and $x$ , build a program that runs $P(x)$ silently and then prints done. It prints done exactly when $P(x)$ halts.

Rice’s theorem (1953) Every non-trivial property of what a program computes is undecidable. “Non-trivial” means some programs have the property and some don’t; “what it computes” means the property depends only on the program’s input–output behaviour, not on how its code is written.

So no algorithm decides, for all programs, whether a program returns 0 on every input, whether two programs compute the same function, whether a program ever divides by zero, or whether it is a virus. Properties of the text, such as “does the source contain a loop?” or “does it use more than 100 lines?”, are decidable: they are not about behaviour.

What this means for real tools

Undecidability does not make program analysis useless. It means every analysis has to give something up, and good tools choose carefully what:

Over-approximate. A type checker or static analyser may reject some correct programs (false alarms) so that it never accepts an incorrect one. When a compiler warns that a variable “may be used uninitialised” in code you know is fine, this is why.
Under-approximate. Testing and bug-finding tools report only real problems but can miss some.
Restrict the language. Total languages, used in proof assistants, only allow recursion that provably terminates, so every program halts. They give up some programs to get the guarantee.
Answer “don’t know”. Termination provers prove that many real programs halt, and give up on the rest. A time-out is an honest third answer.

Common misconceptions

“So we can never tell whether a program halts.”: For a particular program we often can, by proof. The theorem only says no single algorithm works for all programs.
“Just run it and see.”: Running it answers “halts” when it halts, but if it hasn’t stopped yet you never learn whether it will. This gives a semi-decision procedure: the halting set is recognisable (computably enumerable) but not decidable. Its complement, “runs forever”, is not even recognisable.
“A faster computer or quantum computer would help.”: No. The proof makes no assumption about speed. Quantum computers compute the same functions as classical ones, just sometimes faster.
“The proof is a trick about self-reference that never matters in practice.”: Self-reference is only the tool for the proof. Through reductions, the same limit applies to ordinary questions about ordinary programs, as Rice’s theorem shows.

References

A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society s2-42(1), 1937 (read 1936). doi:10.1112/plms/s2-42.1.230
H. G. Rice, “Classes of recursively enumerable sets and their decision problems”, Transactions of the American Mathematical Society 74(2), 1953. doi:10.1090/S0002-9947-1953-0053041-6
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012. Chapters 4 and 5.
“Halting problem”, Wikipedia.

The problem

Turing’s proof, step by step

Theorem: the halting problem is undecidable

Why it is called a diagonal argument

Try to build a halting decider

1. The diagonal table

2. Ask H about D running on itself

What “program” means here

Rice’s theorem: almost everything is undecidable

What this means for real tools

Common misconceptions

Related results

References

Keep going

Finite-state machines

Sets, relations and functions

Recursion