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