Math 784 — Fall 2001 Recursion Theory

This course will study the global structure of the Turing degrees with the aim of proving that the first order theory of the Turing degrees has the same complexity as second order arithmetic and many of the current results on definability and automorphisms. We hope to use as a text a (forthcoming) monograph by Slaman and Woodin, Definability in Degree Structures. We also expect to cover some of the local versions of these results by analyzing the structure of the degrees below the Halting problem and the degrees of sets definable in arithmetic. Again we will precisely characterize the complexity of the theories of these structures and study definability and automorphisms.

Prerequisites are a basic course in logic (Math 681) and/or complexity theory (CS 682), preferably including some familiarity with Turing reducibility.