Algorithmic randomness and complexity.

*(English)*Zbl 1221.68005
Theory and Applications of Computability. New York, NY: Springer (ISBN 978-0-387-95567-4/hbk; 978-0-387-68441-3/ebook). xxviii, 855 p. (2010).

The book is an encyclopedia on algorithmic randomness theory (ART). It covers almost all the subfields of ART which have grown enormously in recent time due to the applications of classical computability (or recursion) theory.

The book begins with some necessary knowledge from classical computability theory and algorithmic information theory. Some of Solovay’s unpublished deep results relating \(C\) and \(K\) can be found here. The second part focuses on classifying randomness notions. One of the most successful applications of computability theory is the characterization of the different randomness notions by investigating the distributions of the Turing degrees of the randomness notions. The third part focuses on relativized randomness notions. It begins with the study of Kolmogorov complexity of randomness notions. Though it is still an open problem whether stronger randomness notions mean higher Kolmogorov complexity, much progress has been made. Then the lowness notions are introduced. The proof of the landmark result that lowness, triviality and random basis coincide can be found here. Some results concerned with effective dimension are also presented in this part. The last part is a little bit diverse. It includes the strong jump traceability, the \(\Omega\)-operator and the Kolmogorov complexity of c.e. sets.

Though the book was written carefully (it took the authors about 10 years to write it), there are numerous typos and errors. An up-to-date errata list can be found on the second author’s homepage (http://math.uchicago.edu/~drh/arc.html).

The book begins with some necessary knowledge from classical computability theory and algorithmic information theory. Some of Solovay’s unpublished deep results relating \(C\) and \(K\) can be found here. The second part focuses on classifying randomness notions. One of the most successful applications of computability theory is the characterization of the different randomness notions by investigating the distributions of the Turing degrees of the randomness notions. The third part focuses on relativized randomness notions. It begins with the study of Kolmogorov complexity of randomness notions. Though it is still an open problem whether stronger randomness notions mean higher Kolmogorov complexity, much progress has been made. Then the lowness notions are introduced. The proof of the landmark result that lowness, triviality and random basis coincide can be found here. Some results concerned with effective dimension are also presented in this part. The last part is a little bit diverse. It includes the strong jump traceability, the \(\Omega\)-operator and the Kolmogorov complexity of c.e. sets.

Though the book was written carefully (it took the authors about 10 years to write it), there are numerous typos and errors. An up-to-date errata list can be found on the second author’s homepage (http://math.uchicago.edu/~drh/arc.html).

Reviewer: Liang Yu (Nanjing)

##### MSC:

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |

03D32 | Algorithmic randomness and dimension |

68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |