The study of the complexity of infinite random sequences, as illustrated by Martin-Löf’s work on algorithmic randomness, has turned out to be deeply connected to the field of relativized theory of computation degrees. Computability, the field started by Turing and Kleene (among others) several decades ago, has more recently been largely enriched by the study of algorithmic randomness. This field has developed in several directions, from strong connections to information theory to the concept of measure and dimension.
The first chapters of the book are devoted to the basics necessary to understand these deep connections, including tools and concepts from measure theory, classical (finite and infinite) Kolmogorov complexity, and recursion theory. More significantly, the book comprises, for the first time, material from several leading researchers whose work hadn’t been published before due to its cutting-edge nature. This material is transparently integrated into the rest of the book and connected in an eloquent fashion to the rest of the existing literature with great care. The authors devote the remaining chapters to presenting the most up-to-date results in connection to the mentioned areas.
A thorough and systematic study of algorithmic randomness, this long-awaited work is an irreplaceable source of well-presented classic and new results for advanced undergraduate and graduate students, as well as researchers in the field and related areas. The book joins a select number of books in this category. One only needs to look at the book’s index and bibliography to see how much care the authors have put into their work--it is definitely a product of two researchers who love their field. The authors deserve the gift they suggest on page 517.