Cornell Math - MATH 784, Spring 1999

MATH 784 — Spring 1999
Recursion Theory

Instructor: Richard Shore

Time:  TR 11:40-12:55

Room: WE B25

There are two possibilities for Math 784 this term (I or II below). In either case, we will assume some minimal background in logic and at least an acquaintance with Turing machines or some other model of computation. Math 681 or Computer Science 682 should be more than sufficient. Whichever version is offered this year, the other should be offered next year.

I. This course 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) with some of the later material taken from more recent papers.

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 (one week). Next will come the notions of relative computability, the Turing jump operator and the arithmetical hierarchy (two weeks).

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 constructions 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.

II. The course will concentrate on the structure of the Turing degrees as a whole. The introductory material described above will be covered a bit more quickly perhaps. As will the basic Kleene-Post constructions. The goal of the course will be to analyze both local and global structure of the Turing degrees as a whole and of certain substructures such as the degrees below the halting problem (those with effective approximations) and the arithmetic degrees (those of sets definable in arithmetic) but not the r.e. degrees. Local questions to be addressed are embeddings of partial orderings, in general, and lattices as initial segments. Global questions include the complexity of theory of the degrees, restrictions on possible automorphisms and definability issues. Connections between degree theoretic and other properties such as types of approximations, rates of growth and complexity of definition will also be considered. Many of the techniques developed will be related to forcing constructions. The text will be Degrees of Unsolvability by M. Lerman (Springer-Verlag) although some of the material will be taken from more recent papers.