The unsettling premise behind this whole field is that "randomness" is not a property of how a string was generated but of the string itself: 0101010101 and a coin-flip sequence of the same length are equally probable, yet one is obviously not random. The resolution — a string is random exactly when it cannot be compressed, when no program shorter than the string can output it — is what this book develops from first principles, and it is one of the rare ideas that simultaneously grounds randomness, information, and provability.
What gives the book its character is its lineage: the second half draws directly on the Moscow "Kolmogorov seminar" that Kolmogorov ran from the 1980s, so it carries results and viewpoints that never made it into the standard Western references.
What's Inside
- Two halves, two audiences. Part one is a clean textbook on plain and prefix complexity, the incompressibility method, and Martin-Löf randomness; part two is closer to a research monograph, surveying algorithmic statistics, mutual information, and frontier seminar work.
- Complexity as a proof tool, not just a definition. The incompressibility method turns "a random object exists" into short combinatorial lower-bound proofs — the payoff most readers actually came for.
- It connects fields that rarely sit together. Shannon information, computability, Hausdorff dimension, ergodic theory, and data compression all reappear as facets of one complexity measure.
- Exercises live in the text. Problems are embedded inline rather than appended, so the book assumes you stop and work, not skim.
Who It Fits / When to Skip
Great fit if you want the definitions and the incompressibility method from a primary source, or want the Moscow-school results unavailable elsewhere. Look elsewhere if you need a gentle first pass — it is mathematically demanding and assumes comfort with computability — or if you want applied machine learning; the "Foundation" framing is about theoretical roots, not modeling practice.
