Fri Nov 20, 2009
60 Evans Hall, 4:10–6 PM
Denis R. Hirschfeldt (University of Chicago)
Lowness Properties and Cost Functions
One of the byproduts of recent developments in the theory of algorithmic randomness is an increased interest in notions of computability-theoretic lowness. We will focus on two such notions: K-triviality, which is a natural notion of “randomness-theoretic weakness” with a number of interesting characterizations, and strong jump traceability, which has a more combinatorial definition but is also strongly connected to algorithmic randomness. In particular, we will see how these notions can be characterized in terms of two other powerful ideas arising from the theory of algorithmic randomness: cost functions and diamond classes. We will use these themes to explain some of the issues of current interest in the rapidly developing area of algorithmic randomness, including a discussion of some major open questions.