Mathematical Sciences: Recursion Theory

数学科学：递归理论

• 批准号: 8900349
• 负责人: Manuel Lerman
• 金额: $ 15.66万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-06-01 至 1993-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8900349&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Recursion; Theory

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.

8900349 Lerman 将继续进行经典递归理论的研究。 这项工作的主要目标是进一步分析的类型， 搜索程序需要获得递归理论的结果， 看看一个集合的信息量有多好 由该集合的度数反映。 第一个目标是 对于所有的n，我们都可以使用O（n）优先级的参数：Lerman会尝试 这样做的背景下，决定存在主义理论的 与Steffen Lempp合作的递归可重复度。 他将 然后与Lempp和Kucera一起尝试找到一个无优先级的证明， 这一理论。 第二个目标将通过研究自同构来实现 度的集合，主要是递归的 度 这个项目已经在进行中，与Lempp合作， 海岸和Soare，希望能产生一个不平凡的 自同构