Topics in Computability Theory

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

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.