MATH 7840: Recursion Theory: Computability theory (Fall 2010)

Instructor: Richard Shore

MATH 7840 will be a course in the theory of computability concentrating on the global and local theory of the Turing degrees. We will assume only some background in logic. MATH 6810 or Computer Science 6820 should be more than sufficient.

We will begin with a brief discussion of the basic properties of a reasonable model of computability: universal machines, the enumeration, s-m-n and recursion theorems, r.e. (effectively or computably enumerable) sets and the halting problem. Next will come the notions of relative computability (Turing reducibility), the Turing jump operator and the arithmetical hierarchy.

We will then proceed to study the structure of the Turing degrees of all sets and functions as well as important substructures such as the degrees below 0' (the Halting problem) and the degrees of the arithmetic sets (those definable in first order arithmetic or equivalently computable form some finite iteration of the Turing jump). The primary techniques will be forcing arguments in the setting of arithmetic rather than set theory. We begin with the development of construction procedures such as the Kleene-Post finite extension method (now seen as Cohen forcing in arithmetic) and minimal degree constrictions by forcing with trees (perfect set forcing).

Relations with rates of growth and the jump hierarchy will be explored. We will prove the basic results about the complexity of theories of these structures such as that the theories of the degrees and the degrees below 0' are of the same complexity as second order arithmetic and first order arithmetic, respectively. We will also study the restrictions on possible automorphisms of the structures and definability results: which apparently external (but natural) relations on the structures can be defined internally. In particular, we hope to reach the proof that the Turing jump which captures quantification in arithmetic is definable in terms of relative computability alone.

The textbook will be Degrees of Unsolvability by M. Lerman and lecture notes of my own.