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