1. Introduction, Finite Automata, Regular Expressions
1:00:342. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
1:03:273. Regular Pumping Lemma, Conversion of FA to Regular Expressions
1:10:024. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
1:09:225. CF Pumping Lemma, Turing Machines
1:13:596. TM Variants, Church-Turing Thesis
1:14:497. Decision Problems for Automata and Grammars
1:16:518. Undecidability
1:17:02Lecture 9: Reducibility (18.404J)
1:16:37Lecture 10: Computation History Method (18.404J)
1:21:41Lecture 11: Recursion Theorem and Logic (18.404J)
1:17:32Lecture 12: Time Complexity (18.404J)
1:25:37Lecture 14: P and NP, SAT, Poly-Time Reducibility (18.404J)
1:19:23Lecture 15: NP-Completeness (18.404J)
1:25:53Lecture 16: Cook-Levin Theorem (18.404J)
1:18:27Lecture 17: Space Complexity, PSPACE, Savitch's Theorem (18.404J)
1:20:10Lecture 18: PSPACE-Completeness (18.404J)
1:17:36Lecture 19: Games, Generalized Geography (18.404J)
1:19:38Lecture 20: L and NL, NL = coNL (18.404J)
1:20:06Lecture 21: Hierarchy Theorems (18.404J)
1:21:57Lecture 22: Provably Intractable Problems, Oracles (18.404J)
1:22:50Lecture 23: Probabilistic Computation, BPP (18.404J)
1:23:418. Undecidability
This lecture, part of MIT's advanced course in Theory of Computation, rigorously demonstrates the undecidability of the Acceptance Problem and the Halting Problem for Turing Machines, utilizing both Cantor's diagonalization method and the technique of reducibility.
MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser
View the complete course: https://ocw.mit.edu/18-404JF20
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY
7. Decision Problems for Automata and Grammars
Next · Lecture 9Lecture 9: Reducibility (18.404J)
Seminar notes & discussion
No public seminar notes on this lecture yet.