Peter Hinman

My main area of interest is the subarea of Mathematical Logic known as Recursion Theory (or, under an increasingly popular renaming, Computability Theory). In its most widely studied form, the subject concerns the precise relationship between sets of natural numbers which formalizes the intuitive notion of relative effective computability . With any set A of natural numbers we associate the A-problem: given a number m, determine whether or not m is a member of A. Then we say that a set A of natural numbers is recursive in another set B exactly when there exists an algorithm which can solve the A-problem with the help of an oracle which can solve the B-problem. The relation A is recursive in B and B is recursive in A is an equivalence relation; the equivalence classes are called degrees (of unsolvability)and inherit a natural partial ordering. The structure of this partial ordering, and particularly its restriction to interesting subsets, have been a fruitful area of study for nearly 50 years.

Some of the most interesting results concern the restriction to the degrees of recursively enumerable sets (r.e. degrees): a set A (of natural numbers) is recursively enumerable if there is an algorithmically calculable (recursive) function F from natural numbers to natural numbers such that A is exactly the set of values of F. At first there were only two r.e. degrees known; Posts Problem (1944) was solved in 1957 by Friedberg and Muchnik, who proved that there are many r.e. degrees and that they are not linearly ordered. They introduced the priority method which has been greatly expanded and developed and is still the dominant method for proving theorems in this area.

By now much is known about the structure of the r.e. degrees, and although there are still open problems, attention has turned recently to the degrees of slightly larger classes --- for example, the degrees of sets which are the difference of two r.e. sets (d-r.e. degrees) or those which are r.e. relative to some r.e. oracle. Surprisingly, these classes seem to have substantially different structure; in particular, the partial orderings are not isomorphic to those of the r.e. degrees. One current leading open question is: is the ordering of the d-r.e. degrees isomorphic to the ordering of the degrees of sets which are differences of differences of r.e. sets. The book Recursively enumerable sets and degrees by R.I. Soare (Springer-Verlag, 1987) is an excellent introduction to the subject, which takes the reader from the basic definitions to the frontiers of the field in 1985-6. A somewhat more encyclopedic approach is taken by Classical Recursion Theory by P. Odifreddi (North-Holland, Volume I, 1989, Volume II, 1999). A third volume is promised for the future.

There are many other aspects to Recursion Theory. One is the overall structure of the degrees of arbitrary sets described in Degrees of Unsolvability by M. Lerman (Springer-Verlag, 1983). Another is the extension of the notion of effective calculability to domains beyond the natural numbers: ordinal numbers, objects of finite type, and arbitrary sets. Some of this appears in Recursion-Theoretic Hierarchies by P.G. Hinman (Springer-Verlag, 1978) and a more recent treatment is in Higher Recursion Theory by G.E. Sacks (Springer-Verlag, 1990). One aspect of this part of the subject that I have been working with most recently is the so-called Medvedev degrees. With a set P of sets of natural numbers we associate the P-problem: solve the A-problem for some member A of P. Then P is Medvedev-reducible to Q iff there is an effective mapping which takes any solution to the Q-problem to a solution to the P-problem --- that is, maps Q into P. This again leads to a notion of degree and to a partial ordering of these degrees.

Recursion Theory has close ties with other branches of Logic, which all fit under the loose heading of Definability Theory. Generally, this is the study of the properties of mathematical objects which can be deduced from the complexity of the means required to define them. One part of this theory is known as Descriptive Set Theory and deals with definable sets of real numbers. A sample classical result is that any set of reals which is the projection of a Borel set in the plane is Lebesgue measurable. An overview of this field is contained in Descriptive Set Theory by Y.N. Moschovakis (North-Holland, 1980).