MIT OpenCourseWare

Browse materialsMIT 18.404J · Fall 2020

Theory of Computation

Subject: Mathematics

Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain

Instructor: Prof. Michael Sipser
Term: Fall 2020
Level: Undergraduate, Graduate
What's inside: 25 videos · 6 problem sets · 3 exams · 1 solution · 1 lecture note · 1 reading · 75 other files · 5 web pages
Materials open: Videos here · files on MIT OCW

Start here

Start course: Lecture 1: Introduction, Finite Automata, Regular Expressions Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.404J Theory of Computation, Fall 2020, Prof. Michael Sipser — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Has MIT solutions 1 file in this course is named by MIT as solutions.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

This course’s cited books, in our reading lists: Introduction to the Theory of Computation

How this course was organized

What's here, and what isn't

MIT's own materials here did not support a verified, course-wide order, so they are grouped by section instead.

Not included here

7 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely. (7 items)

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

50 files

Assignments

Exams

Other materials from this course

25 video transcripts

4 images

MIT OpenCourseWare, Prof. Michael Sipser, 18.404J Theory of Computation, Fall 2020.

License: CC BY-NC-SA 4.0 · Edition: Fall 2020 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Theory of Computation

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Exams

Other materials from this course

Lecture 1: Introduction, Finite Automata, Regular Expressions

Lecture 2: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata

Lecture 3: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs

Lecture 4: Pushdown Automata, CFG ↔ PDA

Lecture 5: CF Pumping Lemma, Turing Machines

Lecture 6: TM Variants, Church-Turing Thesis

Lecture 7: Decision Problems for Automata and Grammars

Lecture 8: Undecidability

Lecture 9: Reducibility

Lecture 10: Computation History Method

Lecture 11: Recursion Theorem and Logic

Lecture 12: Time Complexity

Lecture 14: P and NP, SAT, Poly-Time Reducibility

Lecture 15: NP-Completeness

Lecture 16: Cook-Levin Theorem

Lecture 17: Space Complexity, PSPACE, Savitch's Theorem

Lecture 18: PSPACE-Completeness

Lecture 19: Games, Generalized Geography

Lecture 20: L and NL, NL = coNL

Lecture 21: Hierarchy Theorems

Lecture 22: Provably Intractable Problems, Oracles

Lecture 23: Probabilistic Computation, BPP

Lecture 24: Probabilistic Computation (cont.)

Lecture 25: Interactive Proof Systems, IP

Lecture 26: coNP ⊆ IP