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.
While supported by this research grant, Cholak worked on issues related non computability in mathematics. For example, it is know that if you have 6 people in a room 3 of them will be friends or 3 of them will not know each other, i.e. they will be nonfriends. What can one computable if one has an infinite set of friends or nonfriends? For example, it is now know that one cannot compute an random real. Does this infinite set of friends or nonfriends allow one to proof new results. All of the Cholak's projects are motivated by the goal of understanding the relationship between computability and definability. For example, Cholak also studied automorphisms of the computably enumerable sets. A set is computability enumerable if a computer can list out the elements of the set. 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. During the period supported by this grant, Cholak with his postdocs discovered new definable sets in the structure of the computably enumerable sets. During the time Cholak held this grant, he graduated 5 Ph.D.s. He wrote 6 papers himself and gave over 15 talks all over the world.
