This award supports several short term research visits to the Federal Republic of Germany by Robert Soare and Theodore Slaman of the University of Chicago and Steffen Lempp of Yale University in order to collaborate with Klaus Ambos-Spies of the University of Heidelberg in several topics of mathematical logic. In particular, they will pursue research on recursive function theory and the theory of computation. The University of Chicago (where Lempp recently obtained his PhD) is a major center of research on these topics and these U.S. mathematicians have produced some outstanding contributions to the field. Germany has a long and distinguished tradition in this field as well, and Professor Ambos-Spies is a leading figure in recursive function theory there. He has also done extensive research in applications of the methods of recursive function theory to computational complexity. Previous intermittent collaboration between Professors Soare and Ambos-Spies has been mutually stimulating and productive. The proposed visits will allow more frequent collaboration between them and the inclusion of two other U.S. mathematicians whose work is directly relevant to that of Ambos-Spies. Mathematical logic and particularly recursive function theory and the theory of computation have recently been very active in the U.S. and abroad. Recursion theory arises from an attempt to formalize what it means for a set to be mechanically definable, and thus it has applications to theoretical computer science and the theory of computational complexity.
