18.404/6.5400 Upcoming Fall 2025
Introduction to the Theory of Computation

NOTE: 2025 lectures will not be recorded.
Slides and nearly all recorded lectures from 2020 are available, see below.

Lecture Schedule

  1. 9/4  Introduction, finite automata, regular expressions §1.1
  2. 9/9  Nondeterminism, closure properties, Reg Exprs → FA §1.2-1.3
  3. 9/11  Reg Exprs ← FA, Proving non-regularity via pumping lemma, CFGs §1.4-2.1
  4. 9/16  Context free languages, Pushdown Automata, CFG ⇆ PDA §2.2
  5. 9/18  Context-free pumping lemma, Turing machines §2.3,3.1 Pset 1 DUE (noon)
  6. 9/23  TM variants, Church-Turing thesis §3.2-3.3
  7. 9/25  Decision problems for automata and grammars §4.1
  8. 9/30  Undecidability §4.2
  9. 10/2  Reducibility §5.1,5.3 Pset 2 DUE (noon)
  10. 10/7  Computation history method §5.2
  11. 10/9  Recursion theorem, Logic §6.1-6.2
  12. 10/14  Time complexity §7.1 Pset 3 DUE (noon)
  13. 10/16  Midterm Exam (during regular lecture time, probably in Walker)
  14. 10/21  P and NP, SAT, Poly-time reducibility §7.2-7.3
  15. 10/23  NP-completeness §7.5
  16. 10/28  Cook-Levin theorem §7.4
  17. 10/30  Space complexity, PSPACE §8.1-8.2
  18. 11/4  Savitch's theorem, PSPACE-completeness §8.3
  19. 11/6  Games, Generalized geography, L and NL §8.3-8.4 Pset 4 DUE (noon)
    11/11  NO CLASS --- Veterans Day
  20. 11/13  NL-completeness, NL = coNL §8.4
  21. 11/18  Hierarchy theorems §9.1
  22. 11/20  Provably intractable problems, oracles §9.2 Pset 5 DUE (noon)
  23. 11/25  Probabilistic computation, BPP §10.2
    11/27  NO CLASS --- Thanksgiving
  24. 12/2  An interesting language in BPP, Arithmetization §10.2
  25. 12/4  Interactive proof systems, IP §10.4 Pset 6 DUE (noon)
  26. 12/9  coNP ⊆ IP §10.4

Required background. To succeed in this course, you need experience and skill with mathematical concepts, theorems, and proofs. If you did reasonably well in 18.062, 18.200, or any other substantial, proof-oriented mathematics subject, you should be fine. The course moves quickly, covering about 90% of the textbook. The problem sets generally require proving some statement, and creativity in finding proofs will be necessary.

2020 Lectures

Accessibility