Undecidability & the Halting Problem

Some problems are provably beyond the reach of any algorithm — and understanding why is one of the deepest results in all of mathematics.

Learning Objectives

Decidable vs. Undecidable Problems

A decision problem asks a yes/no question about a given input. A problem is decidable if there exists a Turing machine that, for every input, always halts and correctly outputs "yes" or "no." A problem is undecidable if no such algorithm can ever exist — not because we haven't found one yet, but because it has been proved that none can.

Definition — Decidability

A language L is decidable (recursive) if there is a Turing machine M that halts on every input: accepting strings in L and rejecting strings not in L. L is undecidable if no such TM exists.

Undecidability is not a practical limitation — it is a fundamental mathematical boundary. A problem that is undecidable cannot be solved by any computer, in any programming language, with any amount of time and memory. The existence of such problems was one of the most startling discoveries of 20th-century mathematics.

Diagram showing decidable, recognisable and unrecognisable languages
The landscape of decision problems: decidable languages sit inside the recognisable ones, which sit inside all languages. Most languages — in a precise mathematical sense — are not even recognisable.
Image: Wikimedia Commons, CC BY-SA 3.0

The Halting Problem

The most famous undecidable problem is the Halting Problem: given a description of a Turing machine M and an input string w, does M halt when run on w?

The Halting Problem — HALT

HALT = {⟨M, w⟩ | M is a Turing machine that halts on input w}. Theorem (Turing, 1936): HALT is undecidable. There is no algorithm that, given any program and any input, correctly determines in all cases whether the program will eventually stop.

Proof by Contradiction (Diagonalisation)

The proof is an elegant argument by contradiction using self-reference. Suppose for the sake of contradiction that a decider H exists for HALT — a TM that always halts and outputs "yes" if M halts on w, and "no" otherwise.

Proof Sketch — Halting Problem is Undecidable
  • Assume a decider H exists such that H(⟨M, w⟩) = accept if M halts on w, reject otherwise.
  • Construct a new TM D that, on input ⟨M⟩, runs H on ⟨M, ⟨M⟩⟩ and does the opposite: loops if H accepts, halts if H rejects.
  • Ask: what does D do on input ⟨D⟩ (feeding itself as input)?
  • If D halts on ⟨D⟩, then H said D loops — but D did the opposite (halts). Contradiction.
  • If D loops on ⟨D⟩, then H said D halts — but D did the opposite (loops). Contradiction.
  • Conclude: The assumed decider H cannot exist. HALT is undecidable. ∎

This argument is closely related to Cantor's diagonal argument (used to prove the uncountability of the real numbers) and to Gödel's Incompleteness Theorems. The self-referential structure is the key: any proposed decider can be turned against itself.

Cantor's diagonal argument diagram
Cantor's diagonal argument — the mathematical technique underlying Turing's proof. By constructing a value that differs from every listed element in at least one position, one derives a contradiction, proving the list cannot be complete.
Image: Wikimedia Commons, CC BY-SA 3.0

Reductions and Further Undecidable Problems

Once we know the Halting Problem is undecidable, we can prove other problems undecidable via reduction: if problem A is reducible to problem B (meaning a solution to B would give us a solution to A), and A is undecidable, then B must also be undecidable.

Definition — Mapping Reduction

Language A is mapping reducible to language B (written A ≤ₘ B) if there is a computable function f such that for all w: w ∈ A ⟺ f(w) ∈ B. If A ≤ₘ B and A is undecidable, then B is undecidable.

Other Famous Undecidable Problems
  • Acceptance problem (A_TM): Does TM M accept input w? Undecidable via reduction from HALT.
  • Rice's Theorem: Any non-trivial property of a Turing machine's language is undecidable. This single theorem renders undecidable a vast class of questions about program behaviour.
  • Post Correspondence Problem (PCP): Given a finite set of domino pairs, can tiles be arranged in a sequence so the top and bottom strings match? Undecidable, and frequently used to prove other undecidability results.
  • Hilbert's Tenth Problem: Does a given Diophantine equation (polynomial with integer coefficients) have an integer solution? Undecidable — proved in 1970 by Matiyasevich.

Implications for Computer Science

Undecidability has direct practical consequences. No general-purpose tool can verify that an arbitrary program is free of bugs, will always terminate, or satisfies a given specification. Automated theorem provers, static analysers, and model checkers work around this boundary by focusing on restricted classes of programs or properties — trading generality for decidability. Understanding the limits of computation is not just theoretical: it shapes what software tools can and cannot promise.