|
|
|
MATH 784: Recursion Theory (Fall 2007)Instructor: Richard Shore This course will study structure of the Turing degrees (i.e. relative complexity of computation). We will explore their basic algebraic structure and relations between order theoretic properties of the degrees of functions, their rates of growth and notions of genericity. We will characterize the complexity of the theory of the structure as that of full second order arithmetic and study the dividing line between decidable and undecidable fragments. We will present an analysis of iterations of the notion of recursive enumerability of sets, Pi-0-1 classes of functions and their relation to order theoretic properties of their degrees. The ultimate goal of the course will be to present the recent proof that the Turing jump (the halting problem viewed relative to an arbitrary set or function or, equivalently, the operation of going from a set to those definable from it in arithmetic with one existential quantifier) is definable (even in almost all jump ideals) and related results on automorphisms of, and definability in, the degrees and their jump ideals. Last modified:March 29, 2007 |
