Computability Theory and Logic

在这个项目中，Soare将研究可计算性理论，特别是一个集合与另一个集合的相对可计算性（图灵归约）。 第一个目标是研究可计算可枚举集合的可计算性，并将它们的代数结构与它们编码的信息的程度以及它们可以相对于计算复杂性的某种度量被枚举的速度相关联。 这里的注意力集中在可计算的可计算集合上，因为它们是由算法生成的，因此最容易由可计算函数近似。 第二个目标是研究可计算性与其他数学对象的关系，例如与皮亚诺算术模型的关系，与代数结构的关系，例如与布尔代数的关系，以及与特殊理论的关系，例如与完全超越理论的关系。 对于代数结构，一般的问题是确定哪些信息可以被编码到该结构的同构类型中。 其根本目的是加深我们对可计算性及其与数学和计算机科学结构的关系的理解。 在20世纪30年代，图灵、丘奇、克莱因、哥德尔和其他人提出了可计算函数的各种定义。 他们很快被证明是等价的，他们（特别是图灵的模型）有助于在战争期间的发展高速数字计算机。 这些模型可能会受到时间和空间等计算资源的限制，并导致计算复杂性，这是现代计算机科学的重要组成部分。 可计算性和算法现在渗透到我们生活的许多方面。 现代可计算性和复杂性的研究者是图灵和哥德尔等创始人的继承人，因为他们试图对现代数学的可计算内容进行分类。

In this project Soare will study computability theory, particularly relative computability (Turing reducibility) of one set from another. The first objective is to study computability on the computably enumerable sets, and to relate their algebraic structure to the degree of information they encode and to the speed with which they can be enumerated with respect to some measure of computational complexity. Here attention is focused on the computably enumerable sets because they are generated by an algorithm, and hence most easily approximated by a computable function. The second objective is to study the relationship of computability to other mathematical objects, for example to models of Peano arithmetic, and to algebraic structures, such as Boolean algebras, and models of special theories like totally transcendental ones. For algebraic structures, the general problem is to determine exactly what information can be coded into the isomorphism type of that structure. The fundamental aim is to deepen our understanding of computability and its relation to structures in mathematics and computer science. In the 1930's various definitions of computable function were proposed by Turing, Church, Kleene, Goedel, and others. They were soon proved equivalent and they (particularly Turing's model) contributed during the war to the development of high speed digital computers. These models can be restricted with respect to computing resources such as time and space and give rise to computational complexity, an important part of modern computer science. Computability and algorithms now permeate many aspects of our lives. Modern researchers in computability and complexity are heirs to the founders like Turing and Goedel in that they are trying to classify the computable content of modern mathematics.