18.404/6.5400 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.
Homework submission instructions.
Upload a single file with all non-optional problems to
Gradescope
by the due date.
Handwritten is ok as long as we can read it easily,
otherwise use latex.
When Gradescope prompts you, mark the pages containing each problem.
If you upload several files, the last upload file replaces all previous
files, so upload the complete set.
Do not upload individual problems separately.
Late homework submission.
At noon on the due date, the regular Gradescope assignment
for non-optional problems will close
and a new "late submission" assignment will appear.
You may submit any individual 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.
Upload only those non-optional problems you wish
to be counted as late, together in a single file.
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 -EVEN IF UNMARKED- will override earlier submissions
and will be subject to the late penalty.
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. Optional
problem parts may not be submitted separately for lateness consideration.
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.
- 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
- Mondays 3-5pm, 2-151, Leo G and Isha
- Monday 5-6pm,
Zoom
(MIT Certificate required), Mike
- Tuesdays 10-11am, 56-169, Jonathan and Rachel
- Tuesdays 11am-noon, 56-169, Leo Y and Rachel
- Tuesdays 4:15-5pm, 2-438 (or down the hall), Mike [if the 4th floor door is locked, use the elevator]
- Tuesdays 5-6pm, 2-103, Pratyush
- Wednesdays 10-11am, 2-146, Jonathan
- Wednesdays 11am-noon, 2-151, Pratyush and Leo Y
- Wednesdays 4-6pm, 2-151, Max and Axel
- 10:00am, 4-159, Jonathan
- 11:00am, 4-159, Rachel
- 12:00pm, 4-257, Leo G and Pratyush
- 1:00pm, 4-257, Axel
- 2:00pm, 4-145, Leo Y
- 3:00pm, 4-145, Isha and Max
- September 5
- Leo's notes
- September 12
September 19
- No classes (student holiday)
- September 26
- October 3
- October 10
- October 17
- October 24
- October 31
- November 7
- November 14
- November 21
- December 5
Notes are generally posted by the Tuesday following the Friday recitation.
-
9/4 Introduction, finite automata, regular expressions §1.1
-
9/9 Nondeterminism, closure properties, Reg Exprs → FA §1.2-1.3
-
9/11 Reg Exprs ← FA, Proving non-regularity via pumping lemma, CFGs §1.4-2.1
-
9/16 Context free languages, Pushdown Automata, CFG ⇆ PDA §2.2
-
9/18 Context-free pumping lemma, Turing machines §2.3,3.1 Pset 1 DUE (noon)
-
9/23 TM variants, Church-Turing thesis §3.2-3.3
-
9/25 Decision problems for automata and grammars §4.1
-
9/30 Undecidability §4.2
-
10/2 Reducibility §5.1,5.3 Pset 2 DUE (noon)
-
10/7 Computation history method §5.2
-
10/9 Recursion theorem, Logic §6.1-6.2
-
10/14 Time complexity §7.1 Pset 3 DUE (noon)
-
10/16 Midterm Exam (during regular lecture time, Walker)
-
10/21 P and NP, SAT, Poly-time reducibility §7.2-7.3
-
10/23 NP-completeness §7.5
-
10/28 Cook-Levin theorem §7.4
-
10/30 Space complexity, PSPACE §8.1-8.2
-
11/4 Savitch's theorem, PSPACE-completeness §8.3
-
11/6 Games, Generalized geography, L and NL §8.3-8.4 Pset 4 DUE (noon)
11/11 NO CLASS --- Veterans Day
-
11/13 NL-completeness, NL = coNL §8.4
-
11/18 Hierarchy theorems §9.1
-
11/20 Provably intractable problems, oracles §9.2 Pset 5 DUE (noon)
-
11/25 Probabilistic computation, BPP §10.2
11/27 NO CLASS --- Thanksgiving
-
12/2 An interesting language in BPP, Arithmetization §10.2
-
12/4 Interactive proof systems, IP §10.4 Pset 6 DUE (noon)
-
12/9 coNP ⊆ IP §10.4
- Midterm exam: Thursday, October 16, 2:30 - 4pm,
Walker (Building 50),
top floor.
- Final exam: During finals week. Time and location announced in the third week of the term.
Exams are closed book.
No book, notes, or laptop. A crib sheat will be allowed.
- If you are dealing with a personal or medical issue that
may affect your participation in any MIT class, please discuss it with
Student Support Services (S3)
at 617-253-4861.
Graduate students may contact
GradSupport.
We cannot excuse you from coursework without support from S3 or
GradSupport.
- If you may require disability accommodations,
please contact
Disability and Access Services early in the semester then let me know
so that we can work together to get your accommodation logistics in place.
For serious urgent matters at any time, every student
may contact the 24x7 Dean on Call at (617) 253-1212.
Accessibility