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

TTh 2:00 - 3:20 in Eckhart 312

Instructor:
Denis Hirschfeldt
drh@uchicago.edu
He/Him/His
Office Hours: by appointment



Assignment 0: Read Alan Turing's On computable numbers, with an application to the Entscheidungsproblem. (Access to the article is free from university computers or using a library proxy.)

Assignment 1 (due on Friday, January 19th)

Assignment 2 (due on Friday, January 26th)

Assignment 3 (due on Friday, February 2nd)

Assignment 4 (due on Friday, February 9th)

Assignment 5 (due on Friday, February 16th)

Assignment 6 (due on Friday, February 23rd)

Assignment 7 (due on Friday, March 1st)



Waking up from Leiniz' Dream: On the Unmechanizability of Truth (lecture video)

Mathematical Logic and Computation by Avigad

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)

Effectively Closed Sets by Cenzer and Remmel