Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 59 · Decidability and Computability

The Halting Problem: Proof of Undecidability

State and prove the halting problem is undecidable by diagonalization. See the contradiction in Python and learn why A_TM is recognizable but not decidable.

Can a program examine another program and always tell whether it will eventually stop? It would be wonderful: no more infinite loops in production code. Alan Turing proved in 1936 that no such universal checker can exist. The halting problem is the first, and the most famous, problem shown to be undecidable. Almost every other undecidability proof is a reduction from it.

The halting problem

Question Given program P and input x, does P(x) ever stop?
Answer No algorithm answers it for all pairs.
Method Feed a program to itself, then flip the answer.

Recognizable (just run it), but not decidable.

1 / 2

The statement

Define the language

HALT = { ⟨M, w⟩ : M is a Turing machine that halts on input w }

and its close cousin

A_TM = { ⟨M, w⟩ : M accepts w }.

Here ⟨M, w⟩ is an encoding of the machine and its input as a string, which is possible because machines have finite descriptions.

Both languages are recursively enumerable. A universal Turing machine U simulates M on w: if M accepts, U accepts (for A_TM); if M halts, U accepts (for HALT). If M loops, so does U, and that is acceptable for a recognizer.

Neither is decidable. To decide, U would have to know that M is going to loop forever, and simulation alone can never confirm that: no number of steps is enough.

The proof by contradiction

Suppose there is a decider H for HALT: given ⟨M, w⟩, it always halts and says "halts" or "loops".

Build a new machine D that takes the description ⟨M⟩ of a machine as input:

  1. Run H on ⟨M, ⟨M⟩⟩: "does M halt when given its own description as input?"
  2. If H says "halts", then D enters an infinite loop.
  3. If H says "loops", then D halts immediately.

So D does the opposite of what H predicts about M(⟨M⟩).

Now ask what happens when D is run on its own description ⟨D⟩:

  • If D halts on ⟨D⟩, then H said "halts", so by step 2 D loops. Contradiction.
  • If D loops on ⟨D⟩, then H said "loops", so by step 3 D halts. Contradiction.

Both cases are impossible, so the assumed decider H cannot exist. ∎

flowchart TB
    A["Assume decider H for HALT exists"] --> B["Build D: on input ⟨M⟩, run H(⟨M⟩, ⟨M⟩) and do the opposite"]
    B --> C["Run D on ⟨D⟩"]
    C --> D1["D halts on ⟨D⟩ ⇒ H said halts ⇒ D loops"]
    C --> D2["D loops on ⟨D⟩ ⇒ H said loops ⇒ D halts"]
    D1 --> E["Contradiction: H cannot exist"]
    D2 --> E

The proof is the diagonal argument in disguise. Imagine a table whose rows and columns are all machines, with entry (i, j) being "does M_i halt on ⟨M_j⟩?". The machine D is the row obtained by flipping the diagonal, so it differs from every machine M_i on the input ⟨M_i⟩ and is therefore a machine that is not in the list: a contradiction, since the list contained all machines.

Seeing the contradiction in Python

We can play the proof out with real code. A "program" is a Python generator function (each yield is a step). Given any candidate halting-checker h, the function make_paradox(h) builds the program D from the proof. We then check what h says about it, and what happens in reality. Whatever h answers, it is wrong about the paradox program.

Python Every halting checker fails on its own paradox

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three candidates fail in three ways: one is wrong because it says yes, one because it says no, and the third never answers because it tries to simulate a program that simulates it. A checker that always halts and is always right would have to dodge all three, and the proof says no such checker exists.

What can be done

The halting problem is semi-decidable: if the program does halt, we find out by running it. What we cannot do is certify non-halting in general. Some programs are easy to analyze; no single method works for all.

Python Halting: easy to confirm, impossible to refute

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

  • count_to_million stops in about a thousand steps and collatz_27 in 112 steps: running them confirms halting.
  • forever never stops, but running it for any number of steps proves nothing.
  • odd_perfect_number shows how deep the problem goes: knowing whether it halts would solve a centuries-old open problem in number theory. A halting oracle would answer all such questions at once, which is another sign that none can exist.

Consequences

  1. A_TM and HALT are undecidable but recognizable. Hence RE ≠ recursive.
  2. The complement of HALT is not RE. If both HALT and its complement were RE, HALT would be decidable (see recursive and RE languages).
  3. No perfect program analyzer exists. No tool can decide, for all programs, whether the program terminates, whether it ever prints "hello", whether two programs are equivalent, or whether a variable is ever used. Real tools (compilers, linters, type checkers) are approximations: they accept only a restricted set of programs, give up on hard cases, or allow false alarms.
  4. Undecidability spreads by reduction: to show a new problem undecidable, show that a decider for it would give a decider for the halting problem. That is the topic of the next lessons.

The halting problem is about all programs and inputs at once. For a particular program the answer exists and may be easy to prove. What is impossible is a single algorithm that works for every program.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does the machine D in the proof of the halting problem do?

    D diagonalizes against H: if H says M halts on its own description, D loops; otherwise D halts.
  2. 2. Which statement about HALT is true?

    A universal machine confirms halting by simulation, but no machine can always confirm looping.
  3. 3. Why is the complement of the halting problem not recursively enumerable?

    A language and its complement both RE implies decidable.
  4. 4. In the Python demo, why does the step_limited checker crash on the paradox?

    The paradox calls the checker on itself, so a checker that simulates it recurses without end.

Summary

  • HALT asks whether a machine halts on an input; it is recognizable (by simulation) but undecidable.
  • The proof builds D, which does the opposite of what the assumed decider predicts, and runs it on itself.
  • It is a diagonal argument on the table "machine i on description j".
  • Consequently the complement of HALT is not RE, and no perfect program analyzer exists.
  • Undecidability of other problems is shown by reducing the halting problem to them.

Next: Reductions and Rice's theorem