Topics in Computability Theory

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

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.