Module 3 · Computation-history method & Recursion theorem

🎧 Narration

🔊 Diagram

A decision tree for applying Rice's theorem. Only nontrivial properties that depend solely on the language L(M) — not on the syntactic description of M — are guaranteed undecidable.

1 · The computation history trick

🔊 Diagram

A computation history records every configuration of M on w, one row per time step. Local 2×3 windows of consecutive rows must follow the transition function. The accepting tableau exists iff M accepts w — this is what gadgets in L_BA and CFG reductions check.

🔊 Callout

Reading this picture — four common questions

1. Why does a single row mix the state and the tape contents?

Each row is a configuration: Sipser's compact snapshot of the whole machine at one moment. We write the tape contents in order, with the state symbol inserted at the head's position. So "0 q₁ 1 1 0" means: the tape reads 0 1 1 0 (left to right), the head is over the cell that holds the leftmost 1, and the machine's control is in state q₁. The state isn't literally written on the tape — it's a notational convention that lets one string encode the entire configuration.

2. Why does the state "move forwards" as time progresses?

In this example the head moves right at every step (column 0 → 1 → 2 → 3 → 4). Since the state symbol sits where the head sits, watching its column shift IS watching the head move. A TM transition δ(q, a) = (q', b, L/R) writes b in place of a and moves the head one cell left or right; in the next row, the state symbol appears one column over.

3. Why exactly a 2×3 window — not 3×4 or 3×2?

A 2×3 window is the smallest rectangle that fully determines whether a transition is legal:

2 rows — you need exactly two consecutive time steps to check a single transition: the "before" row and the "after" row. One row alone has nothing to compare against; three rows is overkill.
3 columns — the cell at position p in the next row can be affected only by positions p−1, p, p+1 in the previous row, because the head moves at most one cell. So the next row's middle cell is a function of the previous row's three-cell neighborhood.

3×4 would still work, but it's wasteful (12 cells per check instead of 6, and the extra row/column carry no information). 3×2 doesn't work: 2 columns can't capture the head's left + right neighborhood, so you can't tell whether a head now at position p came from p−1 or from p+1.

4. Why does that make 2×3 the indicator of validity?

Local-to-global. If every 2×3 window in the tableau is consistent with δ, then every transition between every pair of consecutive rows is legal — so the whole tableau is a valid computation. Conversely, one bad window kills validity. This is exactly the lever that Cook–Levin, E_LBA undecidability, and ALL_CFG undecidability all pull: encode "every 2×3 window obeys δ" as a finite set of constraints (SAT clauses / LBA states / CFG productions) and you've encoded "M accepts w."

A computation history of a TM M on input w is the complete sequence of configurations that M goes through:

🔊 Formula

C 1 # C 2 # C 3 # \dots # C_ℓ

where C₁ is the start configuration (state q₀, head at position 0, tape = w followed by blanks), C_i+1 follows from C_i by one application of δ, and C_ℓ is an accepting configuration (a configuration whose state is the accept state). The symbol # is just a separator.

🔊 Key idea

The trick. A string x is "an accepting computation history of M on w" iff a list of local properties holds: it is a sequence of configurations separated by #; each adjacent pair (C_i, C_i+1) agrees on the unchanged parts of the tape and differs only at the head position by one transition of δ; the first configuration is correct; and the last is accepting. Local properties can be checked by humble machines (DFAs, NFAs, LBAs, CFGs combined with intersection) — and that is the whole leverage.

See it visually

Below: pick a tiny TM and an input. The widget displays the full computation history as a table of configurations. Use this picture to keep in your head while reading the rest of the section.

🔊 Widget

Preset:

How to read each row.

q_i| — the state symbol sits just before the head's cell. The | is the visual delimiter between "what the head is in" and "what the head is reading"; it is NOT a tape symbol.
So 0q1|01 = tape contains 001 (three cells), state is q₁, head on cell index 1 (the second cell, which holds a 0). Counting characters in the string: 0 (cell 0) · q1| (head marker) · 0 (cell 1, head here) · 1 (cell 2). The q1| in the middle is bookkeeping, not tape content.
Where do the Xs come from? The TM itself writes them. The transition δ(q₀, 0) = (q₁, X, R) tells the machine "when in state q₀ reading a 0, overwrite that cell with X, switch to q₁, and move right." The X is a marker the machine uses to remember "this 0 has already been processed." Tape symbols are NOT just the input alphabet — the tape alphabet Γ may include working symbols like X and the blank _ that never appear in the input.
Why the head shuttles back and forth. Each round: mark the next un-marked 0 with X, walk right past existing 0s to the blank, write a fresh 0 there (so we've "shifted" one 0 to the right), walk back left until we hit the X, step over, and repeat. That's the "shuttle" pattern you see in the trace.

🔊 Trace explanation

Configuration format

Each row is one configuration: tape content with the current state inserted to the left of the head's position. So q0|00 means "tape contains 00, state is q0, head reads the leftmost 0." Reading down the column, every adjacent pair differs by one δ-step.

🎧 Narration

2 · Linear bounded automata (LBAs)

An LBA is a TM that is only allowed to use the cells originally occupied by its input. (Implementation detail: we mark the end cells with special symbols and the LBA may not overwrite them.) This is a meaningful restriction — LBAs are strictly weaker than general TMs — but is enough to recognize the context-sensitive languages.

🔊 Diagram

An LBA is a Turing machine whose tape is exactly as long as the input — visualized by the end markers ⊢ and ⊣ that the head may not cross. With only n cells available, the number of configurations is finite, so A_LBA = {⟨M, w⟩ : M is an LBA that accepts w} is decidable (Sipser Theorem 5.9). E_LBA remains undecidable — see the next slide.

Key fact: A_LBA is decidable

Membership in an LBA's language can be tested: even though a TM on an input of length n might have infinitely many configurations, an LBA on the same input has only finitely many. So if the LBA runs long enough without halting, it must repeat a configuration, and then it will repeat forever.

🔊 Callout

Counting LBA configurations

An LBA with |Q| states, tape alphabet |Γ|, and input length n has at most |Q| · n · |Γ|ⁿ distinct configurations. (State, head-position, and tape contents — bounded.) So A_LBA is decidable by simulating for that many steps and accepting if we hit an accept state; if we time out, reject.

This is a delicate result. The decider does halt — but it might run for an astronomically long time. In Module 6 we'll see that A_LBA is PSPACE-complete: decidable in polynomial space, but not known to be in P.

🎧 Narration

3 · E_LBA is undecidable

Now the punchline. E_LBA = {⟨B⟩ : B is an LBA and L(B) = ∅} is undecidable. The proof uses computation histories.

🔊 Reminder

Reminder · what does A_TM (or "co-A_TM") mean?

The bar over a language name, or the prefix co-, denotes the complement: the set of strings not in the language. So A_TM = {⟨M, w⟩ : M is a TM that does NOT accept w}. We met this in Module 2 · slide 5 as a canonical example of a co-recognizable but undecidable language. Writing A_TM ≤_m E_LBA means "given ⟨M, w⟩ we build an LBA whose language is empty iff M accepts w" — equivalently A_TM ≤_m E_LBA. Either form gives undecidability of E_LBA.

🔊 Callout

The reduction A_TM ≤_m E_LBA

Given ⟨M, w⟩, build an LBA B_M,w whose language is the set of accepting computation histories of M on w. Then L(B_M,w) ≠ ∅ iff M accepts w.

Why is B_M,w an LBA? Because checking that a string x is a valid accepting history of M on w can be done by going through x and verifying local properties — start configuration is right, each step is legal, end is accepting. The LBA can do this in space proportional to its input (the history itself).

🔊 Diagram

The LBA B_M,w hardcodes the TM M and the string w. On any input x, it performs three local checks (start, transition, accept) on x interpreted as a sequence of configurations C₁ # … # C_ℓ. Because each check is local, the LBA never needs more tape than |x|. Therefore L(B_M,w) is non-empty exactly when an accepting history of M on w exists — i.e., when M accepts w. A decider for E_LBA would let us decide A_TM, which is impossible.

🔊 Direction note

Wait — isn't this proof actually about E_LBA (non-emptiness)?

Yes — and that's fine. Look at the punchline of the figure: L(B_M,w) ≠ ∅ ⇔ M accepts w. Read literally, this says M accepts w iff ⟨B_M,w⟩ ∈ E_LBA (i.e., the LBA's language is non-empty). So the function ⟨M, w⟩ ↦ ⟨B_M,w⟩ is a many-one reduction A_TM ≤_m E_LBA, not A_TM ≤_m E_LBA.

Why does this still prove E_LBA undecidable? Because decidability is closed under complement: a language L is decidable iff L is decidable (just flip the decider's output). So E_LBA undecidable and E_LBA undecidable are the same statement. We can use either as the target of the reduction.

Equivalently: A_TM ≤_m E_LBA is the same as A_TM ≤_m E_LBA (apply the bar to both sides — mapping reductions are symmetric in that sense). And since A_TM is undecidable (Module 2 · slide 5), E_LBA is undecidable. The "output the opposite" trick below is just this complement-flip made concrete in code.

So if we had a decider for E_LBA, we could decide A_TM: given ⟨M, w⟩, build B_M,w, test whether L(B_M,w) = ∅; output the opposite (this is the complement-flip — it turns a decider for emptiness into a decider for non-emptiness). Since A_TM is undecidable, so is E_LBA.

🔊 Widget

Drag the assertions onto the appropriate side: things B_M,w needs to check vs. things outside its job description. Click Check to grade.

The LBA's job

B_M,w takes a candidate computation history as input and decides whether it is a valid accepting history of M on w. It does not simulate M itself; it only checks that what's on the tape is a valid trace.

🎧 Narration

4 · ALL_CFG is undecidable

Recall A_CFG and E_CFG were decidable (Module 1). Their inequality cousin EQ_CFG = {⟨G, H⟩ : L(G) = L(H)} is undecidable, and so is the simpler-looking ALL_CFG = {⟨G⟩ : L(G) = Σ*}.

🔊 Reminder

Reminder · the "co-" / overline notation

The bar in A_TM (also written co-A_TM) means the complement of the language — every string that is NOT in A_TM. So A_TM = {⟨M, w⟩ : M is a TM that does NOT accept w}. We introduced this in Module 2 · slide 5 as a canonical example of a co-recognizable but undecidable language. In this slide we'll write the reduction as A_TM ≤_m ALL_CFG — meaning "given ⟨M, w⟩ we build a CFG whose language is NOT all of Σ* iff M accepts w." This is equivalent to A_TM ≤_m ALL_CFG; either form proves ALL_CFG undecidable because both A_TM and its complement are undecidable.

The proof again uses computation histories, with a twist. We reduce A_TM to ALL_CFG. Given ⟨M, w⟩, we build a CFG G_M,w that generates everything except the accepting histories of M on w.

🔊 Diagram

The CFG G_M,w generates every string EXCEPT valid accepting histories of M on w. It does this by three nondeterministic branches, each detecting one kind of local violation: wrong start, wrong transition (the trick is writing odd-indexed configs in reverse so a CFG can match them position-by-position), or non-accepting end. So L(G_M,w) = Σ* exactly when there is no accepting history, i.e., M does not accept w. A decider for ALL_CFG would decide A_TM (Sipser Theorem 5.13).

🔊 Direction note

Same question as slide 3 — isn't this proof actually about ALL_CFG?

Yes, exactly the same pattern as E_LBA. The figure footer literally states A_TM ≤_m ALL_CFG. Read off the punchline: L(G_M,w) = Σ* ⇔ M does NOT accept w. So ⟨G_M,w⟩ ∈ ALL_CFG ⇔ M does not accept w, which means ⟨G_M,w⟩ ∈ ALL_CFG ⇔ M accepts w. The mapping ⟨M, w⟩ ↦ ⟨G_M,w⟩ is a reduction A_TM ≤_m ALL_CFG, not A_TM ≤_m ALL_CFG.

Why this still proves ALL_CFG undecidable. Decidability is closed under complement: L decidable iff L decidable. So ALL_CFG undecidable and ALL_CFG undecidable are the same statement.

Equivalent way of saying it: A_TM ≤_m ALL_CFG ≡ A_TM ≤_m ALL_CFG (bar both sides). Since A_TM is undecidable (Module 2 · slide 5), ALL_CFG is undecidable too.

🔊 Key idea

The twist. "Is a valid accepting history" is checkable by an LBA but not by a CFG (because checking that C_i+1 faithfully follows from C_i needs matching them position by position, which requires an unbounded memory). But "is not a valid accepting history" can be done by a CFG, because to fail it is enough to find one local violation, and a CFG can guess where the violation is and verify it locally.

So L(G_M,w) = Σ* iff no accepting history exists iff M does not accept w. A decider for ALL_CFG would decide A_TM, so it can't exist.

Note also: EQ_CFG is undecidable as a corollary, since ALL_CFG = {⟨G⟩ : L(G) = Σ*} = {⟨G⟩ : L(G) = L(G_Σ*)} reduces to EQ_CFG.

🎧 Narration

5 · The recursion theorem: programs that print themselves

Switching gears completely. The recursion theorem is a beautiful, weird result — and once you've seen it, several proofs we'll do later (Rice's theorem, the incompleteness theorem in Module 7) become much cleaner.

🔊 Callout

Recursion theorem (informal)

For any TM T that takes two inputs ⟨M, w⟩, there is a TM R such that on any input w, the computation of R(w) equals T(⟨R⟩, w). In plain English: any TM can effectively obtain its own description and use it as data.

🔊 Friendly read

Wait, what does that even mean? — a friendlier read

Read the statement in two steps.

Step 1 · You give me a "template" T. T is just a 2-argument program. Slot #1 is "a TM's source code"; slot #2 is "some input string." You can write whatever you want inside T — for instance:

T(⟨M⟩, w) = "print ⟨M⟩ and halt." (T just echoes its first argument.)
T(⟨M⟩, w) = "simulate M on w and accept iff M rejects."
T(⟨M⟩, w) = "count states of M, accept iff that number divides |w|."

Step 2 · The theorem hands you back R. The recursion theorem promises: I can compile your T into a one-argument TM R whose runtime behavior is exactly "plug my own source code into slot #1 of T, plug the input into slot #2, and do whatever T does." Two worked applications of this idea — the quine and a slick proof that A_TM is undecidable — appear in the "Two applications" callout further down.

Why is this called "recursion"? The relationship R(w) = T(⟨R⟩, w) doesn't look like programming-recursion at first glance — it looks like R is calling T, not R itself. The trick is realising that T is the body of the recursive function, and slot 1 of T is where the recursive call lives: when the theorem hands you back R with ⟨R⟩ already plugged into slot 1, the text "simulate ⟨M⟩" inside T's body becomes "simulate ⟨R⟩" — and that's R calling itself. The Sipser construction below shows how R obtains its own description without reading it from anywhere.

🔊 Diagram

The construction. T is built as T = A · B. The "front" part A is a tiny constant printer whose only job is to dump ⟨B⟩ on the tape and halt. The "back" part B then reads ⟨B⟩, mechanically reconstructs ⟨A⟩ from it (there's a uniform recipe for "TM that prints any fixed string s"), concatenates them to get ⟨A·B⟩ = ⟨T⟩, and now has T's own description available as data. With ⟨T⟩ in hand, T can do anything that depends on its own source — print it (quine), feed it to a hypothetical decider and flip the answer (A_TM undecidability proof), and so on.

🔊 Examples

Two examples to anchor the idea

Example 1 · the quine. Pick T(⟨M⟩, w) = "print ⟨M⟩ and halt" — T just echoes whatever's in slot 1. Plug T into the recursion theorem. You get back R with the behavior R(w) = T(⟨R⟩, w) = "print ⟨R⟩ and halt". So R is a TM that prints its own source code — a quine. The recursion theorem says quines always exist in any Turing-complete language. (We just built one in the widget above.)

Example 2 · slick A_TM undecidability. Suppose for contradiction that some TM D decides A_TM. Pick T(⟨M⟩, w) = "run D on ⟨M, w⟩; accept iff D rejects". The recursion theorem gives R with R(w) = T(⟨R⟩, w) = "run D on ⟨R, w⟩; accept iff D rejects". But now: R accepts w iff D says R does NOT accept w — direct contradiction, so D can't exist. The recursion theorem lets us skip the awkward self-reference dance of the original diagonal proof.

Build a quine, step by step

🔊 Widget

Below is a minimal self-printer in pseudo-language. Press Run to watch it execute; the output box should reproduce the source exactly.

Source code

Output (after running)

How to use this widget

1. The left pane shows the source of a tiny JavaScript quine.

2. The right pane is empty — click ▶ Run to execute the program.

3. The program will print(…) some text into the right pane. If it's a real quine, the right pane will end up showing the exact same text as the left pane.

4. Press Compare source vs output to verify they match byte-for-byte.

Idea: S is a string containing the program text with a placeholder; the code prints S with the placeholder replaced by a quoted copy of S itself. Because the printer's behavior is captured in S, the output matches the source.

🎧 Narration

6 · Rice's theorem

Rice's theorem is a meta-result that swallows half of the "undecidability of natural properties" results in one stroke.

🔊 Diagram

Rice's theorem proof in pictures (Sipser §6.3, Theorem 6.10). Three panels: ① Because P is nontrivial, two specific witness TMs exist — T_yes (whose language has P) and T_no (whose language doesn't; we pick "reject everything" so L(T_no) = ∅). They get fixed once and never change. ② For any ⟨M, w⟩ we build a new TM M_M,w that gates T_yes behind the question "does M accept w?": if yes, M_M,w behaves like T_yes (so its language equals L(T_yes), which has P); if no, M_M,w just rejects everything (so its language is ∅, the same as T_no's, which lacks P). ③ Running the assumed P-decider R on ⟨M_M,w⟩ therefore answers "does M accept w?" — which would decide A_TM. Impossible, so R doesn't exist.

🔊 Callout

Rice's theorem

Let P be any property of recognizable languages such that (a) P is nontrivial (some recognizable language has it, some doesn't), and (b) P depends only on L(M), not on the particular TM M. Then the language L_P = {⟨M⟩ : L(M) has property P} is undecidable.

Examples killed by Rice's theorem in one shot: "L(M) is empty", "L(M) is regular", "L(M) is decidable", "L(M) contains the empty string", "L(M) is finite", "L(M) = {0, 1}", and so on. All undecidable, immediately, by one application of Rice's theorem.

Predict-the-property quiz

🔊 Widget

How to use: for each property below, click either Rice applies or Doesn't apply. The selected button will turn coloured. When you've answered all 8, click Grade my answers. You can also Reveal answers at any time to skip ahead.

0 / 8 answered

How to play

For each property, decide whether Rice's theorem applies (yes/no). Remember the two requirements: nontrivial (some recognizable languages have it, others don't), and semantic (depends only on L(M), not on the structure of M).

🎧 Narration

7 · Practice (Sipser §5.1, §6.1, §6.3)

Sipser 5.3

Find a match in the following instance of the Post Correspondence Problem (or show none exists): { (ab, abab), (b, a), (aba, b), (aa, a) }.

Show hint

PCP allows reuse and any order. Try short combinations and look for accumulating mismatches that can be repaired.

Show solution outline

Try domino sequences starting with (ab, abab) — top reads ab, bottom abab, top is a prefix of bottom. Append (aba, b): top abaaba, bottom ababb — mismatch at position 3 (a vs b). Try (b, a) next instead: top abb, bottom ababa — mismatch. Continue exploring; the answer here is that a match exists with specific tiles. (The general PCP is undecidable; for small instances, BFS over partial matches works.)

Sipser 5.11

Consider EQ_CFG = {⟨G_1, G_2⟩ : L(G_1) = L(G_2)}. Show that EQ_CFG is undecidable.

Show hint

Use the fact that ALL_CFG is undecidable (from this module). Find a "fixed" grammar that generates Σ*.

Show solution outline

Let G_* be a fixed CFG with L(G_*) = Σ* (easy to build: S → aS | bS | ε). Then on input ⟨G⟩, output ⟨G, G_*⟩. This is a mapping reduction ALL_CFG ≤_m EQ_CFG: ⟨G⟩ ∈ ALL_CFG iff L(G) = Σ* = L(G_*) iff ⟨G, G_*⟩ ∈ EQ_CFG.

Sipser 5.16

Let A_LBA be the language of LBAs and inputs they accept. Show A_LBA is decidable. Then show E_LBA is undecidable.

Show hint

For A_LBA: bound the number of configurations and detect repetitions. For E_LBA: reduce from A_TM using computation histories.

Show solution outline

A_LBA decidable: on input ⟨B, w⟩ with |w| = n, simulate B for up to |Q| · n · |Γ|ⁿ steps; accept iff an accept config is hit. If we exceed the bound without accepting, reject (any longer run would repeat). E_LBA undecidable: given ⟨M, w⟩, construct LBA B_M,w recognizing accepting computation histories of M on w. Then L(B_M,w) ≠ ∅ iff M accepts w. So a decider for E_LBA would decide A_TM.

Sipser 6.1

Give an example of a TM that has access to its own description and uses it to make a decision (formalize via the recursion theorem).

Show hint

The simplest example: a TM that prints its own description, then halts.

Show solution outline

Define T(⟨P⟩, w) to be "write ⟨P⟩ on the tape, halt." By recursion theorem, there exists R with R(w) = T(⟨R⟩, w), i.e., R writes ⟨R⟩ on its tape and halts. R is a quine.

Sipser 6.5

Let A = {⟨M⟩ : M is a TM that accepts ⟨M⟩}. Show that A is recognizable but not decidable.

Show hint

Recognizable by simulation. For undecidability: use diagonalization or reduce from A_TM.

Show solution outline

Recognizable: on input ⟨M⟩, simulate M on ⟨M⟩; accept iff it accepts. Undecidable: suppose D decides A. Build M via recursion theorem: on any input, get ⟨M⟩, run D(⟨M⟩), accept iff it rejects, reject iff it accepts. Then M accepts ⟨M⟩ iff ⟨M⟩ ∉ A iff M doesn't accept ⟨M⟩ — contradiction.

Sipser 6.7

Prove that, if A is Turing-recognizable and A ≤_m A, then A is decidable.

Show hint

Mapping reducibility preserves recognizability. If A ≤_m A and A is recognizable, then A is recognizable too.

Show solution outline

From A ≤_m A and recognizability of A: the reduction f witnesses A recognizable by composing the recognizer of A with f. Wait — we need to recognize A: on input x, compute f(x), then run the recognizer of A; x ∈ A iff f(x) ∈ A. So A is recognizable; combined with A recognizable, by the bridge theorem A is decidable.

🎧 Narration

One-sentence summary

🔊 Key idea

Computation histories let humble models (LBAs, CFGs combined with intersection) "verify" TM computations, transferring undecidability from A_TM to E_LBA, ALL_CFG, and many others; and the recursion theorem lets any TM behave as if it had its own description on tape — a tool that proves Rice's theorem in a few lines.

Next → Module 4: Time complexity & P

1 · The computation history trick

Reading this picture — four common questions

See it visually

2 · Linear bounded automata (LBAs)

Key fact: ALBA is decidable

Counting LBA configurations

3 · ELBA is undecidable

Reminder · what does ATM (or "co-ATM") mean?

The reduction ATM ≤_m ELBA

Wait — isn't this proof actually about ELBA (non-emptiness)?

4 · ALLCFG is undecidable

Reminder · the "co-" / overline notation

Same question as slide 3 — isn't this proof actually about ALLCFG?

5 · The recursion theorem: programs that print themselves

Recursion theorem (informal)

Wait, what does that even mean? — a friendlier read

Two examples to anchor the idea

Build a quine, step by step

Source code

Output (after running)

6 · Rice's theorem

Rice's theorem

Predict-the-property quiz

7 · Practice (Sipser §5.1, §6.1, §6.3)

One-sentence summary

Key fact: A_LBA is decidable

3 · E_LBA is undecidable

Reminder · what does A_TM (or "co-A_TM") mean?

The reduction A_TM ≤_m E_LBA

Wait — isn't this proof actually about E_LBA (non-emptiness)?

4 · ALL_CFG is undecidable

Same question as slide 3 — isn't this proof actually about ALL_CFG?