## An Introduction to Kolmogorov Complexity and Its Applications"The book is outstanding and admirable in many respects. ... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field." Journal of Symbolic Logic 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 book presents a thorough treatment of the subject with a wide range of illsutrative applications. Such applications include the randomeness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computationla learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. the book is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and himnts to solutions of problems. In this new edition the authors have added new material on circuit theory, distributed algorithms, data compression, and other topics. |

### 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