MATH 7840: Recursion Theory (Fall 2012)

Instructor: Richard Shore

Prerequisites: We will assume some background in logic. MATH 6810 or Computer Science 6820 should be more than sufficient.

Textbooks: Depending on the emphasis of the course (see below), either Recursively Enumerable Sets and Degrees by R. I. Soare (or the new edition Computably Enumerable...) or Degrees of Unsolvability by M. Lerman and lecture notes of my own.

MATH 7840 will be a first course in the theory of computability. There will be two possibilities for the emphasis of the course. The choice will depend on the background and interests of the participants.

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.

In either version of the course 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).

From that point on, the two alternatives diverge. One is to concentrate on the recursively (computably) enumerable sets and degrees. The text would then be Recursively Enumerable Sets and Degrees by R. I. Soare (or the new edition Computably Enumerable...). The heart of the course, in this case 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. At the moment this seems to be the likely choice of topics.

The second alternative (especially for those who may have taken the first version already) is to concentrate on the global structure of the degrees and of important substructures other than the r.e. degrees such as the degrees below 0' and the degrees of the arithmetic sets. The primary techniques will be forcing arguments. Relations with rates of growth and the jump hierarchy will be explored. We will get to some 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. For this alternative the text would probably be Degrees of Unsolvability by M. Lerman and lecture notes of my own.