Peter Cholak

Biography

Peter Cholak works in computability theory. In particular, Professor Cholak focuses on the relationship between computability and definability. A classic example is Post’s result that the set of integers accepted by a Turing machine is a $\Sigma^0_1$ definable set in arithmetic. Another example is the result of Cholak and his coauthors that the question of whether two c.e. sets are in the same orbit in the structure of c.e. sets is $\Pi^1_1$ complete. Cholak has also spent a lot of time and energy exploring what is possible in the orbits of c.e. sets. The answer is that basically anything is possible.