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