Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1169.03034
Nies, André
Computability and randomness. (English)
[B] Oxford Logic Guides 51. Oxford: Oxford University Press. xv, 433~p. \sterling~55.00 (2009). ISBN 978-0-19-923076-1/hbk

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.
[Cristian S. Calude (Auckland)]

MSC 2000:: *03D32
68Q30 Algorithmic information theory
03-02 Research monographs (mathematical logic)
68-02 Research monographs (computer science)

Keywords: random strings; random sequences; random sets; descriptive complexity; lowness; $K$-triviality; algorithmic information theory

Cited in: Zbl 1237.03027 Zbl 1235.68086 Zbl 1169.03033

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]