18.404/6.5400 Fall 2023
Introduction to the Theory of Computation
Required background. To succeed in this class, 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, prooforiented mathematics class, you should be fine. The class moves quickly, covering about 90% of the textbook. The homework assignments generally require proving some statement, and creativity in finding proofs will be necessary.
** Access requires MIT certificates.
Homework submission instructions.
Upload a single file with all nonoptional problems to
Gradescope (will be set up by Thursday 9/14)
before 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 overrides all previous
uploads, so do not upload individual problems separately.
Late homework submission.
You may submit any individual nonoptional 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 ontime 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.
 Lecturer:
Michael Sipser, sipser@mit.edu
 Head Grading Coordinator TA: Freya Edholm, fe2o3@mit.edu
 Head Recitation TA: Jett Wang, jett@mit.edu
 Recitation TA: Fatima Abbasi, fabbasi@mit.edu
 Recitation TA: Vaishnavi Addala, vaddala9@mit.edu
 Recitation TA: Sean Cheng, scheng12@mit.edu
 Grading Coordinator TA: Della Hendrickson, della@mit.edu
 Recitation TA: Jonathan Huang, jhuang25@mit.edu
 Recitation TA: Mark Jabbour, mjabbour@mit.edu
 Grading Coordinator TA: Jeffery Li, jeli@mit.edu
 Recitation TA: Samuel Tenka, samtenka@mit.edu
 Recitation TA: Audrey Xie, ahx@mit.edu
 Recitation TA: Yuxuan Zheng, yuxuanz@mit.edu
 Mondays 23pm, 2361, Yuxuan
 Mondays 34pm, 2361, Fatima and Yuxuan
 Mondays 45pm, 4153, Audrey and Fatima
 Mondays 56pm,
Zoom
(MIT Certificate required), Mike
 Tuesdays 4:155pm, 2438 (or down the hall), Mike
 Tuesdays 79pm, 26204, Vaishnavi and Jett
 Wednesdays 11noon, 8205, Jonathan and Jeffery [Except Nov 15 in 4163]
 Wednesdays 45pm, 26204, Audrey and Mark
 Wednesdays 56pm, 26204, Jonathan and Mark
 Wednesdays 67pm, 2135, Freya and Sam
 Wednesdays 78pm, 2135, Sean and Sam
 Wednesdays 89pm, 2135, Sean and Jett
Weeks when problem sets are due will be staffed by two TAs during office
hours;
other weeks will be staffed by one TA.
Lectures are held in room 34101 on Tuesdays and Thursdays from 2:30 to 4pm.
The onehour recitations meet Fridays at the following times and rooms:
 10:00am, 4261, Vaishnavi and Jonathan
 11:00am, 4261, Mark
 12:00pm, 4257, Jett
 1:00pm, 4257, Fatima and Yuxuan
 2:00pm, 4145, Sean and Audrey
 3:00pm, 4145, Sam
Notes are generally posted by the Monday following the Friday recitation.
 September 8
 Jett's notes
 September 15
 Sean's notes
 September 22
 No classes (student holiday)
 September 29
 Mark's notes
 October 6
 Jonathan's notes
 October 13
 Mark's notes
 October 20
 Fatima's notes
 October 27
 Yuxuan's notes
 November 3
 Vaishnavi's notes
 November 10
 No classes (Veterans Day)
 November 17
 Audrey's notes
Midterm exam: Thursday, October 26, 2:30  4pm,
Walker (Building 50),
top floor.
Final exam: Friday, December 22, 9am  Noon,
DuPont Gym.
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 6172534861. They have a Dean on Call 24x7 at 6172531212.
Graduate students may contact
GradSupport.
We cannot excuse you from coursework without support from S3 or
GradSupport.
If you may require disability accommodations,
please speak early in the semester with
Associate Dean Kathleen Monagle then let me know so that we can
work together to get your accommodation logistics in place.

9/7 Introduction, finite automata, regular expressions §1.1

9/12 Nondeterminism, closure properties, Reg Exprs → FA §1.21.3

9/14 Reg Exprs ← FA, Proving nonregularity via pumping lemma, CFGs §1.42.1

9/19 Context free languages, Pushdown Automata, CFG ⇆ PDA §2.2

9/21 Contextfree pumping lemma, Turing machines §2.3,3.1 Pset 1 DUE (noon)

9/26 TM variants, ChurchTuring thesis §3.23.3

9/28 Decision problems for automata and grammars §4.1

10/3 Undecidability §4.2

10/5 Reducibility §5.1,5.3 Pset 2 DUE (noon)
10/10 NO CLASS  Student Holiday

10/12 Computation history method §5.2

10/17 Recursion theorem, Logic §6.16.2

10/19 Time complexity §7.1 Pset 3 DUE (noon)

10/24 P and NP, SAT, Polytime reducibility §7.27.3

10/26 Midterm Exam

10/31 NPcompleteness §7.5

11/2 CookLevin theorem §7.4

11/7 Space complexity, PSPACE §8.18.2

11/9 Savitch's theorem, PSPACEcompleteness §8.3 Pset 4 DUE (noon)

11/14 Games, Generalized geography, L and NL §8.38.4

11/16 NLcompleteness, NL = coNL §8.4

11/21 Hierarchy theorems §9.1
11/23 NO CLASS  Thanksgiving

11/28 Provably intractable problems, oracles §9.2 Pset 5 DUE (noon)

11/30 Probabilistic computation, BPP §10.2

12/5 An interesting language in BPP, Arithmetization §10.2

12/7 Interactive proof systems, IP §10.4 Pset 6 DUE (noon)

12/12 coNP ⊆ IP §10.4
Accessibility