## An Introduction to Kolmogorov Complexity and Its ApplicationsBriefly, we review the basic elements of computability theory and prob ability theory that are required. Finally, in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This way the stage is set for Chapters 2 and 3, where we introduce the notion of optimal effective descriptions of objects. The length of such a description (or the number of bits of information in it) is its Kolmogorov complexity. We treat all aspects of the elementary mathematical theory of Kolmogorov complexity. This body of knowledge may be called algo rithmic complexity theory. The theory of Martin-Lof tests for random ness of finite objects and infinite sequences is inextricably intertwined with the theory of Kolmogorov complexity and is completely treated. We also investigate the statistical properties of finite strings with high Kolmogorov complexity. Both of these topics are eminently useful in the applications part of the book. We also investigate the recursion theoretic properties of Kolmogorov complexity (relations with Godel's incompleteness result), and the Kolmogorov complexity version of infor mation theory, which we may call "algorithmic information theory" or "absolute information theory. " The treatment of algorithmic probability theory in Chapter 4 presup poses Sections 1. 6, 1. 11. 2, and Chapter 3 (at least Sections 3. 1 through 3. 4). |

### What people are saying - Write a review

User Review - Flag as inappropriate

This is a great book. See reviews on Amazon.

### Contents

Preliminaries | 1 |

12 Prerequisites | 6 |

13 Numbers and Combinaorics | 8 |

14 Binary Stings | 12 |

15 Asymptotic Notation | 15 |

16 Basics of Probability Theory | 18 |

17 Basics of Computability Theory | 24 |

18 The Roots of Kolmogorov Complexity | 47 |

Inductive Reasoning | 315 |

52 Solomonoffs Theory of Prediction | 324 |

53 Universal Recursion Induction | 335 |

54 Simple PacLearning | 339 |

55 Hypothesis Identification by Minimum Description Length | 351 |

56 History and References | 372 |

The Incompressibility Method | 379 |

61 Three Examples | 380 |

19 Randomness | 49 |

110 Prediction and Probability | 59 |

111 Information Theory and Coding | 65 |

112 State x Symbol Complexity | 84 |

113 History and References | 86 |

Algorithmic Complexity | 93 |

21 The Invariance Theorem | 96 |

22 Incompressibility | 108 |

23 C as an Integer Function | 119 |

24 Random Finite Sequences | 127 |

25 Random Infinite Sequences | 136 |

26 Statistical Properties of Finite Sequences | 158 |

27 Algorithmic Properties of C | 167 |

28 Algoithmic Information Theory | 179 |

29 History and References | 185 |

Algorithmic Prefix Complexity | 189 |

31 The Invariance Theorem | 192 |

32 Sizes of the Constants | 197 |

33 Incompressibility | 202 |

34 K as an Integer Function | 206 |

35 Random Finite Sequences | 208 |

36 Random Infinite Sequences | 211 |

37 Algorithmic Properties of K | 224 |

38 Complexity of Complexity | 226 |

39 Symmetry of Algorithmic Information | 229 |

310 History and References | 237 |

Algorithmic Probability | 239 |

41 Enumerable Functions Revisited | 240 |

42 Nonclassical Notation of Measures | 242 |

43 Discrete Sample Space | 245 |

44 Universal AverageCase Complexity | 268 |

45 Continuous Sample Space | 272 |

Universal AverageCase Complexity Continued | 307 |

62 HighProbability Properties | 385 |

63 Combinatorics | 389 |

Graphs | 396 |

65 Compact Routing | 404 |

66 AverageCase Complexity of Heapsort | 412 |

67 Longest Common Subsequence | 417 |

68 Formal Language Theory | 420 |

69 Online CFL Recognition | 427 |

610 Turing Machine Time Complexity | 432 |

611 Parallel Computation | 445 |

612 Switching Lemma | 449 |

613 History and References | 452 |

ResourceBounded Complexity | 459 |

71 Mathematical Theory | 460 |

72 Language Compression | 476 |

73 Computational Complexity | 488 |

74 Instance Complexity | 495 |

75 Kt Complexity and Universal Optimal Search | 502 |

76 TimeLimited Universal Distributions | 506 |

77 Logical Depth | 510 |

78 History and References | 516 |

Physics Information and Computation | 521 |

81 Algorithmic Complexity and Shannons Entropy | 522 |

82 Reversible Computation | 528 |

83 Information Distance | 537 |

84 Thermodynamics | 554 |

85 Entropy Revisited | 565 |

86 Compression in Nature | 583 |

87 History and References | 586 |

References | 591 |

618 | |

### Common terms and phrases

algorithmic entropy Bayes's Rule binary string code word Comments compression computation Consider contains defined Definition denote Descriptional Complexity effective enumeration element encoding enumerable semimeasure Equation Example Exercise finite fixed follows Gacs given graph halting Hence hypothesis i-test incompressibility inequality infinite binary sequence infinite sequences input integers Invariance Theorem Km(x Kolmogorov complexity Kolmogorov random L.A. Levin Lemma log log logarithmic logn lower bound Martin-L6f Math monotone natural numbers nodes notion object optimal outcome output P.M.B. Vitanyi pac-learnable partial recursive function polynomial prefix complexity prefix machine prefix-code probabilistic probability distribution probability theory problem Proc proof prove random sequences randomness deficiency real number recursively enumerable set reversible computation sample space satisfies Section self-delimiting sequential test Shannon-Fano code shortest program Show simulate Solomonoff source word steps strings of length subset tape Theorem tion total recursive uniform measure universal Turing machine upper bound