This course on the Theory of Computation aims to teach students important concepts such as computability and computational complexity theory. The learning outcomes include understanding the Cook-Levin Theorem, Savitch’s Theorem, and Immerman-Szelepcsenyi theorem. Students will develop skills in finite automata, regular expressions, pushdown automata, Turing machines, decision problems, undecidability, time complexity, NP-completeness, PSPACE, and probabilistic computation. The teaching method involves video lectures by Professor Sipser, with a syllabus covering various topics in theoretical computer science. This course is intended for students interested in deepening their knowledge of the theoretical foundations of computation.
Overview
Syllabus
1. Introduction, Finite Automata, Regular Expressions.
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA.
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions.
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion.
5. CF Pumping Lemma, Turing Machines.
6. TM Variants, Church-Turing Thesis.
7. Decision Problems for Automata and Grammars.
8. Undecidability.
9. Reducibility.
10. Computation History Method.
11. Recursion Theorem and Logic.
12. Time Complexity.
14. P and NP, SAT, Poly-Time Reducibility.
15. NP-Completeness.
16. Cook-Levin Theorem.
17. Space Complexity, PSPACE, Savitch's Theorem.
18. PSPACE-Completeness.
19. Games, Generalized Geography.
20. L and NL, NL = coNL.
21. Hierarchy Theorems.
22. Provably Intractable Problems, Oracles.
23. Probabilistic Computation, BPP.
24. Probabilistic Computation (cont.).
25. Interactive Proof Systems, IP.
26. coNP is a subset of IP.
Taught by
MIT open courseware
