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.