Theory of Computation, Fall 2017



Introduction

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).

Textbook


Class notes

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

  • Homework


    Maintained by Wonhong Nam.