Learn · MIT OpenCourseWare

A man in front of a black screen with text and images.

Course18.404J / 18.4041J,6.840J25 lectures32 h 19 min

Theory of Computation

Prof. Michael Sipser · Massachusetts Institute of Technology

Start with lecture 1 At MIT OpenCourseWare

About

This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

Lectures

Video Lectures

  1. Lecture 1: Introduction, Finite Automata, Regular Expressions 1 h 1 min · Video
  2. Lecture 2: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata 1 h 4 min · Video
  3. Lecture 3: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs 1 h 11 min · Video
  4. Lecture 4: Pushdown Automata, CFG ↔ PDA 1 h 10 min · Video
  5. Lecture 5: CF Pumping Lemma, Turing Machines 1 h 14 min · Video
  6. Lecture 6: TM Variants, Church-Turing Thesis 1 h 15 min · Video
  7. Lecture 7: Decision Problems for Automata and Grammars 1 h 17 min · Video
  8. Lecture 8: Undecidability 1 h 18 min · Video
  9. Lecture 9: Reducibility 1 h 17 min · Video
  10. Lecture 10: Computation History Method 1 h 22 min · Video
  11. Lecture 11: Recursion Theorem and Logic 1 h 18 min · Video
  12. Lecture 12: Time Complexity 1 h 26 min · Video
  13. Lecture 14: P and NP, SAT, Poly-Time Reducibility 1 h 20 min · Video
  14. Lecture 15: NP-Completeness 1 h 26 min · Video
  15. Lecture 16: Cook-Levin Theorem 1 h 19 min · Video
  16. Lecture 17: Space Complexity, PSPACE, Savitch's Theorem 1 h 21 min · Video
  17. Lecture 18: PSPACE-Completeness 1 h 18 min · Video
  18. Lecture 19: Games, Generalized Geography 1 h 20 min · Video
  19. Lecture 20: L and NL, NL = coNL 1 h 21 min · Video
  20. Lecture 21: Hierarchy Theorems 1 h 22 min · Video
  21. Lecture 22: Provably Intractable Problems, Oracles 1 h 23 min · Video
  22. Lecture 23: Probabilistic Computation, BPP 1 h 24 min · Video
  23. Lecture 24: Probabilistic Computation (cont.) 1 h 24 min · Video
  24. Lecture 25: Interactive Proof Systems, IP 1 h 15 min · Video
  25. Lecture 26: coNP ⊆ IP 1 h 24 min · Video

Syllabus and materials

At MIT OpenCourseWare, as the course publishes them.

Credits and licence

Institution
Massachusetts Institute of Technology
Department
Mathematics; Electrical Engineering and Computer Science
Teacher
Prof. Michael Sipser
Term
Fall 2020
Level
Undergraduate
Language
English
Subjects
Mathematics, Computer science, Engineering
Source
MIT OpenCourseWare
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only. MIT OpenCourseWare's terms
Attribution
Prof. Michael Sipser. Theory of Computation. Fall 2020. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
MIT OpenCourseWare gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed