An Introduction to Kolmogorov Complexity and Its Applications

We are to admit no more causes of natural things (as we are told by New- ton) than such as are both true and sufficient to explain their appearances. This central theme is basic to the pursuit of science, and goes back to the principle known as Occam's razor: "if presented with a choice between indifferent alternatives, then one ought to select the simplest one". Uncon- sciously or explicitly, informal applications of this principle in science and mathematics abound.
How to U se This Book
The technical contents of this book consists of four layers. The main text is the first layer. The second layer consists of examples in the main text. These elaborate the theory developed from the main theorems. The third layer consists of indented smaller font paragraphs interspersed with the main text. The purpose of such paragraphs is to have an explanatory aside, to raise some technical issues which are important but would distract attention from the main narrative, or to point to alternate or related technical issues. Much of the technical contents of the literature on Kolmogorov complexity and related issues appears in the fourth layer, the exercises. When the idea behind a nontrivial exercise is not our own, we have tried to give credit to the person who originated the idea. Corresponding references to the literat ure are usually given in comments to an exercise or in the historical section of that chapter.
Starred sections are not really required for the understanding of the sequel and should be omitted at first reading. The application sections are not starred. The exercises are grouped together at the end of main sections. Each group relates to the material in between it and the previous group.
Each chapter is concluded by an extensive historical section with explicit references. The book is concluded with an exhaustive bibliography on the literature on Kolmogorov complexity and its applications. We added a very detailed index combining the index to notation, the name index, and the concept index. The page number where a not ion is defined first is printed in boldface. The initial part of the Index is an index to notation.