Math
784 — Fall 2001
Recursion Theory
| Instructor: |
Richard Shore |
| Time: |
TR 1:25–2:40 |
| Room: |
Malott 205 |
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.
Last modified:
April 7, 2003
|
