18.404/6.840 Fall 2020 Online
Introduction to the Theory of Computation

For the Fall 2020 semester, I taught Theory of Computation remotely and produced the lectures below. I am leaving them online as an ongoing resource. If you use them for your own teaching, you will need to make minor modifications to change dates and references to problem sets and exams. (Note, be careful modifying slides that contain equations because it sometimes breaks the animations due to an apparent bug in PowerPoint.)

If you (re-)post the original or modified versions of these slides, I ask that you credit the original source.

Michael Sipser

Lecture outline and slides

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