Theory of Computation

Mort Yao

Textbook:

  • Michael Sipser. Introduction to the Theory of Computation, 3rd edition.

Supplementary reading:

  • Neil Jones. Computability and Complexity: From a Programming Perspective. [PDF]

1 Formal Languages and Automata

  1. Preliminaries
  2. Finite languages
  3. Regular languages
  4. Context-free languages
  5. *Context-sensitive languages

2 Computability

  1. Church-Turing thesis
    • Turing machines
    • Turing completeness
      • Lambda calculus
      • Combinatory logic
      • Recursive function
      • Cellular automaton
      • Abstract rewriting system
  2. Algorithm
  3. Decidability
    • Decidable languages
    • Undecidability
    • Logical theories
  4. Reducibility
    • Many-one reductions
    • Turing reductions, Turing equivalence and Turing degree
  5. Recursion theorem
  6. Algorithmic information theory

3 Complexity

  1. Overview
  2. Time complexity
  3. Space complexity
    • Savitch’s theorem
    • PSPACE
      • PSPACE-completeness
    • L and NL
      • NL-completeness
      • NL=coNL
  4. Provable intractability
    • Hierarchy theorems
    • Relativization
    • Circuit complexity
  5. Advanced topics