Michael Sipser
Donner Professor of Mathematics · MIT · Distinguished · author of Introduction to the Theory of Computation
Michael Sipser is Donner Professor of Mathematics at MIT and author of the textbook Introduction to the Theory of Computation.
- lectures
- 25
- series
- 1
- hours
- 32
Start here
Series and courses
MIT 18.404J: Theory of Computation
Open the course
- 1Introduction, Finite Automata, Regular Expressions
- 2Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
- 3Regular Pumping Lemma, Conversion of FA to Regular Expressions
- 4Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
Show 21 moreShow fewer
- 5CF Pumping Lemma, Turing Machines
- 6TM Variants, Church-Turing Thesis
- 7Decision Problems for Automata and Grammars
- 8Undecidability
- 9Reducibility
- 10Computation History Method
- 11Recursion Theorem and Logic
- 12Time Complexity
- 13P and NP, SAT, Poly-Time Reducibility
- 14NP-Completeness
- 15Cook-Levin Theorem
- 16Space Complexity, PSPACE, Savitch's Theorem
- 17PSPACE-Completeness
- 18Games, Generalized Geography
- 19L and NL, NL = coNL
- 20Hierarchy Theorems
- 21Provably Intractable Problems, Oracles
- 22Probabilistic Computation, BPP
- 23Probabilistic Computation
- 24Interactive Proof Systems, IP
- 25coNP is a Subset of IP
In these lectures
- Cantor's diagonalization method proves that the set of real numbers and the collection of all languages are uncountable, whereas the set of all Turing machines is countable.Undecidability
- Nondeterministic finite automata (NFAs) allow multiple computation paths, zero paths, or transitions on the empty string.Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
- Generalized geography is PSPACE-complete, demonstrated via a polynomial-time reduction from TQBF.Games, Generalized Geography
Draws on
People cited in the lectures, at the moment of the citation.
- David HilbertFormulated Hilbert's problems, specifically his 1st problem regarding intermediate-sized sets between natural and real numbers.
- Kurt GödelShowed in the 1930s that the continuum hypothesis cannot be proved using standard axioms.
- Alonzo Church1903-1995, mathematician and logician.
- Alan Turing1912-1954, mathematician and computer scientist.
- Georg CantorMathematician in the late 19th century who conceived the diagonalization method and studied infinite sets.
- Paul CohenShowed in the early 1970s that the continuum hypothesis cannot be disproved using standard axioms.
Playlists
1About
Michael Sipser is Donner Professor of Mathematics at MIT and author of the textbook Introduction to the Theory of Computation. Sipser's MIT 18.404J lectures prove results from finite automata and undecidability to the Cook-Levin theorem and Savitch's theorem.
Same subject, Algorithms & Theoretical CS
Connections
32Their places, courses, books and lectures.
Concept1
Lectures25
- Undecidability
- Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
- Games, Generalized Geography
- Introduction, Finite Automata, Regular Expressions
- P and NP, SAT, Poly-Time Reducibility
- Regular Pumping Lemma, Conversion of FA to Regular Expressions
Show 19 moreShow fewer
- CF Pumping Lemma, Turing Machines
- Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
- PSPACE-Completeness
- TM Variants, Church-Turing Thesis
- Reducibility
- Recursion Theorem and Logic
- Cook-Levin Theorem
- NP-Completeness
- Computation History Method
- Decision Problems for Automata and Grammars
- Space Complexity, PSPACE, Savitch's Theorem
- Hierarchy Theorems
- Time Complexity
- Provably Intractable Problems, Oracles
- Probabilistic Computation, BPP
- L and NL, NL = coNL
- Interactive Proof Systems, IP
- Probabilistic Computation
- coNP is a Subset of IP





