Mathematical Sciences: Recursion Theory

8900349进行经典递归理论的勒曼研究。这项工作的主要目标是进一步分析在递归理论中获得结果所需的搜索过程的类型，并查看集合的信息内容在多大程度上被该集合的程度所反映。第一个目标是为所有n发展一个O(n)优先级论证：Lerman将在与Steffen Lempp决定递归可枚举度的存在论的背景下尝试这样做。然后，他将与Lempp和kuucera一起尝试找到一个无关优先级的理论证明。第二个目标将通过研究度集合的自同构来实现，主要是递归可枚举的度。这个项目已经在进行中，与Lempp， Shore和Soare合作，希望产生一个非平凡的自同构。

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.