Theory of Computation, Fall 2017


To understand computation, this course offers an introduction to the science behind computing by studying computation abstractly without worrying about specifics of programming languages and/or computing platforms. In particular, we will study (a) finite automata that capture what can be computed using constant memory, and define the class of regular languages useful for pattern matching languages; (b) the universal computational model of Turing machines, and the inherent limits of what can be solved on a computer (undecidability).


Class notes

  • Chapter 0. Introduction [2-up] [4-up]
  • Chapter 1. Regular Languages [2-up] [4-up]
  • Chapter 2. Context-Free Languages [2-up] [4-up]
  • Chapter 3. The Church-Turing Thesis [2-up] [4-up]
  • Chapter 4. Decidability [2-up] [4-up]
  • Halting Problem

  • Midterm stat.


    Maintained by Wonhong Nam.