Mathematical Surveys and Monographs
Volume: 220;
2017;
511 pp;
Hardcover
MSC: Primary 68; 03; 60; 97;
Print ISBN: 978-1-4704-3182-2
Product Code: SURV/220
List Price: $124.00
AMS Member Price: $99.20
MAA Member Price: $111.60
Electronic ISBN: 978-1-4704-4083-1
Product Code: SURV/220.E
List Price: $124.00
AMS Member Price: $99.20
MAA Member Price: $111.60
You may also like
Supplemental Materials
Kolmogorov Complexity and Algorithmic Randomness
Share this pageA. Shen; V. A. Uspensky; N. Vereshchagin
Looking at a sequence of zeros and ones, we
often feel that it is not random, that is, it is not plausible as an
outcome of fair coin tossing. Why? The answer is provided by
algorithmic information theory: because the sequence is compressible,
that is, it has small complexity or, equivalently, can be produced by a short
program. This idea, going back to Solomonoff, Kolmogorov, Chaitin,
Levin, and others, is now the starting point of algorithmic
information theory.
The first part of this book is a textbook-style exposition of the
basic notions of complexity and randomness; the second part covers
some recent work done by participants of the “Kolmogorov
seminar” in Moscow (started by Kolmogorov himself in the 1980s)
and their colleagues.
This book contains numerous exercises (embedded in the text) that
will help readers to grasp the material.
Readership
Graduate students and researchers interested in topics related to an algorithmic approach to complexity and randomness.
Reviews & Endorsements
This book is an excellent reference for the working mathematician and would also serve well as a text for a graduate course. The exercises fit well into the text and are at an appropriate level.
-- Johanna N. Y. Franklin, Mathematical Reviews
Table of Contents
Table of Contents
Kolmogorov Complexity and Algorithmic Randomness
- Cover Cover11
- Title page iii4
- Contents vii8
- Preface xi12
- Basic notions and notation xv16
- Introduction. What is this book about? 120
- Chapter 1. Plain Kolmogorov complexity 1534
- Chapter 2. Complexity of pairs and conditional complexity 3150
- Chapter 3. Martin-Löf randomness 5372
- Chapter 4. A priori probability and prefix complexity 7594
- 4.1. Randomized algorithms and semimeasures on ℕ 7594
- 4.2. Maximal semimeasures 7998
- 4.3. Prefix machines 81100
- 4.4. A digression: Machines with self-delimiting input 85104
- 4.5. The main theorem on prefix complexity 91110
- 4.6. Properties of prefix complexity 96115
- 4.7. Conditional prefix complexity and complexity of pairs 102121
- Chapter 5. Monotone complexity 115134
- 5.1. Probabilistic machines and semimeasures on the tree 115134
- 5.2. Maximal semimeasure on the binary tree 121140
- 5.3. A priori complexity and its properties 122141
- 5.4. Computable mappings of type Σ→Σ 126145
- 5.5. Monotone complexity 129148
- 5.6. Levin–Schnorr theorem 144163
- 5.7. The random number Ω 157176
- 5.8. Effective Hausdorff dimension 172191
- 5.9. Randomness with respect to different measures 176195
- Chapter 6. General scheme for complexities 193212
- Chapter 7. Shannon entropy and Kolmogorov complexity 213232
- Chapter 8. Some applications 233252
- Chapter 9. Frequency and game approaches to randomness 261280
- 9.1. The original idea of von Mises 261280
- 9.2. Set of strings as selection rules 262281
- 9.3. Mises–Church randomness 264283
- 9.4. Ville’s example 267286
- 9.5. Martingales 270289
- 9.6. A digression: Martingales in probability theory 275294
- 9.7. Lower semicomputable martingales 277296
- 9.8. Computable martingales 279298
- 9.9. Martingales and Schnorr randomness 282301
- 9.10. Martingales and effective dimension 284303
- 9.11. Partial selection rules 287306
- 9.12. Non-monotonic selection rules 291310
- 9.13. Change in the measure and randomness 297316
- Chapter 10. Inequalities for entropy, complexity, and size 313332
- 10.1. Introduction and summary 313332
- 10.2. Uniform sets 318337
- 10.3. Construction of a uniform set 321340
- 10.4. Uniform sets and orbits 323342
- 10.5. Almost uniform sets 324343
- 10.6. Typization trick 326345
- 10.7. Combinatorial interpretation: Examples 328347
- 10.8. Combinatorial interpretation: The general case 330349
- 10.9. One more combinatorial interpretation 332351
- 10.10. The inequalities for two and three strings 336355
- 10.11. Dimensions and Ingleton’s inequality 337356
- 10.12. Conditionally independent random variables 342361
- 10.13. Non-Shannon inequalities 343362
- Chapter 11. Common information 351370
- Chapter 12. Multisource algorithmic information theory 367386
- 12.1. Information transmission requests 367386
- 12.2. Conditional encoding 368387
- 12.3. Conditional codes: Muchnik’s theorem 369388
- 12.4. Combinatorial interpretation of Muchnik’s theorem 373392
- 12.5. A digression: On-line matching 375394
- 12.6. Information distance and simultaneous encoding 377396
- 12.7. Conditional codes for two conditions 379398
- 12.8. Information flow and network cuts 383402
- 12.9. Networks with one source 384403
- 12.10. Common information as an information request 388407
- 12.11. Simplifying a program 389408
- 12.12. Minimal sufficient statistics 390409
- Chapter 13. Information and logic 401420
- 13.1. Problems, operations, complexity 401420
- 13.2. Problem complexity and intuitionistic logic 403422
- 13.3. Some formulas and their complexity 405424
- 13.4. More examples and the proof of Theorem 238 408427
- 13.5. Proof of a result similar to Theorem 238 using Kripke models 413432
- 13.6. A problem whose complexity is not expressible in terms of the complexities of tuples 417436
- Chapter 14. Algorithmic statistics 425444
- Appendix 1. Complexity and foundations of probability 455474
- Probability theory paradox 455474
- Current best practice 455474
- Simple events and events specified in advance 456475
- Frequency approach 458477
- Dynamical and statistical laws 459478
- Are “real-life” sequences complex? 459478
- Randomness as ignorance: Blum–Micali–Yao pseudo-randomness 460479
- A digression: Thermodynamics 461480
- Another digression: Quantum mechanics 463482
- Appendix 2. Four algorithmic faces of randomness 465484
- Bibliography 491510
- Name Index 501520
- Subject Index 505524
- Back Cover Back Cover1534