Theory of Computation

This inaugural lecture for MIT's Theory of Computation course introduces finite automata, regular languages, and regular expressions. It formally defines these concepts and proves closure properties for regular languages under union and concatenation.

This lecture introduces Nondeterministic Finite Automata (NFAs), proving their equivalence to Deterministic Finite Automata (DFAs) and demonstrating the closure properties of regular languages under concatenation and Kleene star. It concludes with methods for converting regular expressions into NFAs.

This lecture elaborates on the Regular Pumping Lemma as a proof technique for non-regular languages. It also covers the formal methods for converting deterministic finite automata (DFAs) into equivalent regular expressions.

This lecture introduces Pushdown Automata (PDA) and establishes the equivalence between Context-Free Grammars (CFG) and PDAs through detailed conversion algorithms. It covers the formal definition of PDAs and demonstrates the transformation process.

This lecture proves the Context-Free Language Pumping Lemma, demonstrating its utility in classifying languages that are not context-free. It then formally introduces Turing Machines, including the definition of deciders.

This lecture examines the equivalence of various Turing machine variants to the single-tape model, establishing the robustness of the computational paradigm. It then articulates the Church-Turing Thesis, positing the fundamental equivalence of Turing machines to all effective algorithms.

This lecture details the decidability of various problems concerning automata and grammars, laying foundational concepts in computational theory. It further introduces the T-recognizability of the acceptance problem for Turing Machines.

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.

This lecture delves into the reducibility method for proving undecidability and T-unrecognizability, defining mapping reducibility. It demonstrates the undecidability and T-unrecognizability of the emptiness problem for Turing Machines.

The session introduces configurations and computation histories, applying the computation history method to prove undecidability. It shows that the acceptance problem for LBA is decidable, while emptiness for LBA, PCP, and ALL for CFG are undecidable.

This lecture explores self-reference and the recursion theorem, presenting various applications. It also sketches Gödel’s first incompleteness theorem, connecting computability to mathematical logic.

This lecture introduces complexity theory, defining TIME(t(n)) complexity classes and the class P. It examines model-dependence for reasonable complexity models and demonstrates that PATH is in P.

The lecture defines NTIME(t(n)) classes and NP, proving COMPOSITES is in NP. It discusses the P vs. NP problem, establishes that CFG acceptance is in P, and introduces SAT and polynomial-time reducibility.

This session covers NP-completeness, focusing on SAT and 3SAT. It details a strategy for proving NP-completeness through reduction from 3SAT using gadget construction to simulate variables and clauses.

This lecture provides a proof of the fundamental Cook-Levin Theorem, establishing that SAT is NP-complete. It also rigorously demonstrates the NP-completeness of 3SAT.

The lecture introduces space complexity, defining SPACE(f(n)), NSPACE(f(n)), PSPACE, and NPSPACE. It proves TQBF is in PSPACE and analyzes LADDER for DFA in NSPACE(n) and SPACE(n^2).

This session proves Savitch’s Theorem, showing NSPACE(f(n)) is a subset of SPACE(f^2(n)). It further establishes PSPACE-completeness and proves that TQBF is PSPACE-complete.

This lecture explores the connection between games and quantifiers, defining the formula game. It proves generalized geography is PSPACE-complete and introduces log space classes L and NL, defining the configuration graph.

This lecture reviews log space, demonstrating NL is a subset of SPACE(log^2n) and P. It introduces log-space transducers, defines NL-completeness, proves PATH is NL-complete, and covers the Immerman-Szelepcsényi theorem (NL = coNL).

The lecture concludes the Immerman-Szelepcsényi theorem (NL = coNL) and proceeds to introduce and prove the time and space hierarchy theorems. It discusses their application in separating various complexity classes.

This session introduces exponential complexity classes and presents a “natural” provably intractable problem. It explores oracles and relativized computation, suggesting limitations of diagonalization for separating P and NP.

The lecture defines probabilistic Turing machines and the class BPP, sketching the amplification lemma. It introduces branching programs and read-once branching programs, starting the proof that EQ for ROBP is in BPP via the arithmetization method.