8900349 Lerman Research in Classical Recursion Theory will be pursued. The main goals of this work are to analyze further the types of search procedures needed to obtain results in Recursion Theory, and to see how well the information content of a set is mirrored by the degree of that set. The first goal is to develop a O(n) -priority argument for all n: Lerman will try to do so in the context of deciding the existential theory of the recursively enumerable degrees with Steffen Lempp. He will then try, with Lempp and Kucera, to find a priority-free proof of this theory. The second goal will be pursued by studying automorphisms of sets of degrees, primarily the recursively enumerable degrees. This project is already underway, jointly with Lempp, Shore and Soare, and the hope is to produce a nontrivial automorphism.
