Mathematics 30200 / Computer Science 38000: Computability Theory,
Spring 2017
TTh 1:30-2:50 in Eckhart 308
Instructor:
Denis Hirschfeldt
Ryerson 359B
(773) 702-7375
drh@math.uchicago.edu
office hours: T 10:00-11:00 and Th 3:00-4:00
Assignment 1, due on Thursday, April 13th,
in class
Assignment 2, due on Thursday, April 20th,
in class
Assignment 3, due on Thursday, April 27th,
in class
Assignment 4, due on Thursday, May 4th,
in class
Assignment 5, due on Thursday, May 11th,
in class
Assignment 6, due on Thursday, May 18th,
in class
Assignment 7, due on Thursday, May 25th,
in class
Soare's
Turing Computability: Theory and Applications
Turing's On
computable numbers, with an application to the
Entscheidungsproblem
Chapter
2: Computability Theory of Algorithmic
Randomness and Complexity by Downey and Hirschfeldt (errata, clarifications, and updates)
Slicing the
Truth: On the Computability Theoretic and Reverse Mathematical Analysis of
Combinatorial Principles by Hirschfeldt
Reflections on
Trusting Trust by Ken Thompson (1983 Turing Award lecture)
Effectively
Closed Sets by Cenzer and Remmel
Slides for my talk at Berkeley