Mathematical Sciences: Recursive Function Theory

数学科学：递归函数论

• 批准号: 9106714
• 负责人: Robert Soare
• 金额: $ 20.43万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-07-15 至 1994-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9106714&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Recursive; Function; Theory

The investigator will continue research in several areas of recursive function theory, including: automorphisms and definable properties of the recursively enumerable (r.e.) sets; algebraic, model-theoretic, and definability questions concerning the r.e. Turing degrees; recursion-theoretic properties of various algebraic structures; and computational complexity questions for polynomially-time-bounded Turing degrees. Soare recently developed with Harrington and Lachlan a very powerful method for generating new automorphisms of the r.e. sets, and they simultaneously found several new definable properties which together with the automorphisms answered many fundamental questions going back to Post's program (1944) on the relationship between the algebraic structure of an r.e. set and its Turing degree. These two new methods will be developed further and applied to answer other open questions on r.e. sets. Soare will continue his study of questions of continuity, definability, embeddability, and partial decidability for the structure of the r.e. Turing degrees. He will complete research on computability aspects of various algebraic structures, specially Boolean algebras, investigating, for example, which information can be coded into their classical isomorphism types. Finally, he will continue research with several collaborators on computational complexity questions for the many-one and Turing degrees under polynomially-time-bounded Turing computations. The motivation for studying such notions lies in their origins. For example, Turing machines idealize actual computing devices, and Turing degrees simply order their relative computational power. The elaborate techniques required to prove theorems in this area sometimes tend to obscure these fundamental facts, despite an effort to use suggestive terminology, e.g., "computability" and "computational complexity."

研究人员将继续在以下几个领域进行研究： 递归函数理论，包括：自同构和可定义 递归可列（r.e.）集合;代数， 模型理论，和可定义性问题有关的r.e. 图灵度;各种递归理论性质 代数结构;和计算复杂性的问题， 多项式时间有界图灵度 Soare最近 与哈灵顿和拉克伦一起开发了一种非常有效的方法， 生成r.e.的新自同构。集，他们 同时发现了几个新的可定义属性， 与自同构一起回答了许多基本问题 问题回到波斯特的计划（1944年）的关系 在r.e.的代数结构之间。集合及其图灵 ℃下 这两种新方法将进一步发展， 用于回答其他关于r.e.的开放性问题。集. Soare将 继续他对连续性，可定义性， 可嵌入性和部分可决定性的结构， R.E.图灵度他将完成关于可计算性的研究 各种代数结构的方面，特别是布尔 代数，研究，例如，哪些信息可以 编码成它们的经典同构类型。 最后，他会 继续与几个合作者研究计算 复杂性问题的多1和图灵度下 多项式时间有界的图灵计算。 研究这些概念的动机在于 起源. 例如，图灵机将实际计算理想化， 设备，而图灵度只是简单地将它们的相对 计算能力 为了证明 在这方面的定理有时往往掩盖这些基本的 事实，尽管努力使用暗示性术语，例如， “可计算性”和“计算复杂性”。"