Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))
William I. Gasarch · ACM SIGACT News · 1997
OverviewThe 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:1. Chapters 1-4 carefully establish the rigorous definitions needed to study randomness.If this were the only goal it would not need four chapters; however, the authors also explore many issues that lead to the definitions and that are consequences of the definitions.2. Chapters 5-7 apply Kolmogorov complexity to computer science; chapter 8 applies it to Physics.Most of the applications only use a small part of what is in chapter 1-4.This is good--if a :reader is only interested in applications they can read these chapters having just learned a few things from chapters 1-4. Summary of ContentsChapter 1 contains motivation for the subject and a quick review of combinatorics, probability, and computability.The treatment is a good refresher course, but is too mature for a first time learner.Chapter 2 defines the complexity of a string and some notions of randomness.Informally, the complexity of a string x is the shortest description of x.We give a formal definition that is equivalent to the one in the book.Definition 2.1 Let (~}¢cz* be an APS (acceptable programming system, i.e., (1) {~}¢ez* contains exactly the partial recursive functions, and (2) the '~r' can be manipulated like code).Let ] be universal for {~¢}¢Ez* (that is, ](o',T) = ~p¢(~-).The complexity oyx given y, relative to f is C/(xly ) = min{l¢l : f(o',y) = x}.Note that ~r tells how to get from y to x since fl'om o and y one can produce x.We also define C/(x) = C/(xlA ).Note that C/(1 n) = logn + 0(1) since all you need to describe 1 n is n, Definition 2.2 Let c E N and x E E*. x is c-incompressible with respect to f if C/(x) > Ixl -c.Intuitively we are seying that the shortest description of x is x itself.This is a notion of randomness.A simple counting argument shows that most strings are c-incompressible.The above definitions seem to depend on the particular f chosen.The next theorem shows that the definitions are actually robust.