MATH 784
Recursion Theory
(Fall 2003)
Instructor:
Richard Shore
Meeting
Time & Room
MATH 784 will be a first course in the theory of computability.
We will assume some background in logic. MATH 681 or COM S 682 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).
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 perhaps 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.
Last modified:
August 13, 2003
|
