Preface to the Second Edition
When this book was conceived ten years ago,
few scientists realized the width of scope and the
power for applicability of the central ideas. Partially
because of the enthusiastic reception of the first edition,
open problems have been solved and new applications have been
developed. We have added new material on the relation between
data compression and minimum description length induction,
computational learning,
and universal prediction; circuit theory; distributed
algorithmics; instance complexity; CD compression;
computational complexity; Kolmogorov random graphs;
shortest encoding of routing tables in communication networks;
computable universal distributions;
average case properties;
the equality of statistical entropy and expected Kolmogorov complexity;
and so on. Apart from being used by researchers and
as reference work, the book
is now commonly used for graduate courses and seminars.
In recognition of this fact, the second
edition has been produced in textbook style. We have
preserved as much as possible the ordering of
the material as it was in the first edition.
The many exercises bunched together at the ends of
some chapters have been moved to the appropriate sections.
The comprehensive bibliography on Kolmogorov complexity
at the end of the book has been updated, as have
the ``History and References'' sections of the chapters.
Many readers were kind enough to express their appreciation
for the first edition and to send notification of typos, errors,
and comments. Their number is too large to thank them individually,
so we thank them all collectively.