Mathematical Sciences: Recursion Theory

数学科学：递归理论

• 批准号: 8901529
• 负责人: Steffen Lempp
• 金额: $ 3.86万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-06-01 至 1991-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8901529&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Recursion; Theory

Lempp intends to pursue research in classical recursion theory. He plans to concentrate in the following areas: 1. Lempp, jointly with Lerman, plans to finish up a project on the decidability of the existential theory of the recursively enumerable (r.e.) degrees with nth jump reducibility predicates. 2. Lempp, jointly with Lerman, Shore, and Soare, plans to investigate the existence of isomorphic r.e. intervals , a partial result toward showing the existence of nontrivial automorphisms of the r.e. degrees. 3. Lempp, jointly with Ambos-Spies, will try to show that every r.e. interval has a non-aleph-0 categorical theory, a result known now only for the set of all r.e. degrees. 4. Lempp, jointly with Kucera and Lerman, will investigate the construction of r.e. degrees via diagonally nonrecursive functions, as an alternative to conventional priority arguments. These are topics of interest to experts in recursion theory, a theory which formalizes the notion of mechanically computable if given enough memory and enough time. Observe that this is not really the same as mechanically computable in some reasonable length of time, but answers to questions about the more general notion are often easier to obtain and do shed light on practical computability questions.

LEMPP打算从事古典递归理论研究。 他计划专注于以下领域：1。LEMPP与Lerman共同计划完成一个有关递归列举（R.E.）度的存在理论的项目，并具有Nth Jumps降低性谓词。 2. Lempp与Lerman，Shore和Soare共同研究了同构R.E.的存在。间隔，这是显示R.E.非平凡自动形态存在的部分结果。学位。 3。莱姆普（Lempp）与Ambos-Spies共同尝试表明每个R.E.间隔具有非ALEPH-0分类理论，这一结果现在仅以所有R.E.的集合而闻名。学位。 4. Lempp与Kucera和Lerman共同研究R.E.的构建。通过对角线非传递函数的学位，作为常规优先参数的替代方案。 这些是递归理论专家感兴趣的主题，该理论是在给予足够的记忆和足够时间的机械计算的概念中形式化的。 观察到这与在某些合理的时间内的机械计算并不相同，但是关于更通用概念的问题的答案通常更容易获得，并阐明了实际的可计算性问题。