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在数学逻辑领域工作，称为计算性理论。计算理论的中心主题是图灵机与确定性之间的关系。 非正式地，图灵机是一台具有无限时间和内存的计算机。 我们说，如果Turing Machine停止使用输入X，则Turing Machine接受了自然的数字X。我们说，自然数的子集a是可以计算的。 对于Cholak，可确定性或表现性意味着公式，主要是在一阶逻辑上，尽管很多时候我们将不得不转向更强的逻辑。 算术相关的可计算性和确定性的帖子的经典结果是，可计算的枚举集是可以通过表单的公式来定义的集合“存在数字x，以使某些可计算的关系保留x。