MATH 6010: Computability Theory (Spring 2021)

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]
37. 04/16: time constructible functions, Time Hierarchy Theorem [see previous slides]
38. 04/19: Immerman-Szelepcsenyi Theorem, NL=coNL [slides]
39. 04/21: polytime reductions, NP-hardness, SAT is NP-complete [slides]
40. 04/23: more NP-complete problems, clique, graph coloring [slides]
41. 04/26: Ladner's Theorem, intermediate complexity [slides]
42. 04/28: presentation Lotfi: stack and counter machines

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,
7. due 03/08
8. due 03/15
9. due 03/29
10. due 04/12
11. due 04/19
12. due 04/26

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)