Module 2 · MIT 18.404J Lectures L8–L9 · Sipser §4.2, §5.1
references open in new tabs →💬 Ask Khayyam ↗

Undecidability & the Halting Problem

There are problems that no algorithm can solve. We prove this with one bold diagonal stroke, then leverage it.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration

1 · Cantor's diagonal argument — the seed of everything

Before we say anything about Turing machines, we will play with a much older and more elementary idea: there are more functions ℕ → {0, 1} than there are natural numbers. That sounds harmless. By the end of this module it will have killed off every hope of a universal algorithm.

The strategy is proof by contradiction: suppose someone hands us a complete list of every function f : ℕ → {0, 1}. We will construct a brand new function g that the list cannot possibly contain. The whole proof fits in three moves — assume the list, look at its diagonal, flip every bit on that diagonal:

Cantor in three moves · the whole proof on one page 1 · Assume the list every function is some row f₁ : 0 1 0 1 … f₂ : 1 1 0 0 … f₃ : 0 0 0 1 … f₄ : 1 1 1 0 … ⋮ "Build next row" adds one row 2 · Look at the diagonal one cell from each row: fᵢ(i−1) f₁ 0 1 0 1 … f₂ 1 1 0 0 … f₃ 0 0 0 1 … f₄ 1 1 1 0 … ⋮ diagonal reads: 0, 1, 0, 0, … 3 · Flip → contradiction g(i) = 1 − fᵢ₊₁(i) Take the diagonal … 0, 1, 0, 0, … … flip every bit: g = 1, 0, 1, 1, … g disagrees with fᵢ at column i − 1. So g ≠ every fᵢ "Flip the diagonal" Why g disagrees with each fᵢ — one cell at a time f₁(0) = 0 vs g(0) = 1 ≠ f₂(1) = 1 vs g(1) = 0 ≠ f₃(2) = 0 vs g(2) = 1 ≠ In general: g(i−1) = 1 − fᵢ(i−1) ⇒ g and fᵢ differ at column i−1. One disagreement is enough — so g ≠ fᵢ for every i. In the widget below: Build next row = panel 1, Flip the diagonal = panel 3. The diagonal cells (panel 2) light up automatically as you build each row.
Three moves: assume someone gives us the supposedly complete list (panel 1); look at the diagonal cells fᵢ(i−1) (panel 2); flip every diagonal bit to define g = 1 − fᵢ₊₁(i) (panel 3). The resulting g differs from each fᵢ at exactly position i − 1, so g cannot be any row in the list.

Why is this enough to prove that the set of functions ℕ → {0,1} is bigger than ℕ? Because "can be listed" is exactly the meaning of countable. If no list can contain every such function, the set is uncountable. Drive the three moves interactively below — and on the next slides we will replay the same trick on Turing machines to prove ATM undecidable.

Drive the proof yourself

🔊 Widget map
How the widget mirrors the proof
  • Build next row — adds the next row fi to the table. Repeated clicks build up the supposedly-complete list (panel 1 of the visual above). The diagonal cell of each new row is shaded gold automatically.
  • Flip the diagonal — once all rows are in, this fills the bottom row g by flipping every diagonal cell (panel 3 of the visual). Watch the contradiction emerge: at column i − 1, g differs from row i.
  • Reset / Size — wipe the table and choose a different table dimension.
Cantor's diagonal — flip the diagonal, escape the list Widget 1
Step 0
Click Build next row to fill in one row at a time. Each row fi is a function ℕ → {0,1}, and column j shows fi(j). Once all rows are filled, click Flip the diagonal to construct a function g that cannot be in the list.
🔊 Diagonal lemma
The diagonal lemma. If you list any countable family of functions f1, f2, … from ℕ to {0,1}, you can construct a new function g(n) = 1 - fn(n) that disagrees with each fi at position i. So g is not in the list. Conclusion: no countable list can contain every function ℕ → {0,1}.

The trick — and we will reuse it three times in this module — is to refuse to be captured by any list. You give me a list; I look down the diagonal and build something that contradicts every row, exactly at its own index. That single move is the entire technology of diagonalization. The next slides will turn the rows from "functions" into "Turing machines", and the punchline will be that ATM is undecidable.

🎧 Narration

2 · ATM is Turing-recognizable

Let ATM = { ⟨M, w⟩ : M is a Turing machine that accepts string w }. This is the "universal acceptance problem" — given a TM and a string, does the TM accept?

The good news first: ATM is at least recognizable. Build a universal TM U that, on input ⟨M, w⟩, simulates M on w. If M halts and accepts, U accepts. If M halts and rejects, U rejects. If M runs forever, U runs forever too.

🔊 Reminder
Reminder — recognizable vs decidable
  • Recognizable (= Turing-recognizable = r.e.): there is a TM that accepts every string in the language, and on strings outside the language either rejects or loops.
  • Decidable: there is a TM that always halts, and accepts iff the input is in the language.

Decidable ⊆ Recognizable. The gap between them — the strings that loop — is exactly where undecidability hides.

The universal TM, in action

Below is a small interpreter for a tiny TM language. Type a TM description and an input string; the simulator is exactly the algorithm that puts ATM in Turing-recognizable. (Try the "loops forever" preset and watch the universal TM never stop.)

Universal TM U · simulates any M on any w using a 3-region tape U's tape (single tape, three logical regions): q₀ , 0 → q₁ , 0 , R ; q₁ , 0 → q₀ , 0 , R ; … ⟨M⟩ · transition table (read-only) # 0 0 0 0 _ _ # M's state: q₁ head position: cell 1 M's head M's simulated tape (initially w, evolves under M's δ) One step of the simulation: U does this in a loop ① Read M's state from work region e.g., q₁ ② Read symbol at M's head pos e.g., 0 ③ Look up δ in ⟨M⟩ scan transition table → (q₀, 0, R) ④ Apply write 0, move R, state ← q₀ repeat until M reaches qaccept or qreject — or loop forever
The universal TM U lays out three regions on its single tape: M's transition table (loaded from ⟨M⟩), M's simulated tape (initially w), and a small work area tracking M's current state and head position. The 4-step cycle below is U's main loop — read state, read symbol, look up δ in the program region, apply the transition. U is one fixed machine that runs every other machine.
🔊 Widget walkthrough

What the widget does: a universal Turing machine simulates any other TM you give it as a program. The transitions you write below ARE the TM M; the universal TM U interprets them step by step, just like an interpreter for a programming language.

How ATM gets its "recognizable" stamp: on input ⟨M, w⟩, U just simulates M on w. If M accepts, U accepts. If M rejects, U rejects. If M loops, U also loops. So U is a recognizer for ATM (accepts iff the input is in ATM) — but it cannot guarantee halting, so it's not a decider.

Try the three presets via the dropdown. The loops forever preset is illustrative: load it, hit Run, and the simulator caps at 200 steps with no halt — exactly the behavior that makes ATM recognizable but not decidable.

Universal TM — simulator for ATM Widget 2

✎ Editable: write your TM here, one transition per line

Each line is one transition rule, in this exact format:

current_state, symbol_read → next_state, symbol_to_write, L or R

Read in plain English: "If I am in current_state and the head reads symbol_read, then go to next_state, overwrite that cell with symbol_to_write, and move the head Left or Right."

Special conventions:

  • _ (underscore) represents a blank tape cell.
  • q0 is the start state (always); other states are q1, q2, … (you choose).
  • qa is the accept state; qr is the reject state. The machine halts when it enters either.
  • Whitespace and the arrow style (-> or →) are flexible.

Worked example. The rule q0, 0 -> q1, 0, R means: from q0, if reading 0, switch to q1, keep the 0 there (write 0 back), then move Right. The rule q0, _ -> qa, _, R means: from q0, if reading blank (end of input), accept.

✎ TM description (edit me)

Tip: pick a preset and click Load to populate this box with example rules, then tweak them.

Tape

State q0
Steps 0
Verdict running…
Loaded
Click Step to apply one transition.

The simulator just is the proof. There is no separate TM to imagine — this is the universal TM, witnessing that ATM is in the recognizable class.

🎧 Narration

3 · ATM is not decidable — the contradiction machine

The contradiction machine D · feeds itself its own description ⟨M⟩ D · on input ⟨M⟩ H(⟨M, ⟨M⟩⟩) does M accept its own ⟨M⟩? output the opposite accept ↦ reject · reject ↦ accept ✓ / ✗ Now run D on ⟨D⟩. By definition, D outputs the opposite of D(⟨D⟩). D contradicts itself ⇒ H cannot exist ⇒ ATM is undecidable.
D is built from H by composition: ask H whether M accepts its own description, then output the opposite. When D is fed its own description, D's answer must equal its own opposite — impossible. The hypothetical decider H cannot exist.

Suppose, for contradiction, that there is a TM H that decides ATM:

H(⟨M, w⟩) = accept  if M accepts w;    reject  otherwise.

From H we will build a contradiction. Define a new machine D that takes as input a TM description ⟨M⟩:

D(⟨M⟩):   run H(⟨M, ⟨M⟩⟩);   if H accepts, reject;   if H rejects, accept.

D exists because H exists, and "flip the answer" is something we know how to do. Now ask: what does D(⟨D⟩) do?

Both cases lead to contradiction, so the assumption that H exists is impossible. There is no decider for ATM. ∎

Walk Sipser's contradiction step by step

Sipser's argument (Theorem 4.11): assume a decider H for ATM exists. Build a new TM D from H:

D on input ⟨M⟩:
  1. Run H on ⟨M, ⟨M⟩⟩.
  2. Output the opposite of H's answer — accept iff H rejects.

The widget below is Sipser's Figure 4.20: rows are TMs, columns are TM descriptions, and the cell at (i, j) is what Mi does on ⟨Mj⟩. The bottom row D is the flipped diagonal — it disagrees with each Mi at column i. Click Walk diagonal to fill that bottom row one column at a time.

ATM diagonalization — Sipser's Figure 4.20 walkthrough Widget 3

A = accepts, R = rejects (or loops — both look the same from outside). The diagonal (green) is highlighted because it's what each TM does on its own description. Walk diagonal inspects one diagonal cell per click and fills in the corresponding D cell as its flip.

Setup
The table shows what each Mi does on each input ⟨Mj⟩. The diagonal — cell (i, i) — is what Mi does on its own description. D is built to disagree with every diagonal cell.
🔊 Why diagonal
Why the diagonal cell matters

D only disagrees with every Mi at the diagonal position. That is enough — if a TM D in the list has index k, then D disagrees with Mk at column k, but D = Mk, so it disagrees with itself, which is impossible. The diagonal is not decoration; it is exactly where the self-reference creates the contradiction.

🎧 Narration

4 · The halting problem & reductions to it

The same idea kills the halting problem: HALTTM = { ⟨M, w⟩ : M halts on input w }. Instead of redoing diagonalization, we use a reduction: we show that if we could decide HALTTM, we could decide ATM — which we just proved we can't.

🔊 Reduction
Reduction from ATM to HALTTM

Suppose R decides HALTTM. Build a decider S for ATM:

  1. On input ⟨M, w⟩: run R on ⟨M, w⟩.
  2. If R rejects, then M doesn't halt, so M doesn't accept w. Reject.
  3. If R accepts, simulate M on w directly — it is guaranteed to halt, so we can read off the verdict.

So a hypothetical R gives us S, deciding ATM. But that's impossible. Hence HALTTM is undecidable too. ∎

Reduction ATM ≤ HALTTM · build a decider S using a hypothetical R Input tape of S: ⟨M⟩ # w — S is asked: "does M accept w?" S · the hypothetical decider for ATM ① Call R(⟨M, w⟩) R is the assumed HALTTM decider "does M halt on w?" R always halts (by assumption) R: no (loops) S rejects ⟨M, w⟩ M loops ⇒ M doesn't accept R: yes (M halts) ② Run U(⟨M, w⟩) directly w₀ w₁ w₂ _ …M's tape Guaranteed to halt (R told us so) — accept iff M accepts. S accepts iff M accepts direct simulation gives the answer S would decide ATM — but ATM is undecidable. So R cannot exist ⇒ HALTTM is undecidable.
If a decider R for HALTTM existed, we could build a decider S for ATM as follows: ① ask R whether M halts on w; if R says no, M loops and cannot accept, so S rejects; ② if R says yes, we know it's safe to directly simulate M on w (it will halt), and S accepts iff the simulation accepts. S is a decider for ATM — which is impossible, so R cannot exist.

Try it: build a reduction chain interactively

Below: three target problems we want to prove undecidable (HALTTM, ETM, REGULARTM). For each one, drag the reduction template into place to construct the formal reduction. The widget checks the construction is well-formed.

Reduction builder — ATM ≤ X Widget 4
Reduction template
Pick a target, then drag the pieces into the green slots to assemble a TM M' whose behavior translates the original ⟨M, w⟩ question into the target's question.
🎧 Narration

5 · The map of languages — decidable, recognizable, neither

By the end of this lecture you have four official regions on the map:

RegionDefinitionExample
DecidableSome TM always halts and answers correctly.ADFA, EDFA, all finite languages.
Recognizable \ DecidableSome TM accepts iff in language, but may loop otherwise.ATM, HALTTM.
co-Recognizable \ DecidableComplement is in Recognizable \ Decidable.ATM, HALTTM.
NeitherNot even recognizable; the complement isn't either.EQTM (we'll show this later).
🔊 Bridge theorem
The bridge theorem. A language L is decidable iff both L and its complement L are Turing-recognizable. So a language sits in "neither" iff at least one of L, L is non-recognizable.
The four regions of language classification All languages over Σ* Recognizable co-Recognizable Decidable ADFA · ECFG ATM HALTTM co-ATM co-HALTTM Neither recognizable nor co-recognizable EQTM Bridge theorem: L is decidable ⇔ both L and its complement L̅ are recognizable.
The four regions on one map: decidable (in both ovals); recognizable but not decidable (left only, e.g. ATM); co-recognizable but not decidable (right only, e.g. ¬ATM); and neither (outside both, e.g. EQTM).

The widget below lets you place a language in the Venn diagram and check whether your classification matches the proof. Hover over a language to see why it lives where it lives.

Language classification quiz Widget 5

Languages to classify (drag into a region or click to assign)

How to play
Click a language pill, then click the region of the Venn diagram you think it belongs to. When you've placed them all, click Check answers.
🎧 Narration

6 · Practice (Sipser Ch. 4.2 & 5.1)

Sipser 4.18

Let T = {⟨M⟩ : M is a TM that accepts wR whenever it accepts w}. Show that T is undecidable.

Show hint
Reduction from ATM. Given ⟨M, w⟩, build a new TM M' whose language is "special" iff M accepts w.
Show solution outline
Given ⟨M, w⟩: build M' that on input x: (a) if x = 01, accept; (b) if x = 10, simulate M on w and accept iff it accepts; (c) otherwise reject. Then L(M') contains 01 but contains 10 = (01)R iff M accepts w. So ⟨M'⟩ ∈ T iff M accepts w.
Sipser 5.9

Let T = {⟨M⟩ : M is a TM that accepts wR whenever it accepts w} (same problem). Show T is not Turing-recognizable.

Show hint
It suffices to show T is not co-recognizable, i.e., that T is not recognizable. Try a reduction from ATM.
Show solution outline
Reduce ATM to T. Given ⟨M, w⟩, build M': on input x, if x = 01 simulate M on w and accept iff it rejects (impossible to do directly — needs co-recognizability!) ... use a more refined "search" technique that exhausts the input space. The standard solution constructs M' so that L(M') equals \{01\} if M doesn't accept w and equals \{01, 10\} otherwise — leveraging the recognizable property gives a recognizer for ATM, contradicting its non-recognizability.
Sipser 5.10

Consider the problem of determining whether a TM M on input w ever attempts to move its head left when its head is on the leftmost tape cell. Formulate and prove this problem is undecidable.

Show hint
Define LEFTTM = {⟨M, w⟩ : M attempts to move left from the leftmost cell while running on w}. Reduce from ATM or its complement; modify M to trigger a left-move at the leftmost cell exactly when it would accept.
Show solution outline
Given ⟨M, w⟩, build M' that simulates M on w on a portion of tape starting from cell 2 onward. If M accepts, M' moves its head to cell 1 and then tries to move left — triggering the LEFT condition. Then ⟨M', w⟩ ∈ LEFTTM iff M accepts w.
Sipser 5.13

A two-headed finite automaton (2DFA) is a deterministic finite automaton with two read-only heads that move independently on a read-only input tape (with end-markers). Show that A2DFA is decidable but E2DFA is undecidable.

Show hint
A 2DFA can be simulated by a TM with linearly bounded tape — leading to a configuration-graph argument for membership. For emptiness, reduce from ATM by encoding TM computations as 2DFA paths.
Show solution outline
Membership decidable: the number of (state, head1-pos, head2-pos) configurations on a fixed input of length n is |Q| · (n+2)2, finite. Build the config graph and check reachability from start to an accept config. Emptiness undecidable: given a TM M and input w, encode the sequence of M's configurations on w as a string; build a 2DFA that verifies a candidate string is exactly such a computation history ending in accept — non-empty iff M accepts w.
Sipser 5.22

Show that ATM is not mapping reducible to ETM. In other words, show that no computable function reduces ATM to ETM.

Show hint
If ATM ≤_m ETM then ATM ≤_m ETM. Since ETM is recognizable, that would make ATM recognizable — but we proved it isn't.
Show solution outline
Mapping reductions transfer recognizability along their direction: if L1 ≤m L2 and L2 is recognizable, so is L1. Same for complements. So ATM ≤m ETM would imply ATM ≤m ETM (just complement both sides), and since ETM is recognizable (loop over inputs w, simulate M in parallel; accept as soon as one accepts), ATM would be recognizable. But it isn't (Module 5 of Sipser).
Sipser 5.28

Use the recursion theorem informally to show that any TM M can effectively be modified to a TM M' that has access to its own description ⟨M'⟩.

Show hint
This is the recursion theorem itself — see Module 3. Build M' by combining M with a self-printer.
Show solution outline
See Module 3, §3 on the recursion theorem. Briefly: there is a computable function q that maps any TM description ⟨P⟩ to a TM description ⟨P'⟩ that begins by writing ⟨P'⟩ on its tape, then runs P. Apply q to M.
Sipser 5.30

Use Rice's theorem (which we'll prove in Module 3) to prove that REGULARTM, the language of TM descriptions whose language is regular, is undecidable.

Show hint
Rice's theorem: every nontrivial property of the recognizable language of a TM is undecidable. Is "regular" nontrivial?
Show solution outline
"L(M) is regular" is a property of the language only (different TMs with the same language all share or don't share this property), it is nontrivial (some TMs have regular languages — e.g., one accepting a* — and some don't, e.g., one accepting {anbn}). By Rice's theorem, REGULARTM is undecidable.
🎧 Narration

One-sentence summary

🔊 Summary
A diagonal argument (or a reduction from one) shows that ATM, HALTTM, ETM, and many other natural TM properties are undecidable — and the gap between "decidable" and "Turing-recognizable" is exactly the looping behavior that prevents an algorithm from always returning an answer.

Next → Module 3: Reductions & the Recursion Theorem