Math 6010 Spring 2021

MATH 6010: Computability Theory (Spring 2021)



  1. 01/15: deterministic finite automata, languages [slides]
  2. 01/20: nondeterministic finite automata, subset construction


  1. due 01/25


  1. Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to automata theory, languages, and computation. Pearson, 3rd edition, 2006.
  2. Odifreddi, Piergiorgio. Classical recursion theory. North-Holland Publishing Co., Amsterdam, 1989 (electronic copy available for free via the University of Colorado library).
  3. Papadimitriou, Christos. Computational complexity. Addison-Wesley, 1994.
  4. Sipser, Michael. Introduction to the theory of computation. Thomson Course Technology, Boston, 2nd edition, 2006.
  5. Soare, Robert I. Recursively enumerable sets and degrees. Springer-Verlag, Berlin, 1987.
  6. Lecture notes by Stephen G. Simpson (PSU, 2005)