Mathematical Sciences: Recursive Function Theory

研究者将继续研究递归函数理论的几个领域，包括：递归可枚举集合的自同构和可定义性质；关于图灵度的代数、模型论和可定义性问题；各种代数结构的递归性质以及多项式时间有界图灵度的计算复杂性问题。Soare最近与Harrington和Lachlan一起开发了一种非常强大的方法来生成re集合的新自同构，他们同时发现了几个新的可定义的性质，这些性质和自同构一起回答了波斯特1944年提出的关于r.e.集的代数结构和图灵度之间关系的程序中的许多基本问题。这两种新方法将得到进一步的发展，并应用于回答r.e.集上的其他开放性问题。Soare将继续研究图灵度结构的连续性、可定义性、可嵌入性和部分可决性问题。他将完成各种代数结构的可计算性方面的研究，特别是布尔代数，例如，研究哪些信息可以编码成它们的经典同构类型。最后，他将与几位合作者继续研究多项式时域图灵计算下的多一度和图灵度的计算复杂性问题。研究这些概念的动机在于它们的起源。例如，图灵机理想化了实际的计算设备，而图灵度只是对它们的相对计算能力排序。在这一领域，证明定理所需的复杂技术有时会模糊这些基本事实，尽管努力使用暗示性术语，例如“可计算性”和“计算复杂性”。

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."