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.
Last modified:
April 7, 2003
|
