Topics in Computability Theory

可计算性理论专题

• 批准号: 0800198
• 负责人: Peter Cholak
• 金额: $ 12.39万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0800198&HistoricalAwards=false
• 关键词: Topics; Computability; Theory

Cholak will study a range of topics in computability theory. All of the Cholak's projects are motivated by the goal of understanding the relationship between computability and definability. For example, Cholak studies automorphisms of the computably enumerable sets. Take two computably enumerable sets A and B; if they are in the same orbit then A and B satisfy the same infinitary formulas. Conversely, if A and B satisfy the same infinitary formulas then A and B are in the same orbit. One of the structures that Cholak will continue to explore is the collection of all computably enumerable sets with the inclusion relation. In addition, Cholak will study what is definable in the collection of all effective closed classes of reals under inclusion and also under Medvedev reducibility which is defined via Turing reducibility. Cholak is also in engaged in other projects involving reverse mathematics and various models of second-order arithmetic, computable structure theory, and effective measure theory and randomness.Cholak works in the area of mathematical logic called computability theory. The central theme in computability theory is the relationship between Turing machines and definability. Informally, a Turing machine is a computer with unlimited time and memory. We say a natural number x is accepted by a Turing machine if the Turing machine halts with input x. We say a subset A of the natural numbers is computably enumerable iff there is a Turing machine that accepts x iff x is in A. A set R is computable iff A and its complement are computably enumerable. For Cholak, definability or expressibility means formulas, mainly in first-order logic, although many times we will have to move to stronger logics. The classical result of Post in arithmetic relating computability and definability is that the computably enumerable sets are the sets that can be defined by a formula of the form "there exists a number x such that some computable relation hold of x.

Cholak将研究可计算性理论中的一系列主题。Cholak的所有项目都是出于理解可计算性和可定义性之间的关系的目标。例如，Cholak研究了可计算可枚举集的自同构。取两个可计算的可枚举集A和B；如果它们在同一轨道上，则A和B满足相同的无穷公式。相反，如果A和B满足相同的无穷公式，则A和B在同一轨道上。Cholak将继续探索的结构之一是具有包含关系的所有可计算可枚举集的集合。此外，Cholak将研究在包含和Medvedev约化(通过图灵约化定义)下的所有有效封闭实数类的集合中什么是可定义的。Cholak还从事其他项目，涉及逆数学和各种模型的二阶算术、可计算结构理论、有效测度论和随机性。Cholak在被称为可计算性理论的数理逻辑领域工作。可计算性理论的中心主题是图灵机和可定义性之间的关系。非正式地说，图灵机是一台拥有无限时间和内存的计算机。我们说一个自然数x是被图灵机接受的，如果图灵机在输入x时停止。我们说自然数的一个子集A是可计算的当且仅当存在一个接受x的图灵机。当x在A中时，集合R是可计算的当且仅当A及其补集是可计算的。对于Cholak来说，可定义性或可表现性意味着公式，主要是在一阶逻辑中，尽管很多时候我们将不得不转向更强的逻辑。Post在关联可计算性和可定义性的算术中的经典结果是，可计算可枚举集是可以由以下形式的公式定义的集：存在一个数x，使得某些可计算关系保持x。