Mathematics 30200 / Computer Science 38000: Computability Theory, Spring 2017

TTh 1:30-2:50 in Eckhart 308


Denis Hirschfeldt
Ryerson 359B
(773) 702-7375
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