Though we did not know it at the time, this book’s genesis began with
the arrival of Cris Calude in New Zealand. Cris has always had an intense
interest in algorithmic information theory. The event that led to much of
the recent research presented here was the articulation by Cris of a seemingly
innocuous question. This question goes back to Solovay’s legendary
manuscript [371], and Downey learned of it during a visit made to Victoria
University in early 2000 by Richard Coles, who was then a postdoctoral fellow
with Calude at Auckland University. In effect, the question was whether
the Solovay degrees of left-computably enumerable reals are dense.
At the time, neither of us knew much about Kolmogorov complexity, but
we had a distinct interest in it after Lance Fortnow’s illuminating lectures
[148] at Kaikoura1 in January 2000. After thinking about Calude’s question
for a while, and eventually solving it together with Andr´e Nies [116], we
began to realize that there was a huge and remarkably fascinating area of
research, whose potential was largely untapped, lying at the intersection of
computability theory and the theory of algorithmic randomness.
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.