18.404/6.5400 (formerly 6.840) Fall 2022
Introduction to the Theory of Computation
Subject Evaluation
Please take a few minutes to
evaluate our 18.404/6.5400 class.
The deadline is Friday, December 16 at 9am.
If you've attended some recitations or office hours,
your TAs (see below for names)
would especially appreciate comments on their teaching.
We read all comments about how to improve the course.
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 problems to
Gradescope
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 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. (Note the change in policy, now allowing late problem
parts. The penalty will be 10% of the part's point value.)
At 2:30pm 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.
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.
 Lecturer:
Michael Sipser, sipser@mit.edu
 Head TA: Zhezheng Luo, ezzluo@mit.edu
 Head TA: Rene Reyes, rdreyes@mit.edu
 TA: Lara Booth, lcbooth@mit.edu
 TA: Jason Chen, jchez@mit.edu
 TA: Haimoshri Das, haimo@mit.edu
 TA: MingYang Deng, dengm@mit.edu
 TA: Jocelin Su, jocelin@mit.edu
 TA: Jett Wang, jett@mit.edu
 Mondays 24pm, 38166, Jocelin
 Mondays 46pm, 36144, Jett
 Mondays 56pm,
Zoom
(MIT Certificate required), Mike
 Tuesdays 11amnoon,
Zoom
(MIT Certificate required), Lara
 Tuesdays 4:155pm, 2438 (or down the hall), Mike
 Tuesdays 57pm, 36112, MingYang
 Wednesdays 24pm, 26142, Jason and Rene
 Fridays 45pm, 36112, Lara
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, 2135, Lara
 11:00am, 2135, Jason
 12:00pm, 2147, Jocelin
 1:00pm, 2147, Rene
 2:00pm, 2139, Jett
 3:00pm, 2139, MingYang
 September 9
 Jett's notes
 September 16
 Jocelin's notes
 September 23
 Jocelin's notes
 September 30
 Jason's notes
 October 7
 Lara's notes
 October 14
 Jett's notes
 October 21
 Jason's notes
 October 28
 MingYang's notes
 November 4
 Rene's notes
 November 18
 Lara's notes
Midterm exam: Thursday, October 27, 2:30  4pm,
Walker (Building 50),
top floor.
Final exam: Tuesday, December 20, 1:30  4:30,
Johnson Track.
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/8 Introduction, finite automata, regular expressions §1.1

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

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

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

9/22 Contextfree pumping lemma, Turing machines §2.3,3.1 Pset 1 DUE

9/27 TM variants, ChurchTuring thesis §3.23.3

9/29 Decision problems for automata and grammars §4.1

10/4 Undecidability §4.2

10/6 Reducibility §5.1,5.3 Pset 2 DUE
10/11 NO CLASS  Student Holiday

10/13 Computation history method §5.2

10/18 Recursion theorem, Logic §6.16.2

10/20 Time complexity §7.1 Pset 3 DUE

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

10/27 Midterm Exam

11/1 NPcompleteness §7.5

11/3 CookLevin theorem §7.4

11/8 Space complexity, PSPACE §8.18.2

11/10 Savitch's theorem, PSPACEcompleteness §8.3 Pset 4 DUE

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

11/17 NLcompleteness, NL = coNL §8.4

11/22 Hierarchy theorems §9.1
11/24 NO CLASS  Thanksgiving

11/29 Provably intractable problems, oracles §9.2 Pset 5 DUE

12/1 Probabilistic computation, BPP §10.2

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

12/8 Interactive proof systems, IP §10.4 Pset 6 DUE

12/13 coNP ⊆ IP §10.4
Accessibility