Robert Soare's main research area is mathematical logic and particularly the theory of computability. The theory of computable function emerged during the 1930's with the primitive recursive functions used in Godel's incompleteness theorem, and then the full definitions by Godel [1934] Turing [1936] and others of computable functions which played a significant role in later development of computing devices. Turing [1939] introduced the notion of an "oracle Turing machine" for defining relative computability of a set A from a set B. Sets are placed into equivalence classes called "degrees" if each is computable from the other, i.e. if they code the same amount of information. Since Post [1944] much work has been done on the structure of these degrees, particularly those containing a set which is computably enumerable (c.e.), that is which can be computably listed. The degrees are used to classify problems in mathematics as being solvable or unsolvable, such as Hilbert's 10th problem on Diophantine equations. They are also used to compare the information content of one unsolvable problem in mathematics or computer science to another. For example, the problem of deciding whether a program computes a total function is of strictly greater degree than that of the halting problem.
The first part of Soare's work has been on degrees and particularly the c.e. degrees C. Major questions concern the first order theory and classifying the algebraic structure of C. For example, Slaman and Soare [Annals of Mathematics, 2001] unified and extended virtually all the major results and methods about C over the last thirty years to solve the extension of embeddings problem for C, namely to give an algorithm to decide whether a given finite embedding into C can be extended to a second given embedding. This also gives a decision procedure for a large part of the Sigma_2 theory of C. Soare is working on related problems.
The second part of Soare's work is on E, the lattice structure of the c.e. sets under inclusion. Post [1944] initiated the study of the relationship between the degree of a c.e. set and its structural properties in E. Harrington and Soare [Proc. Nat'l. Acad. Sci., 1991] answered a question of Post by producing an E-definable property which guarantees incompleteness. On the other hand, Harrington and Soare have invented a new method [JAMS, 1996] for generating automorphisms of E. Automorphisms and definable properties tend to work in opposite directions closing the gap of our lack of knowledge. Soare and his students are working on a number of questions about automorphisms and definable properties.
The third part deals with computability and its interaction with model theory and algebraic structures. From basic theorems of model theory we know when a given theory has prime or saturated models. For example, when does a computable theory have computable prime or saturated models? Soare has worked with Lachlan on degrees of models of the theory Peano arithmetic, and also for full (true) arithmetic, to decide how such a model differs from a mere uniform upper bound for arithmetic sets. Soare and his students have worked with Bakh Khoussainov on computable categoricity of certain structures related to trees. Computability has also played a strong role in effective analyses of algebraic structures. For example, when does a structure have an isomorphic copy in every degree, but no computable copy? Soare and another student are working on such questions.
The fourth part of Soare's work deals with computability and differential geometry. In their preprint, The Fractal Nature of Reim/Diff , the authors Alex Nabutovsky and Shmuel Weinberger (NW), begin, ``In this paper we would like to expose some of the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.'' Part of this richness is due to the connection of computability, and in particular computably enumerable (c.e.) sets, to the geometry. The authors write ``there are large `basins' that have topology, and are repeated infinitely often within the space,'' and ``there seem to be infinitely many different sorts of basins with different geometries from each other.'' They show that, under certain circumstances, deciding whether a configuration is a basin is equivalent to an element being enumerated in a certain c.e. set, x in We, and even more surprising, that the depth of that basin in roughly the same as the least stage s such that x in We,s. At the request of the authors Soare proved a theorem that there exists an infinite chain {An} of c.e. sets with a certain property on how fast initial segments settle relative to one another. Soare's result will be published in his paper, Computability Theory and Differential Geometry . NW use this to show that the distribution and depth of the basins in the geometry are much more dramatic than previously thought. Soare and his graduate student are exploring other constructions of c.e. set with geometric applications.
Finally Soare is writing a new book on the theory of computability. His previous book with Springer Verlag, 1987, became the standard reference in mathematics and computer science for computability and computably enumerable sets. That book is now slightly outdated with respect to notation, terminology, and new results. The new book is intended as a replacement, updating the initial chapters, omitting many later chapters and writing ones on new results, and adding chapters on the relation of computability to model theory and to computational complexity in computer science. The new book will be called, "Computability Theory and Applications."