Math 6010 Fall 2023

MATH 6010: Computability Theory (Fall 2023)

Syllabus

Schedule

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

Assignments

Reading

Arora, Sanjeev; Barak, Boaz. Computational complexity: a modern approach. Cambridge University Press, 2007 (electronic copy available via the CU library).
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 via the CU library).
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 via the CU library).