18.404/6.840 Fall 2020 Online
Introduction to the Theory of Computation

This year, lectures are offered live online via Zoom. The lectures will also be recorded for viewing at a later time to accomodate students who cannot participate in the live lectures due to time-zone differences or other reasons. Weekly TA-led recitations are offered online at various times on Fridays according to the registrar's schedule. MIT certificates are required.


Information and Homework Handouts

Homework submission instructions. Upload a single file with all problems to Gradescope, before the due date. When Gradescope prompts you, mark the pages containing each problem.

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 p-set, you may submit some problems on time and some late. 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.

Lecture schedule and slides

  1. PPT PDF (Sep 1) Introduction, finite automata, regular expressions §1.1
  2. PPT PDF (Sep 3) Nondeterminism, closure properties, FA → Reg Exprs §1.2–1.3
  3. PPT PDF (Sep 8) FA ← Reg Exprs, Regular pumping lemma, CFGs §1.4–2.1
  4. PPT PDF (Sep 10) Pushdown automata, CFG ↔ PDA §2.2
  5. PPT PDF (Sep 15) Context-free pumping lemma, Turing machines §2.3,3.1
  6. PPT PDF (Sep 17) TM variants, Church-Turing thesis §3.2–3.3
  7. PPT PDF (Sep 22) Decision problems for automata and grammars §4.1
  8. PPT PDF (Sep 24) Undecidability §4.2
  9. PPT PDF (Sep 29) Reducibility §5.1,5.3
  10. PPT PDF (Oct 1) Computation history method §5.2
  11. PPT PDF (Oct 6) Recursion theorem, logic §6.1–6.2
  12. PPT PDF (Oct 8) Time complexity §7.1
    (Oct 13) NO CLASS — Monday schedule due to Indigenous Peoples' Day
  13. (Oct 15) Midterm Exam
  14. PPT PDF (Oct 20) P and NP, SAT, poly-time reducibility §7.2–7.3
  15. PPT PDF (Oct 22) NP-completeness §7.5
  16. (draft) PPT PDF (Oct 27) Cook-Levin theorem §7.4
  17. (Oct 29) Space complexity, PSPACE, Savitch's theorem §8.1–8.2
  18. (Nov 3) PSPACE-completeness §8.3
  19. (Nov 5) Games, Generalized geography §8.3
  20. (Nov 10) L and NL, NL=coNL §8.4
  21. (Nov 12) Hierarchy theorems §9.1
  22. (Nov 17) Provably intractable problems, oracles §9.2
  23. (Nov 19) Probabilistic computation, BPP §10.2
    (Nov 24) NO CLASS — Thanksgiving week
    (Nov 26) NO CLASS — Thanksgiving week
  24. (Dec 1) An interesting language in BPP, Arithmetization §10.2
  25. (Dec 3) Interactive proof systems, IP §10.4
  26. (Dec 8) coNP ⊆ IP §10.4

Course Staff and Zoom Office Hours

Lectures and Recitation Sections

The live online lectures are on Tuesdays and Thursdays from 2:30 to 4:00.
The one-hour live online recitations meet Fridays at the following times.

Recitation Notes

  1. September 4 - Damian's notes
  2. September 11 - Damian's notes - Alex's notes
  3. September 18 - Damian's notes - Abbas's notes
  4. September 25 - Damian's notes - Fadi's notes
  5. October 2 - Alex's notes
  6. October 9 - Damian's notes - Abbas's notes
    October 16 - No recitations this week
  7. October 23 - Damian's notes

Other Information

Textbook: Introduction to the Theory of Computation, 3rd edition, Sipser, published by Cengage, 2013. It has an errata web site. You may use the 2nd edition, but it is missing some additional practice problems. You may use the International Edition, but it numbers a few of the problems differently.

Check-in Quizzes: Following student recommendations, we will de-emphasize (but not eliminate) the midterm and final exams by adding graded live check-in quizzes for credit during the lectures, to be conducted via Zoom's polling feature. The check-in quizzes (aka check-ins) are listed under the Quizzes tab in Canvas. For students viewing a recorded lecture, an alternate timed and graded recorded check-in quiz will be available but it must be completed within 46 hours of the original live lecture. You may may chose whether to take the live check-in or the recorded check-in, but you must take one or the other to receive credit. The live check-ins won't be graded for correctness. You will receive full credit for submitting any answer, correct or not. The recorded check-ins will be graded for correctness but you may take these as many times as you like before the closing time. If you take one or more recorded check-ins, the last grade will override previous live or recorded check-in grades.

Required background: To succeed in this class, you need a good facility with mathematical concepts, theorems, and proofs. If you did reasonably well in 6.042, 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.

Exam Schedule

Midterm exam: Thursday, October 15, 2020, 90 minutes, start time flexible.
Final exam: Thursday, December 17, 2020, 3 hours, start time flexible.

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 5pm-9am weekdays and 24 hours on weekends at 617-253-1212 or 100 from campus phones. We cannot excuse you from coursework without support from S3.

If you may require disability accommodations, please speak early in the semester with Associate Dean Kathleen Monagle at 617-253-1473 and then let me know so that we can work together to get your accommodation logistics in place.