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

• Piazza - discussion forum
• Pset Partners - for finding study groups
• Gradescope - log in to Canvas first if you have trouble accessing Gradescope
• Canvas - not used for any course content
• Math Learning Center - free tutoring in many math subjects
• 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 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.

Information, Problem Sets, and Study Materials

• Course Information Guide - Policies for grading, collaboration, and AI.
• Problem Set 1

Late homework submission. You may submit any individual non-optional problems after the due date, before 11:59pm the following day, for a 1 point per problem late penalty deduction. In each pset, you may submit some problems or problem parts on time and others late. (The penalty will be 10% of the part's point value.) At Noon on the due date, the regular Gradescope assignment will close and a new "late submission" assignment will appear. Please upload only those problems you wish to be counted as late. You may resubmit problems you submitted previously if you wish to change your answer, but these will be marked late and get the 1 point penalty. DO NOT RESUBMIT UNCHANGED PROBLEMS you submitted previously. The late submissions will override earlier submissions. Note: We cannot accept unexcused (see "Student Support" below) homework after the late submission deadline.

Optional problem submission. Submit the optional problems to a separate "optional problem" assignment. That assignment is configured to accept both on-time and late submissions. You will receive the usual 1 point penalty for a late optional problem.

Regrade requests. If you feel that your work was incorrectly graded, you may submit a regrade request through gradescope. Please review your graded papers promptly; regrade requests are accepted only for two weeks from the original pset due date. Please do not abuse the regrade system by making lots of frivolous requests; we have limited grader capacity.

If you need to communicate with us about the psets (e.g., medical extensions), email the grading team.

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

Office Hours

• Mondays 4-5pm, 2-147, Pratyush
• Mondays 4:30-5:30, 2-147, Lillian
• Mondays 5-6pm, 2-147, Isha
• Tuesdays 4:15-5pm, 2-438 (or down the hall), Mike
• Wednesdays 4-5pm, 2-147, Max and Raina
• Wednesdays 5-6pm, 2-147, Jacqueline and Jiaxu

Lectures and Recitation Sections

Lectures are held in room 34-101 on Tuesdays and Thursdays from 2:30 to 4pm.
The one-hour recitations meet Fridays at the following times and rooms:

• 10:00am, 4-159, Pratyush
• 11:00am, 4-159, Jiaxu
• 12:00pm, 4-257, Kimberly
• 1:00pm, 4-257, Isha and Jacqueline
• 2:00pm, 4-145, Max and Raina

Exams

• Quiz: Tuesday, October 6, 7:30 - 9pm, Walker (Building 50), top floor.
  
• Midterm: Thursday, October 29, 2:30 - 4pm, Walker (Building 50), top floor.
  
• Final: Three hours during finals week. Date and location announced in the third week of the term.
  

Course Schedule

1. 9/10  Introduction, finite automata, regular expressions §1.1
   9/11   Recitation 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
   9/18   Recitation 2
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)
   9/25   Recitation 3
6. 9/29  TM variants, Church-Turing thesis §3.2-3.3
7. 10/1  Decision problems for automata and grammars §4.1
   10/2   Recitation 4
8. 10/6  Undecidability §4.2 Evening Quiz (7:30-9pm, Walker)
9. 10/8  Reducibility §5.1,5.3
   10/9   Recitation 5
   10/13  NO CLASS --- Monday schedule Pset 2 DUE (noon)
10. 10/15  Computation history method §5.2
    10/16   Recitation 6
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)
    10/23   Recitation 7
13. 10/27  NP-completeness §7.5
14. 10/29  Midterm Exam (during regular lecture time, Walker)
    10/30   Recitation 8
15. 11/3  Cook-Levin theorem §7.4
16. 11/5  Space complexity, PSPACE §8.1-8.2 Pset 4 DUE (noon)
    11/6   Recitation 9
17. 11/10  Savitch's theorem, PSPACE-completeness §8.3
18. 11/12  Games, Generalized geography, L and NL §8.3-8.4
    11/13   Recitation 10
19. 11/17  NL-completeness, NL = coNL §8.4
20. 11/19  Hierarchy theorems §9.1 Pset 5 DUE (noon)
    11/20   Recitation 11
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)
    12/4   Recitation 12
24. 12/8  Interactive proof systems, IP §10.4
25. 12/10  coNP ⊆ IP §10.4

2020 Lectures

• Slides
• Videos OCW, YouTube

Accessibility