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.）n阶跳跃约简 谓词。 2. Lempp与Lerman、海岸和Soare一起， 计划调查同构r.e.间隔 ，一个部分结果，以显示存在的非平凡的 r.e.的自同构度 3. Lempp，与 Ambos-Spies，将试图表明，每一个r. e。间隔具有 非aleph-0范畴理论，一个现在只知道的结果， 所有r.e.的集合度 4. Lempp与Kucera和 勒曼，将调查r.e.的建设。度通过 对角非递归函数，作为 传统的优先权论点。 这些都是递归专家感兴趣的话题 理论，一个理论，形式化的概念，机械 如果有足够的内存和足够的时间， 观察 这和机械计算是不一样的 一些合理的时间长度，但回答问题， 更一般概念往往更容易获得和摆脱 在实际的可计算性问题上。