MATH 7840: Recursion Theory (fall 2008)

Instructor: Richard Shore

For the fall of 2008, MATH 7840 will be a standard first course in the theory of computability. We will assume some background in logic. MATH 681 or CS 682 should be more than sufficient, but a good undergraduate course should also suffice.

We will concentrate on the recursively (computably) enumerable sets and degrees. The text will be a current draft of the book Computability Theory and Applications (a new version of the classic Recursively Enumerable Sets and Degrees) by R. I. Soare.

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. We will establish connections between complexity of definitions in arithmetic, the Turing jump and computability. Some time will be devoted to index sets and their complexity, rates of growth of functions and connections with computational complexity. We will also see some examples of mathematical theorems and constructions that cannot be carried out effectively and perhaps some analysis of relative complexity among such constructions.

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 perhaps minimal degree constrictions by forcing with trees (perfect set forcing).

The final topic of the course will be the development of various kinds of priority arguments for the construction of r.e. sets including finite and infinite injury and perhaps tree arguments as well. 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.