Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))

Abstract

The string 111111111111 looks "less random" then the string 100110001001. Kolmogorov complexity makes this intuitive notion of randomness rigorous. Once this is done, new questions arise and some old questions can be answered. This book spends half of its time making these notions rigorous, and the other half applying them. More precisely: