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, proof-oriented 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.

Resources

Information, Problem Sets, and Study Materials

** Access requires MIT certificates.

Homework submission instructions. Upload a single file with all non-optional 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 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

Office Hours

Weeks when problem sets are due will be staffed by two TAs during office hours;
other weeks will be staffed by one TA.

Thanksgiving Week Extra Office Hours

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:

Recitation Notes

Notes are generally posted by the Monday following the Friday recitation.
  1. September 8 - Jett's notes
  2. September 15 - Sean's notes
  3. September 22 - No classes (student holiday)
  4. September 29 - Mark's notes
  5. October 6 - Jonathan's notes
  6. October 13 - Mark's notes
  7. October 20 - Fatima's notes
  8. October 27 - Yuxuan's notes
  9. November 3 - Vaishnavi's notes
  10. November 10 - No classes (Veterans Day)
  11. November 17 - Audrey's notes

Exam Schedule

Midterm exam: Thursday, October 26, 2:30 - 4pm, Walker (Building 50), top floor.
Final exam: Friday, December 22, 9am - Noon, DuPont Gym.

Student Support

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. They have a Dean on Call 24x7 at 617-253-1212. 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.

Course Schedule

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

2020 Lectures

Accessibility