MATH 6010: Computability Theory (Spring 2021)

Schedule

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

Assignments

1. due 01/25

Reading

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)