18.404/6.5400 Fall 2026
Introduction to the Theory of Computation

Required background. To succeed in this course, you need experience and skill with basic combinatorics, probability, graph theory, and logical reasoning, as well as comfort with theorems and proofs. If you did well in 18.062, 18.200, or any other substantial, proof-oriented discrete mathematics subject, you should be fine.

The course moves quickly, covering about 90% of the textbook. The problem sets and exams require proving various statements, and creativity in finding proofs is necessary.

Resources

• Canvas, piazza, psetpartners, and gradescope, coming soon.
• Math Learning Center - free tutoring in math subjects, usually including 18.404
• Textbook - Introduction to the Theory of Computation, 3rd edition. It has an errata web site. You may use the 2nd edition but it is missing some additional practice problems, or the International Edition but it numbers some items differently.
• Slides and nearly all recorded lectures from 2020 are available below. 2026 lectures will not be recorded. The online videos are intended as a supplement to the in-person lectures, or as backup in case of illness, but not as a substitute. The midterm exam(s) will take place during regular lecture times. Makeup times are available only in case of illness. The videos may not track the in-person lectures. In particular, the in-person lecture may discuss this year's problem sets, and some different material.

Course Staff

• Lecturer: Michael Sipser, sipser@mit.edu
• Recitation TA: Isha Agarwal, agarwali@mit.edu
• Grading Coordinator TA: Alicia Lin, ayl27@mit.edu
• Recitation TA: Jiaxu Liu, jxl26@mit.edu
• Recitation TA: Max Lu, maxlu@mit.edu
• Grading Coordinator TA: Sarah Mokhtar, sarah04@mit.edu
• Recitation TA: Jacqueline Wang, wangyj05@mit.edu
• Recitation TA: Kimberly Wang, kwang26@mit.edu
• Grading Coordinator TA: Michael Sun, msun415@mit.edu
• Recitation TA: Pratyush Venkatakrishnan, psvenk@mit.edu
• Recitation TA: Raina Wu, rwu986@mit.edu

Tentative Lecture Schedule

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

2020 Lectures

• Slides
• Videos OCW, YouTube

Accessibility