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

TTh 2:00-3:20 in Eckhart 312

Instructor:

Denis Hirschfeldt
Ryerson 359B
(773) 702-7375
drh@math.uchicago.edu
office hours: T 3:30 - 4:30 and W 1:00 - 2:00, or by appointment



Homework 1 (due Thursday, April 12th)

Homework 2 (due Thursday, April 19th)

Homework 3 (due Thursday, April 26th)

Homework 4 (due Thursday, May 3rd)

Homework 5 (due Thursday, May 10th)

Homework 6 (due Tuesday, May 22nd)

Homework 7 (due Thursday, May 31st)



Turing's On computable numbers, with an application to the Entscheidungsproblem

A video of my public lecture Waking up from Leiniz' Dream: On the Unmechanizability of Truth

Turing Computability: Theory and Applications by Soare

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)