MATH 6010: Computability Theory (Fall 2015)

Schedule

1. 08/24: deterministic finite automata, languages
2. 08/26: nondeterministic finite automata, subset construction
3. 08/28: regular expressions, regular languages
4. 08/31: limits of automata, pumping lemma
5. 09/02: Turing machines
6. 09/04: configurations, nondeterministic Turing machines
7. 09/09: recursive and recursively enumerable languages
8. 09/11: Church-Turing thesis, lambda-calculus
9. 09/14: halting problem
10. 09/16: many-one reductions
11. 09/18: Rice's Theorem
12. 09/21: word problem for semigroups
13. 09/23: primitive recursive functions and predicates
14. 09/25: Ackermann function, mu-recursion
15. 09/28: Arithmetization via prime power coding, Enumeration Theorem for computable functions
16. 09/30: Kleene's Normal Form Theorem, s-m-n Theorem
17. 10/02: Arithmetical Hierarchy
18. 10/05: Normal Form Theorem for recursively enumerable predicates, universal predicates
19. 10/07: complete sets
20. 10/09: creative and simple sets
21. 10/12: nonrecursive, non m-complete, r.e. sets
22. 10/14: finite approximations
23. 10/16: Friedberg Splitting Theorem
24. 10/19: oracles, relativization
25. 10/21: Turing degrees
26. 10/23: Turing jump
27. 10/26: finite approximations, Post's Theorem
28. 10/28: incomparable degrees
29. 10/30: minimal pairs
30. 11/02: properties of the jump
31. 11/04: Post's Problem
32. 11/06: Friedberg-Muchnik Theorem
33. 11/09: time complexity, O
34. 11/11: P, NP, polytime verifiers
35. 11/13: space complexity
36. 11/16: connecting space and time, reachability, configuration graph
37. 11/18: Savitch's Theorem
38. 11/20: Space Hierarchy Theorem
39. 11/30: Space Hierarchy Theorem
40. 12/02: Time Hierarchy Theorem

Assignments

1. due 09/02
2. due 09/09
3. due 09/16
4. due 09/23
5. due 09/30
6. due 10/07
7. due 10/14
8. due 10/21
9. due 10/28
10. due 11/18
11. due 12/09

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