Math 6010 Spring 2021

MATH 6010: Computability Theory (Spring 2021)

Syllabus

Schedule

  1. 01/15: deterministic finite automata, languages [slides]
  2. 01/20: nondeterministic finite automata, subset construction [slides]
  3. 01/22: regular expressions, regular languages [slides]
  4. 01/25: Pumping Lemma, Myhill-Nerode Theorem, properties of regular languagues [slides]
  5. 01/27: Turing machines, configurations [slides]
  6. 01/29: nondeterministic Turing machines [slides]
  7. 02/01: computable and computabely enumerable languages [slides]
  8. 02/03: Church-Turing thesis, lambda-calculus [slides]
  9. 02/05: encodings, universal TM, (self) acceptance problem not computable [slides]
  10. 02/08: many-one reductions, halting problem [slides]
  11. 02/10: string rewriting, word problem for semigroups [slides]
  12. 02/12: primitive recursive functions and predicates [slides]
  13. 02/15: Ackermann function [slides]
  14. 02/19: mu-recursion, recursive functions are computable [slides]
  15. 02/22: Goedel numbering of DTM, computable functions are recursive, Kleene's normal form theorem [slides]
  16. 02/24: Enumeration Theorem for computable functions, s-m-n Theorem [see previous slides]
  17. 02/26: Arithmetical Hierarchy, Normal Form Theorem for c.e. predicates, universal predicates [slides]
  18. 03/01: many-one completeness for arithemtical hierarchy [slides]
  19. 03/03: Hilbert's Tenth Problem, Diophantine sets and functions [slides]
  20. 03/05: productive, creative sets are ``effectively'' non-computable [slides]
  21. 03/08: creative sets are Sigma_1-complete [see previous slides]
  22. 03/10: simple sets are not computable and not Sigma_1-complete [slides]
  23. 03/12: finite approximations, Friedberg Splitting Theorem [slides]
  24. 03/17: oracle TMs, relativization [slides]
  25. 03/19: Turing degrees, Jump Theorem [slides]
  26. 03/22: finite approximations, Post's Theorem [slides]
  27. 03/24: jump is not injective but unto > 0' [slides]
  28. 03/26: Friedberg's completeness criterion, e-splittings, incomparable degrees meeting in 0 [see previous slides]
  29. 03/29: Post's Problem, Friedberg-Muchnik Theorem via finite injury priority method [slides]
  30. 03/31: c.e. degrees are dense and split, distributive lattices embed into the poset of c.e. degrees [see previous slides]
  31. 04/02: time complexity, big O notation, single tape DTM simulating a multi tape DTM, non-deterministic TM [slides]
  32. 04/05: reachability, Hamiltonian cycle, P, NP, polytime verifiers [slides]
  33. 04/07: space complexity, connecting space and time [slides]
  34. 04/09: PSPACE, recursion for graph reachability [slides]
  35. 04/12: Savitch's Theorem, membership for semigroups [see previous slides]
  36. 04/14: space constructible functions, little o notation, Space Hierarchy Theorem [slides]

Assignments

  1. due 01/27
  2. due 02/03
  3. due 02/10
  4. due 02/15
  5. due 02/22
  6. due 03/01, solution for 3
  7. due 03/08
  8. due 03/15
  9. due 03/29
  10. due 04/12

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 CU 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. Turing computability : theory and applications. Springer, Berlin, 2016. (electronic copy available for free via the CU library).
  6. Lecture notes by Stephen G. Simpson (PSU, 2005)