AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Kolmogorov Complexity and Algorithmic Randomness
About this Title
A. Shen, LIRMM CRNS, Université de Montpellier, Montpellier, France, V. A. Uspensky, Lomonosov Moscow State University, Moscow, Russia and N. Vereshchagin, Lomonosov Moscow State University, Moscow, Russia
Publication: Mathematical Surveys and Monographs
Publication Year:
2017; Volume 220
ISBNs: 978-1-4704-3182-2 (print); 978-1-4704-4083-1 (online)
DOI: https://doi.org/10.1090/surv/220
MathSciNet review: MR3702040
MSC: Primary 03-02; Secondary 03D32, 60F15, 62A01, 62B10, 68-02, 68Q30
ReadershipTable of Contents
Download chapters as PDF
Front/Back Matter
Chapters
- What is this book about?
- Plain Kolmogorov complexity
- Complexity of pairs and conditional complexity
- Martin-Löf randomness
- A priori probability and prefix complexity
- Monotone complexity
- General scheme for complexities
- Shannon entropy and Kolmogorov complexity
- Some applications
- Frequency and game approaches to randomness
- Inequalities for entropy, complexity, and size
- Common information
- Multisource algorithmic information theory
- Information and logic
- Algorithmic statistics
- Complexity and foundations of probability
- Four algorithmic faces of randomness