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

### Other editions - View all

An Introduction to Kolmogorov Complexity and Its Applications Ming Li,Paul Vitanyi Limited preview - 2013 |

An Introduction to Kolmogorov Complexity and Its Applications Ming Li,Paul Vitanyi Limited preview - 2013 |

### Common terms and phrases

according additive algorithm applications Assume binary binary string bits bound called Comments compression Comput conditional Consider consisting constant construct contains corresponding defined Definition denote describe distribution effective element encoding entropy enumerable equal Equation Example Exercise exists finite fixed follows formal give given graph halting Hence holds incompressibility infinite infinite sequences initial input Item Kolmogorov complexity language least Lemma length Math means measure method natural nodes Notes notion object obtain optimal output partial recursive polynomial positive possible prefix probability problem proof prove random recursive function recursively enumerable reference relation requires respect result reversible sample satisfies semimeasure sense sequence shortest Show simple simulate Source space statistical steps string symbol takes tape term Theorem theory tion Turing machine uniform universal