Mathematical Sciences: Recursion Theory

数学科学：递归理论

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

Lempp will pursue research in recursion theory. The main project is to study the decidability of fragments of the first- order theories of the sets of r.e. degrees and of Turing degrees where information about the jump operator is included in the language. Lempp hopes that strategies from the solution to the deep degree problem (with Slaman) will help with the necessary embeddings of homomorphisms of partial orders into these sets of degrees. Secondly, Lempp will investigate the existence of a join operation in the r.e. degrees modulo some equivalence relation defined by iterated jumps. In a forcing argument, Lempp has already shown that the join does not necessarily exist in the Turing degrees modulo this equivalence relation. Furthermore, Lempp plans to conclude work begun with Cooper and Watson by proving an extension of the nondensity theorem in the d.r.e. degrees. Finally, Lempp intends to continue his work in index sets. In his thesis, Lempp has exhibited a large family of such index sets for r.e. sets the r.e. supersets of which form a Boolean algebra; he now plans to look at the non-Boolean algebra case and at index sets of r.e. degrees. Recursion theory being the study of the theoretical limits of computability, such investigations when completed may well renew contact with their original inspiration in the world of electronic computers.

Lempp将继续研究递归理论。 主要 项目是研究第一个片段的可判定性- r.e.集合的序理论度和图灵度 其中关于跳转操作符的信息包括在 语言 Lempp希望从解决方案到 深度问题（与斯拉曼）将有助于必要的 偏序同态嵌入到这些集合中， 度 其次，Lempp将调查是否存在一个 r.e.中的连接操作模某些等价的次数 由迭代跳跃定义的关系。 在一个令人信服的论点中， 已经表明，连接不一定存在于 图灵度模这个等价关系。 此外，委员会认为， Lempp计划结束与库珀和沃森开始的工作， 在D.R.E.中证明非密度定理的一个推广。 度 最后，Lempp打算继续他的索引工作， 集. 在他的论文中，伦普展示了一个大家族 r.e.的索引集设置r.e.其中的超集形成了 布尔代数;他现在计划研究非布尔代数 case和at index sets of r.e.度 递归理论是 对可计算性的理论极限的研究，如 调查工作一旦完成， 电子计算机世界的原始灵感。