NB: A PDF version of this announcement (suitable for posting) is also available.

Kolmogorov complexity and Martin-Lof randomness

Joseph Miller
Indiana University

Monday, February 14, 2005
Filene Auditorium, 4:10 pm
Tea 3:10 pm, Math Lounge

Abstract: Kolmogorov defined the complexity of a finite binary string to be the length of the shortest program that generates it. Most strings have Kolmogorov complexity close to their lengths; in other words, they cannot be compressed. Such strings are considered to have high information content. Martin-Lof, a student of Kolmogorov, considered the complexity of infinite binary sequences. He defined a sequence to be random if it passes certain effectively presented statistical tests. Levin and Chaitin both modified Kolmogorov complexity to characterize Martin-Lof randomness, while Schnorr gave a characterization in terms of effective betting games. Thus we have three equivalent formulations of randomness arising from three different fundamental intuitions: random sequences are ``unremarkable'', ``incompressible'' and ``unpredictable''.

This talk will focus on some of the main themes of my work on Kolmogorov complexity and Martin-Lof randomness. We will examine the complexity of initial segments of random reals, giving new insight into the behavior of this complexity and applying it to study the ``degrees of randomness" of infinite sequences. Along the way, we are able for the first time to characterize Martin-Lof randomness in terms of Kolmogorov's original complexity measure. We will also contrast the notions of ``information" found in computability theory and algorithmic randomness. For example, we will see that an appropriate upper bound on the computational power of a random sequence actually enforces a lower bound on its degree of randomness. Similarly, there are connections between high initial segment complexity and low computational power.

This talk will be accessible to graduate students.