Math 6010 Spring 2019

MATH 6010: Computability Theory (Spring 2019)

Syllabus

Schedule

  1. 01/14: deterministic finite automata, languages
  2. 01/16: nondeterministic finite automata, subset construction
  3. 01/18: regular expressions, regular languages
  4. 01/23: Pumping Lemma, Myhill-Nerode Theorem
  5. 01/25: Turing machines
  6. 01/28: configurations, nondeterministic Turing machines
  7. 01/30: recursive and recursively enumerable languages
  8. 02/01: Church-Turing thesis, lambda-calculus
  9. 02/04: Goedel numbering, halting problem
  10. 02/06: acceptance problem, many-one reductions
  11. 02/08: universal Turing machine, Rice's Theorem
  12. 02/11: word problem for semigroups is undecidable
  13. 02/13: generative grammar, Chomsky hierarchy
  14. 02/15: contextfree grammar, pushdown machines, balanced parentheses languages
  15. 02/18: primitive recursive functions and predicates
  16. 02/20: Ackermann function, mu-recursion
  17. 02/22: elementary recursive functions, complexity classes ELEMENTARY < PR < R, recursive functions are computable
  18. 02/25: Arithmetization via prime power coding, computable functions are recursive
  19. 02/27: Enumeration Theorem for computable functions, Kleene's Normal Form Theorem, s-m-n Theorem
  20. 03/01: Arithmetical Hierarchy
  21. 03/06: Normal Form Theorem for recursively enumerable predicates, universal predicates
  22. 03/08: complete sets
  23. 03/15: productive, creative sets
  24. 03/18: simple sets
  25. 03/20: nonrecursive, non m-complete, r.e. sets
  26. 03/22: finite approximations, Friedberg Splitting Theorem
  27. 04/01: oracles, relativization
  28. 04/03: Turing degrees, Turing jump
  29. 04/05: finite approximations, Post's Theorem
  30. 04/08: e-splittings, incomparable degrees meeting in 0
  31. 04/10: the jump is not injective, Friedberg completeness criterion
  32. 04/12: Post's Problem, Friedberg-Muchnik Theorem via finite injury priority method
  33. 04/15: r.e. degrees are dense and split, every finite distributive lattice embeds into the poset of r.e. degrees
  34. 04/17: time complexity, O
  35. 04/19: P, NP, polytime verifiers, space complexity, L, NL
  36. 04/22: connecting space and time, reachability, configuration graph
  37. 04/24: Savitch's Theorem, Space Hierarchy Theorem
  38. 04/26: Time Hierarchy Theorem
  39. 04/29: descriptive complexity, Fagin's Theorem
  40. 05/01:

Assignments

  1. due 01/25
  2. due 01/30
  3. due 02/06
  4. due 02/13
  5. due 02/22
  6. due 02/27
  7. due 03/08
  8. due 03/15
  9. due 04/10
  10. due 04/29

Reading

Some of the following books are on reserve in Gemmill library.
  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)