Computability and randomness. (English) Zbl 1169.03034

Oxford Logic Guides 51. Oxford: Oxford University Press (ISBN 978-0-19-923076-1/hbk). xv, 433 p. (2009).
The book presents recent results in algorithmic information theory. It contains the following chapters: 1. The complexity of sets; 2. The descriptive complexity of strings; 3. Martin-Löf randomness and invariants; 4. Diagonally noncomputable functions; 5. Lowness properties and \(K\)-triviality; 6. Some advanced computability theory; 7. Randomness and betting strategies; 8. Classes of computational complexity; 9. Higher computability and randomness. The book includes many exercises (some with solutions).
Written by a researcher who contributed with significant results to the field, the treatment is mathematical rigourous, with many open problems, and an up-dated list of references. The book is suited for advanced courses and research.


03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
68-02 Research exposition (monographs, survey articles) pertaining to computer science