MATH 7840: Recursion Theory: The Recursively Enumerable Degrees (Fall 2011)

Instructor: Richard Shore

MATH 7840 will be a first course in the theory of computability. We will assume some background in logic. MATH 6810 or CS 6820 should be more than sufficient.

This term we will concentrate on the recursively (computably) enumerable sets and degrees. The text will be Recursively Enumerable Sets and Degrees by R. I. Soare (Springer-Verlag) or more precisely a version of the new edition in preparation.

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, the Turing jump operator and the arithmetical hierarchy.

Next there will be some development of construction procedures for non-r.e. sets including the Kleene-Post finite extension method (really Cohen forcing in arithmetic) and minimal degree constrictions by forcing with trees (perfect set forcing).

The heart of the course, however, will be the development of various kinds of priority arguments for the construction of r.e. sets including finite and infinite injury as well as tree arguments. We will use these methods to analyze the structure of the (Turing) degrees of r.e. sets and something of their set theoretic structure as well. Connections between degree theoretic and other properties such as types of approximations, rates of growth and complexity of definition will be considered.