Computability Theory and Logic

可计算性理论和逻辑

• 批准号: 9802619
• 负责人: Robert Soare
• 金额: $ 9.51万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-01 至 2001-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9802619&HistoricalAwards=false
• 关键词: Computability; Theory; Logic

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.

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