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

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.

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

Course Staff

• Lecturer: Michael Sipser, sipser@mit.edu
• Recitation TA: Axel Adjei, asadjei@mit.edu
• Recitation TA: Isha Agarwal, agarwali@mit.edu
• Recitation TA: Jonathan Huang, jhuang25@mit.edu
• Recitation TA: Leo Gagnon, leognon@mit.edu
• Grading Coordinator TA: Addison Julistiono, aaron25@mit.edu
• Recitation TA: Max Lu, maxlu@mit.edu
• Grading Coordinator TA: Katherine Taylor, ketaylor@mit.edu
• Recitation TA: Pratyush Venkatakrishnan, psvenk@mit.edu
• Recitation TA: Leo Yao, leoy@mit.edu
• Recitation TA: Rachel Zhang, rachelyz@mit.edu

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, 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

Exam Schedule

Midterm exam: Thursday, October 15, 2:30 - 4pm, Walker (Building 50), top floor.
Final exam: During finals week. Time and location announced in the third week of the term.

2020 Lectures

• Slides
• Videos OCW, YouTube

Accessibility