What can be computed, and how fast? From finite automata to the halting problem to BQP — the complexity class where quantum computers live.
The question of whether machines can think is about as relevant as whether submarines can swim.— Edsger Dijkstra
Computation theory is the ladder you climb twice. Once upward — from machines so simple they cannot count, to machines so powerful they cannot know themselves. And once inward — because every rung is a theorem about limits: what a finite memory can never recognize, what no algorithm can ever decide, what no efficient procedure can plausibly solve. Fourteen weeks, nine chapters of Sipser, one quantum coda. By the end, the halting problem and Gödel's incompleteness will be, for you, the same theorem wearing two coats.
The clearest introduction ever written. Every proof is a small machine; read them the way you would read code. Read Ch. 4 in parallel with Gödel (Track 1) — the halting problem is incompleteness in disguise.
The bridge. Once Sipser gives you P, NP, and PSPACE, de Wolf shows you where BQP sits among them — and why nobody knows whether it swallows NP.
The smallest machines first: fixed memory, one pass over the input, no second chances. This chapter teaches the two moves that carry the entire course — simulation, to prove two machine models equal, and adversarial argument, to prove a machine cannot exist. Everything in weeks 3–14 is these two moves at larger scale.
A deterministic finite automaton is a five-tuple (Q, Σ, δ, q₀, F): finitely many states, exactly one transition per state and symbol, no tape, no memory beyond which state you are standing in. That poverty is the point — the DFA is the minimal formal model of "a machine," and the regular languages it recognizes are precisely what fixed memory can do. Every richer machine in this course is a DFA plus one resource: a stack (Chapter 2), a tape (Chapter 3).
A nondeterministic automaton is allowed to guess: several arrows per symbol, ε-moves, acceptance if some branch succeeds. The subset construction proves guessing buys no new languages — build a DFA whose states are sets of NFA states, tracking everywhere the NFA could possibly be. An n-state NFA thus becomes a DFA with at most 2ⁿ states, and that exponential is sometimes unavoidable: nondeterminism buys no power here, but it buys real succinctness. Remember this trade — it is your first resource/expressiveness trade-off, and the ghost of P vs NP.
Regular expressions are the algebraic face of the same class: patterns built from union, concatenation, and star. Regex → NFA is compositional (one gadget per operator); automaton → regex goes through generalized NFAs, ripping out states one at a time and writing every path through the deleted state onto the surviving arrows as a regular expression. The theorem says a declarative pattern language and an operational machine model coincide exactly — the first of the semester's great syntax–semantics coincidences, and a sibling of the completeness theorem you are proving in Logic.
Every regular language has a pumping length p — any member longer than p splits as xyz with |xy| ≤ p and y ≠ ε such that xyⁱz stays in the language for all i. To prove non-regularity, play it as a game: the demon claims L is regular and hands you p; you choose a string s ∈ L with |s| ≥ p; the demon cuts s = xyz under the constraints; you choose an i with xyⁱz ∉ L. If you can win against every legal cut, L is not regular. The game framing exists to keep the quantifiers straight — you never get to pick the cut, so your s must defeat all of them.
Call x and y distinguishable relative to L if some extension z sends exactly one of xz, yz into L. The theorem: L is regular iff this relation has finitely many equivalence classes — and the classes are, one for one, the states of the minimal DFA. This is the cleaner tool Sipser hides in the exercises: unlike the pumping lemma it is an exact characterization, so it never fails on a non-regular language, and when L is regular it hands you the state count for free.
Add one resource — a stack — and the machines learn to count matched pairs. Chapter 2 is grammar as machinery: the same language class described declaratively by rewriting rules and operationally by pushdown automata, then the second impossibility proof, because the stack has limits too.
A CFG generates strings by rewriting variables with production rules until only terminals remain; the record of the rewriting is a parse tree, and the tree — not the string — is the meaning. A grammar is ambiguous when one string admits two parse trees, which is fatal in a compiler and endlessly interesting in a natural language. Every programming language you have ever used is specified by a CFG; this section is why parsers exist.
Every CFG converts to a grammar whose rules are all A → BC or A → a. The prize is control: in CNF, every derivation of a length-n string takes exactly 2n − 1 steps, which is the length bound that powers both the CFL pumping lemma and the CYK parsing algorithm. The conversion itself is a pipeline — new start symbol, remove ε-rules, remove unit rules, split long rules — and each stage must be argued to preserve the language.
A PDA is an NFA holding an unbounded stack: push, pop, and guess. The equivalence with grammars runs in both directions — grammar → PDA simulates a leftmost derivation on the stack, expanding variables and matching terminals against the input; PDA → grammar builds variables Apq meaning "the machine can travel from state p to state q, ending with the stack as it started." Two utterly different descriptions, one class: the context-free languages.
Long strings in a CFL pump in two coordinated pieces: s = uvxyz with vy ≠ ε, |vxy| ≤ p, and uvⁱxyⁱz in the language for all i — because a tall parse tree must repeat a variable, and the subtree between the repeats can be spliced in or out. The demon game returns with a subtler cut. Then the casualties: {aⁿbⁿcⁿ} is not context-free because a stack compares two blocks, never three; {ww} is not, because a stack reverses — which is exactly why {wwR} is context-free. Keep {aⁿbⁿcⁿ}: it is your first sighting of the strict Chomsky hierarchy.
Here the course changes register. The Turing machine is the last machine — the one the Church–Turing thesis says is all machines — and within two chapters of meeting it you prove there are questions it can never answer. Read Chapter 4 with the Gödel weeks of the Logic track open beside it; they are the same story told twice.
A Turing machine is a finite control over an unbounded tape it can read, write, and move across in both directions. The right unit of analysis is not the state but the configuration — current state, tape contents, head position — because a computation is simply a sequence of configurations, each yielding the next by one application of δ. Hold that image: in week 10, Cook–Levin works by writing this exact sequence into a table and describing the table with a Boolean formula. Machines may accept, reject, or loop forever; a decider always halts, a recognizer merely accepts what it accepts.
Multitape machines, nondeterministic machines, enumerators — every enrichment collapses back to the one-tape model. Multitape → single-tape: concatenate the tapes with separators, mark virtual heads with dotted symbols, sweep to simulate one step (a quadratic slowdown). Nondeterministic → deterministic: breadth-first search of the computation tree (an exponential slowdown — remember that number; it is the germ of P vs NP). Robustness is the evidence file for the Church–Turing thesis: no reasonable extension changes what is computable, only how fast.
The thesis: the informal notion "algorithm" coincides exactly with "Turing machine." It is not a theorem and can never be one — one side of the equation is not a mathematical object. It is believed because every serious proposal for a model of computation (λ-calculus, recursive functions, your laptop, quantum circuits) computes precisely the same functions. It is also the load-bearing wall of this entire track: "A_TM is undecidable" means "no algorithm whatsoever decides it" only if the thesis holds. You are allowed to find that unsettling; Gödel did.
First the positive results: A_DFA, E_DFA, EQ_DFA, A_CFG are all decidable — small, honest algorithms about automata, each a warm-up in writing deciders as high-level descriptions. Then the pivotal object: the universal Turing machine U, a single machine that takes ⟨M, w⟩ and simulates M on w. Software, invented as a lemma in 1936. U is why A_TM is at least recognizable — simulate and accept if the simulation accepts — and it is the direct ancestor of the stored-program computer on your desk.
Suppose a decider H for A_TM exists. Build D: on input ⟨M⟩, run H on ⟨M, ⟨M⟩⟩ and do the opposite. Now run the self-reference table: rows are machines, columns are machine descriptions, entry (i, j) records whether Mᵢ accepts ⟨Mⱼ⟩. D is constructed to differ from row i at column i — it disagrees with every machine somewhere on the diagonal — yet D must itself be some row. At entry (D, ⟨D⟩) the definition demands D accept iff D doesn't. Contradiction; H cannot exist. This is Cantor's diagonal argument wearing machinery, and it is the exact skeleton of Gödel's sentence. The coda: A_TM is recognizable but its complement is not, so recognizable ≠ co-recognizable — the first asymmetry of the semester.
One impossibility becomes infinitely many. A reduction is a compiler from one problem into another, and it is the single most-used proof device in the rest of your mathematical life — here it spreads undecidability; in weeks 10–11 the same discipline, polynomial-time-bounded, spreads NP-completeness.
A ≤ₘ B means there is a computable function f with w ∈ A ⟺ f(w) ∈ B: membership questions about A translate mechanically into membership questions about B. Direction is everything. To prove B undecidable you reduce from a known-undecidable A to B — "if I could decide B, then via f I could decide A, which I cannot." Reduce the wrong way and you have proven nothing; half of all beginner reduction errors are direction errors, so state the direction in words before writing a single line of f. With this engine, HALT_TM, E_TM, and EQ_TM all fall — each by a small machine-building trick around A_TM. The Post correspondence problem (§5.2) then carries undecidability outside machine-land entirely, into dominoes.
One theorem to end a thousand questions: every nontrivial semantic property of the language of a Turing machine is undecidable. Does M accept a regular language? Accept the empty string? Accept anything at all? Undecidable, undecidable, undecidable — all instances of the same proof. "Semantic" means the property depends only on L(M), never on the machine's text; "nontrivial" means some machine has it and some machine lacks it. Both hypotheses are load-bearing: "M has at least 50 states" is syntactic and perfectly decidable. Rice is why perfect malware detection, complete dead-code elimination, and fully automatic program verification are impossible in general.
Machines may lawfully obtain their own descriptions: "compute ⟨self⟩" is a legitimate instruction, and the proof is a constructive two-part trick (the machine B that prints A followed by B). Its toy incarnation is the quine — a program that prints its own source. The theorem pays rent immediately: it gives a second, breathtakingly short proof that A_TM is undecidable (a decider would let a machine ask "do I accept this input?" and do the opposite), and it is the formal engine behind the diagonal lemma that manufactures the Gödel sentence in Track 1.
Suppose arithmetic had a sound, complete, effectively axiomatized theory. Then you could decide A_TM by brute proof-search: "M accepts w" is expressible as an arithmetic sentence, so enumerate all proofs — by completeness, a proof of the sentence or of its negation must eventually appear, and soundness guarantees the verdict is true. That is a decider for A_TM, which cannot exist. Therefore no such theory exists: some true sentence of arithmetic is unprovable. This is Gödel's first incompleteness theorem, derived in one paragraph from Turing — while in the Logic track you build the original 1931 route through Gödel numbering and the diagonal lemma. Two coats, one theorem; when you can narrate both and say precisely where each hypothesis is spent, you own the deepest result you will meet this year.
From "can it be computed at all" to "can it be computed before the sun dies." Chapter 7 defines the two most famous classes in mathematics and proves the theorem — Cook–Levin — that turns P vs NP into a question about one concrete problem. Chapter 8 replays the whole story with space instead of time, where nondeterminism turns out, astonishingly, to be nearly free.
P is the class of languages decidable in polynomial time — the robust, model-independent formalization of "feasible." NP has two definitions, and you need both fluently: (1) the verifier definition — L ∈ NP iff some polynomial-time verifier accepts ⟨w, c⟩ for some short certificate c exactly when w ∈ L; (2) the decider definition — L is decided by a nondeterministic polynomial-time TM. They are equivalent because a certificate is nothing but a transcript of the nondeterministic choices, and an NTM can guess a certificate branch by branch. So NP does not mean "not polynomial"; it means verifiable — and P vs NP asks whether finding a solution can be harder than checking one.
SAT is NP-complete: every NP computation compiles into one Boolean formula. The strategy: an accepting computation of an nᵏ-time NTM on w is an nᵏ × nᵏ tableau — one configuration per row, each row yielding the next. Variables xi,j,s assert "cell (i, j) holds symbol s," and four formula families pin the tableau down: φcell (each cell holds exactly one symbol), φstart (row one is the start configuration on w), φaccept (an accept state appears somewhere), and φmove (every 2×3 window of adjacent cells is consistent with the transition function). The deep trick is that legality is local: a global computation is certified by checking polynomially many constant-size windows, so the formula stays polynomial-size and is satisfiable iff M accepts w. This is the crown of the track — hence the two-part write-up in weeks 10–11.
Once one NP-complete problem exists, thousands follow by polynomial-time reduction — always from the known-complete problem, the same direction discipline as week 7. Each classic reduction is a gadget with a signature: 3SAT → CLIQUE turns clauses into triples of nodes wired to every non-contradictory neighbor; CLIQUE → VERTEX-COVER is the complement flip (k-clique in G ⟺ (n−k)-cover in Ḡ); 3SAT → SUBSET-SUM engineers decimal digits so that no column can carry, making arithmetic simulate logic. Learn them as gadget patterns, not as texts to memorize — the gadget is the idea.
coNP is the class of complements of NP languages: TAUTOLOGY, UNSAT, "this graph has no clique of size k." Where NP has short certificates for yes, coNP has short certificates for no — and nobody knows whether the two coincide. P sits inside NP ∩ coNP; NP = coNP would mean every tautology has a short proof, which almost no one believes; and NP ≠ coNP would imply P ≠ NP. This one definition sharpens everything you think about proof length.
Space is reusable; time is not — that single asymmetry drives the whole chapter. Savitch's theorem: NSPACE(s(n)) ⊆ SPACE(s(n)²) — nondeterminism, which seems to cost exponential time to remove, costs only a squaring of space. The trick is the recursive middle-configuration procedure CANYIELD(c₁, c₂, t): can c₁ reach c₂ within t steps? Try every candidate middle configuration cm and recurse on both halves with t/2 — the two recursive calls reuse the same space. Recursion depth log t = O(s(n)), each stack frame stores one configuration of size O(s(n)): total O(s(n)²). Immediate corollary: NPSPACE = PSPACE, which is why nobody ever writes "NPSPACE."
TQBF asks whether a fully quantified Boolean formula ∀x∃y∀z… φ is true, and it is PSPACE-complete: quantifier alternation is exactly what polynomial space can express. Read the formula as a two-player game — the ∃-player chooses values to make φ true, the ∀-player chooses to wreck it; the sentence is true iff ∃ has a winning strategy. That is why PSPACE is the natural home of perfect-play questions (generalized geography, go on an n×n board). The hardness proof is Savitch's middle-configuration recursion in formula form, with the quantifiers introduced precisely to stop the formula from doubling at each level.
The finale proves that limits exist unconditionally — meaningfully more time really does decide strictly more — and then walks to the frontier, where BQP takes its seat among the classical classes. The honest answer to "do quantum computers break NP?" is: almost certainly not, and nobody can prove it.
Diagonalization returns, now with a budget: build a machine D that, on input ⟨M⟩10ᵐ, simulates M on that same input for f(n) steps and flips the answer. D runs in O(f(n)) but differs from every machine deciding in o(f(n)/log f(n)) time — the log factor is pure simulation overhead, the bookkeeping cost of one machine impersonating another. When the raw separation lands between awkward bounds, padding arguments stretch it to the classes you care about: pad the inputs with 0s until an exponential-time problem looks polynomial, and separations transfer upward. The unconditional prizes: P ⊊ EXPTIME and PSPACE ⊊ EXPSPACE — real, proven walls, in a field where almost every interesting wall is conjecture.
An oracle machine gets a magic subroutine for some language A. Baker, Gill and Solovay: there exist oracles A and B with PA = NPA and PB ≠ NPB. But diagonalization-style proofs relativize — they go through unchanged when both machines carry the same oracle — so no relativizing proof can settle P vs NP in either direction. This is the first of the great barrier theorems: a proof about the limits of proofs, telling you the hierarchy-theorem toolbox, mighty as it is, cannot climb this wall.
BPP is polynomial time with coin flips and error at most 1/3 on every input. The 1/3 is arbitrary because of amplification: run the machine k times, take the majority vote, and Chernoff bounds crush the error to 2−Ω(k) — so "probably correct" is as good as correct for every practical purpose. BPP is the honest formalization of "practically computable," and the modern consensus, driven by derandomization results, is that P = BPP: randomness likely buys convenience, never power. It also matters here as scaffolding — BQP's definition is BPP's with amplitudes in place of probabilities.
BQP: languages decided by uniform polynomial-size quantum circuits with error at most 1/3 — bounded-error quantum polynomial time, the class where quantum computers live. The containment BQP ⊆ PSPACE comes from a path-sum argument: the acceptance amplitude is a sum, over all computation paths through the circuit, of a product of polynomially many gate entries. Each path's contribution is computable in polynomial space, and you sum over paths one at a time, reusing the space — Savitch's lesson again. So P ⊆ BPP ⊆ BQP ⊆ PSPACE, and quantum computers cannot escape polynomial space. The sting: since P ⊆ BQP ⊆ PSPACE, proving P ≠ BQP would prove P ≠ PSPACE — even "quantum beats classical" is beyond every current technique.
Shor puts FACTORING in BQP — but factoring is not known to be NP-complete; it lives in NP ∩ coNP, exactly where an NP-complete problem cannot sit unless NP = coNP. Grover speeds up unstructured search only quadratically, and the BBBV lower bound proves that quadratic is optimal in the black-box model — no quantum brute-force miracle exists. The picture that emerges: quantum computers devour structured problems (period-finding, hidden subgroups) and merely dent brute force. Whether NP ⊆ BQP is open — like everything else worth asking here — but the black-box evidence says no: quantum computers almost certainly do not solve NP-complete problems efficiently, and you should be able to argue why.
Gödel ↔ Turing. Incompleteness is undecidability in disguise: the diagonal argument that kills the halting problem is the same argument behind the Gödel sentence. Weeks 4–8 here run in parallel with Logic Track 1.
Games ↔ Games. The strategy arguments you build for automata return as Ehrenfeucht–Fraïssé games in model theory (Track 4) — model comparison by adversarial play is one idea wearing many crowns.
BQP ↔ the Quantum track. The coda hands you the complexity-theoretic map that the quantum computing track fills in with actual algorithms — Shor, Grover, and the honest boundaries of the quantum advantage.