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

- due 01/27
- due 02/03
- due 02/10
- due 02/15
- due 02/22
- due 03/01, solution for 3
- due 03/08
- due 03/15
- due 03/29
- due 04/12
- due 04/19
- due 04/26

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