Skip to content

Lesson 40 ยท 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