Theory of Computation, Fall 2020
Dive into the world of theoretical computer science with this comprehensive lecture series on the Theory of Computation, taught by Professor Michael Sipser at MIT. Explore fundamental concepts such as finite automata, regular expressions, pushdown automata, Turing machines, and computational complexity theory. Learn about key theorems like Cook-Levin, Savitch's, and Immerman-Szelepcsenyi, while developing a deep understanding of computability and complexity. Progress through 26 lectures covering topics from basic automata to advanced concepts like interactive proof systems, probabilistic computation, and NP-completeness. Gain insights into decision problems, undecidability, reducibility, and space complexity. Engage with this rigorous course to build a strong foundation in theoretical computer science and its applications.