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;
resource-bounded 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.
Written by two experts in the field, this is the only
comprehensive and unified treatment of the
central ideas and their applications of Kolmogorov complexity---the
theory dealing with the quantity of information in individual objects.
Kolmogorov complexity is known variously as `algorithmic
information', `algorithmic entropy', `Kolmogorov-Chaitin
complexity', `descriptional complexity', `shortest program length',
`algorithmic randomness', and others.
The book is ideal for advanced undergraduate students, graduate students
and researchers in computer science, mathematics, cognitive sciences,
artificial intelligence, philosophy, statistics and physics.
The book is self contained in the sense that it contains the basic requirements
of computability theory, probability theory, information theory, and coding.
Included are also numerous problem sets, comments, source references and hints
to the solutions of problems, course outlines for classroom use, as well as a
great deal of new material not included in the first edition.
Preface to the First Edition v
How to Use This Book viii
Preface to the Second Edition xii
Outlines of One-Semester Courses xii
List of Figures xix
1 Preliminaries 1
1.1 A Brief Introduction 1
1.2 Prerequisites and Notation 6
1.3 Numbers and Combinatorics 8
1.4 Binary Strings 12
1.5 Asymptotic Notation 15
1.6 Basics of Probability Theory 18
1.7 Basics of Computability Theory 24
1.8 The Roots of Kolmogorov Complexity 47
1.9 Randomness 49
1.10 Prediction and Probability 59
1.11 Information Theory and Coding 65
1.12 State Symbol Complexity 84
1.13 History and References 86
2 Algorithmic Complexity 93
2.1 The Invariance Theorem 96
2.2 Incompressibility 108
2.3 C as an Integer Function 119
2.4 Random Finite Sequences 127
2.5 *Random Infinite Sequences 136
2.6 Statistical Properties of Finite Sequences 158
2.7 Algorithmic Properties of 167
2.8 Algorithmic Information Theory 179
2.9 History and References 185
3 Algorithmic Prefix Complexity 189
3.1 The Invariance Theorem 192
3.2 *Sizes of the Constants 197
3.3 Incompressibility 202
3.4 K as an Integer Function 206
3.5 Random Finite Sequences 208
3.6 *Random Infinite Sequences 211
3.7 Algorithmic Properties of 224
3.8 *Complexity of Complexity 226
3.9 *Symmetry of Algorithmic Information 229
3.10 History and References 237
4 Algorithmic Probability 239
4.1 Enumerable Functions Revisited 240
4.2 Nonclassical Notation of Measures 242
4.3 Discrete Sample Space 245
4.4 Universal Average-Case Complexity 268
4.5 Continuous Sample Space 272
4.6 Universal Average-Case Complexity, Continued 307
4.7 History and References 307
5 Inductive Reasoning 315
5.1 Introduction 315
5.2 Solomonoff's Theory of Prediction 324
5.3 Universal Recursion Induction 335
5.4 Simple Pac-Learning 339
5.5 Hypothesis Identification by Minimum Description Length 351
5.6 History and References 372
6 The Incompressibility Method 379
6.1 Three Examples 380
6.2 High- Probability Properties 385
6.3 Combinatorics 389
6.4 Kolmogorov Random Graphs 396
6.5 Compact Routing 404
6.6 Average-Case Complexity of Heapsort 412
6.7 Longest Common Subsequence 417
6.8 Formal Language Theory 420
6.9 Online CFL Recognition 427
6.10 Turing Machine Time Complexity 432
6.11 Parallel Computation 445
6.12 Switching Lemma 449
6.13 History and References 452
7 Resource-Bounded Complexity 459
7.1 Mathematical Theory 460
7.2 Language Compression 476
7.3 Computational Complexity 488
7.4 Instance Complexity 495
7.5 Kt Complexity and Universal Optimal Search 502
7.6 Time-Limited Universal Distributions 506
7.7 Logical Depth 510
7.8 History and References 516
8 Physics, Information, and Computation 521
8.1 Algorithmic Complexity and Shannon's Entropy 522
8.2 Reversible Computation 528
8.3 Information Distance 537
8.4 Thermodynamics 554
8.5 Entropy Revisited 565
8.6 Compression in Nature 583
8.7 History and References 586
If you are seriously interested in using the text in the course,
contact Springer-Verlag's Editor for Computer Science, Martin
Gilchrist, for a complimentary copy.
Martin Gilchrist marting at springer-sc.com
Suite 200, 3600 Pruneridge Ave. (408) 249-9314
Santa Clara, CA 95051
If you are interested in the text but won't be teaching a course,
we understand that Springer-Verlag sells the book, too.
To order, call toll-free 1-800-SPRINGER (1-800-777-4643); N.J.
residents call 201-348-4033. For information regarding
examination copies for course adoptions, write Springer-Verlag
New York, Inc. , 175 Fifth Avenue, New York,NY 10010.
You can order through the Web site: "http://www.springer-ny.com/"
For U.S.A./Canada/Mexico- e-mail: orders at springer-ny.com or fax an
order form to: 201-348-4505.
For orders outside U.S.A./Canada/Mexico send this form to: orders at springer.de
Or call toll free: 800-SPRINGER - 8:30 am to 5:30 pm ET (that's 777-4643 and
201-348-4033 in NJ). Write to Springer-Verlag New York, Inc., 175 Fifth Avenue,
New York, NY, 10010.
Visit your local scientific bookstore. Mail payments may be made by check,
purchase order, or credit card (see note below). Prices are payable in U.S.
currency or its equivalent and are subject to change without notice. Remember,
your 30-day return privilege is always guaranteed!
Your complete address is necessary to fulfill your order.