Computability and randomness.

*(English)*Zbl 1169.03034Oxford Logic Guides 51. Oxford: Oxford University Press (ISBN 978-0-19-923076-1/hbk). xv, 433 p. £ 55.00 (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.

Reviewer: Cristian S. Calude (Auckland)

##### MSC:

03D32 | Algorithmic randomness and dimension |

68Q30 | Algorithmic information theory |

03-02 | Research monographs (mathematical logic) |

68-02 | Research monographs (computer science) |