Mathematics 30200 / Computer Science 38000: Computability Theory, Winter 2021

TTh 2:40 - 4:00 (see Canvas page for Zoom links)

Instructor:
Denis Hirschfeldt
drh@math.uchicago.edu
He/Him/His
Office Hours: M 12:00 - 1:00, W 1:00-2:00, or by appointment



Howework Assignment 1 (due Friday, January 29th)

Howework Assignment 2 (due Friday, February 5th)

Howework Assignment 3 (due Friday, February 12th)

Howework Assignment 4 (due Friday, February 19th)

Howework Assignment 5 (due Friday, February 26th)

Howework Assignment 6 (due Friday, March 5th)

Howework Assignment 7 (due Friday, March 12th)



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

Theory of Recursive Function and Effective Computability by Rogers

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