Theory of Computation

September 2019–January 2020

Theory of Computation

I wrote these notes (in Chinese) when I took a bachelor course Theory of Computation by Prof. Huan Long. They follow Sipser’s amazing textbook Introduction to the Theory of Computation that sparked my interest in theoretical computer science. The point becomes apparent through my somewhat enthusiastic style in the notes; my apologies if I overdid it occasionally.

  1. Finite automata & regular languages
  2. Push down automata & context free languages
  3. Turing machines, RE and R
  4. Undecidability by diagonalisation
  5. Reduction
  6. Time complexity, P and NP
  7. Space complexity, PSPACE, L and NL
  8. Hierarchy theorems and oracles
Return↩︎