# Theory of Computation

- 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](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/)
- Licence: [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) (Non-commercial use only.)
- Syllabus: [at the source](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/pages/syllabus/)
- Readings: [at the source](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/pages/readings/)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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

1. [Lecture 1: Introduction, Finite Automata, Regular Expressions](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/9e790fe6a679), 1 h 1 min (Video)
2. [Lecture 2: Nondeterminism, Closure Properties, Regular Expressions → Finite Automata](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/0ea832149382), 1 h 4 min (Video)
3. [Lecture 3: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/4fb84ca282e7), 1 h 11 min (Video)
4. [Lecture 4: Pushdown Automata, CFG ↔ PDA](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/066f6ce80901), 1 h 10 min (Video)
5. [Lecture 5: CF Pumping Lemma, Turing Machines](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/313cf9f27e07), 1 h 14 min (Video)
6. [Lecture 6: TM Variants, Church-Turing Thesis](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/0f2e2918a5d6), 1 h 15 min (Video)
7. [Lecture 7: Decision Problems for Automata and Grammars](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/38d301946058), 1 h 17 min (Video)
8. [Lecture 8: Undecidability](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/ba884a477c28), 1 h 18 min (Video)
9. [Lecture 9: Reducibility](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/27cef7d73d6e), 1 h 17 min (Video)
10. [Lecture 10: Computation History Method](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/45c1ed30d6ef), 1 h 22 min (Video)
11. [Lecture 11: Recursion Theorem and Logic](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/a1e4ff0c0b9b), 1 h 18 min (Video)
12. [Lecture 12: Time Complexity](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/6a5d40936d33), 1 h 26 min (Video)
13. [Lecture 14: P and NP, SAT, Poly-Time Reducibility](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/da3f0bc7d4d9), 1 h 20 min (Video)
14. [Lecture 15: NP-Completeness](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/2241cc041a56), 1 h 26 min (Video)
15. [Lecture 16: Cook-Levin Theorem](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/49d547b63a85), 1 h 19 min (Video)
16. [Lecture 17: Space Complexity, PSPACE, Savitch's Theorem](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/f864f469c1ab), 1 h 21 min (Video)
17. [Lecture 18: PSPACE-Completeness](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/8541ce0ff700), 1 h 18 min (Video)
18. [Lecture 19: Games, Generalized Geography](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/3d9d9b12f726), 1 h 20 min (Video)
19. [Lecture 20: L and NL, NL = coNL](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/e11a8d41b5fc), 1 h 21 min (Video)
20. [Lecture 21: Hierarchy Theorems](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/3f3556ed1717), 1 h 22 min (Video)
21. [Lecture 22: Provably Intractable Problems, Oracles](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/5b432688d741), 1 h 23 min (Video)
22. [Lecture 23: Probabilistic Computation, BPP](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/4c5a100ea98f), 1 h 24 min (Video)
23. [Lecture 24: Probabilistic Computation (cont.)](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/d6a63a1938a5), 1 h 24 min (Video)
24. [Lecture 25: Interactive Proof Systems, IP](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/9c35fe1509a6), 1 h 15 min (Video)
25. [Lecture 26: coNP ⊆ IP](https://invisiblenetwork.ai/learn/mit/18-404j-theory-of-computation-fall-2020/b019b32f02ab), 1 h 24 min (Video)