Math 6010 Spring 2021
MATH 6010: Computability Theory (Spring 2021)
Syllabus
Schedule
- 01/15: deterministic finite automata, languages [slides]
- 01/20: nondeterministic finite automata, subset construction
Assignments
- due 01/25
Reading
- Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to automata theory, languages,
and computation. Pearson, 3rd edition, 2006.
- Odifreddi, Piergiorgio. Classical recursion theory. North-Holland Publishing Co., Amsterdam, 1989 (electronic copy available for free via the University of Colorado library).
- Papadimitriou, Christos. Computational complexity. Addison-Wesley, 1994.
- Sipser, Michael. Introduction to the theory of computation. Thomson Course Technology, Boston,
2nd edition, 2006.
- Soare, Robert I. Recursively enumerable sets and degrees. Springer-Verlag, Berlin, 1987.
- Lecture notes by Stephen G. Simpson (PSU, 2005)