Preface to the First Edition |
Preface to the Second Edition |
Preface to the Third Edition |
How to Use This Book |
Outlines of One-Semester Courses |
Contents |
List of Figures |
Preliminaries / 1: |
A Brief Introduction / 1.1: |
Prerequisites and Notation / 1.2: |
Numbers and Combinatorics / 1.3: |
Binary Strings / 1.4: |
Asymptotic Notation / 1.5: |
Basics of Probability Theory / 1.6: |
Basics of Computability Theory / 1.7: |
The Roots of Kolmogorov Complexity / 1.8: |
Randomness / 1.9: |
Prediction and Probability / 1.10: |
Information Theory and Coding / 1.11: |
State × Symbol Complexity / 1.12: |
History and References / 1.13: |
Algorithmic Complexity / 2: |
The Invariance Theorem / 2.1: |
Incompressibility / 2.2: |
C as an Integer Function / 2.3: |
Random Finite Sequences / 2.4: |
*Random Infinite Sequences / 2.5: |
Statistical Properties of Finite Sequences / 2.6: |
Algorithmic Properties of C / 2.7: |
Algorithmic Information Theory / 2.8: |
Algorithmic Prefix Complexity / 2.9: |
*Sizes of the Constants / 3.1: |
K as an Integer Function / 3.3: |
Algorithmic Properties of K / 3.5: |
*Complexity of Complexity / 3.8: |
*Symmetry of Algorithmic Information / 3.9: |
Algorithmic Probability / 3.10: |
Semicomputable Functions Revisited / 4.1: |
Measure Theory / 4.2: |
Discrete Sample Space / 4.3: |
Universal Average-Case Complexity / 4.4: |
Continuous Sample Space / 4.5: |
Universal Average-Case Complexity, Continued / 4.6: |
Inductive Reasoning / 4.7: |
Introduction / 5.1: |
Solomonoff's Theory of Prediction / 5.2: |
Simple Pac-Learning / 5.3: |
Hypothesis Identification by MDL / 5.4: |
Nonprobabilistic Statistics / 5.5: |
The Incompressibility Method / 5.6: |
Three Examples / 6.1: |
High-Probability Properties / 6.2: |
Combinatorics / 6.3: |
Kolmogorov Random Graphs / 6.4: |
Compact Routing / 6.5: |
Average-Case Analysis of Sorting / 6.6: |
Longest Common Subsequence / 6.7: |
Formal Language Theory / 6.8: |
Online CFL Recognition / 6.9: |
Turing Machine Time Complexity / 6.10: |
Communication Complexity / 6.11: |
Circuit Complexity / 6.12: |
Resource-Bounded Complexity / 6.13: |
Mathematical Theory / 7.1: |
Language Compression / 7.2: |
Computational Complexity / 7.3: |
Instance Complexity / 7.4: |
Kt and Universal Search / 7.5: |
Time-Limited Universal Distributions / 7.6: |
Logical Depth / 7.7: |
Physics, Information, and Computation / 7.8: |
Information Theory / 8.1: |
Reversible Computation / 8.2: |
Information Distance / 8.3: |
Normalized Information Distance / 8.4: |
Thermodynamics / 8.5: |
Entropy Revisited / 8.6: |
Quantum Kolmogorov Complexity / 8.7: |
Compression in Nature / 8.8: |
References / 8.9: |
Index |
Preface to the First Edition |
Preface to the Second Edition |
Preface to the Third Edition |