Theoretical Computer Science

Course notes for Harvard CS 121: Theoretical Computer Science (Fall 2022, Boaz Barak). Provides foundational knowledge in computability and complexity, as well as strong intuitions on computational models and fundamental limits of computation; my favorite computer science course at Harvard.

1. Computational models: circuits, regular expressions, context-free grammars, and Turing machines; standard Turing-equivalence reductions (\(\lambda\)-calculus, finite automata, etc).
2. Regex-DFA equivalence: single-pass constant-memory algorithms.
3. Rice’s theorem: nontrivial semantic functions are uncomputable. This is the price of universality!
4. Proof as computation: Gödel’s incompleteness theorem.