An introduction to Kolmogorov complexity and its applications
With this book, the authors are trying to present in a unified treatment an introduction to the central ideas and their applications of the Kolmogorov Complexity, the theory dealing with the quantity of information in individual objects. This book is appropriate for either a one- or two-semester introductory course in departments of computer science, mathematics, physics, probability theory and statistics, artificial intelligence, and philosophy. Although the mathematical theory of Kolmogorov complexity contains sophisticated mathematics, the amount of math one needs to know to apply the notions in widely divergent areas, is very little. The authors' purpose is to develop the theory in detail and outline a wide range of illustrative applications. This book is an attempt to grasp the mass of fragmented knowledge of this fascinating theory. Chapter 1 is a compilation of material on the diverse notations and disciplines we draw upon in order to make the book self-contained. The mathematical theory of Kolmogorov complexity is treated in chapters 2-4; the applications are treated in chapters 4-8.
12 pages matching pac-learnable in this book
Results 1-3 of 12
What people are saying - Write a review
We haven't found any reviews in the usual places.
Sections 1 1 1 2 1 4 except Section 1 4
17 other sections not shown
A.N. Kolmogorov additive constant algorithm Bernoulli process bits code word length Comments computation Consider countably decodable defined Definition denote descriptional complexity effective enumeration element encoding entropy enumerable function enumerable semimeasure Equation Example Exercise exists follows formula Gacs given halting Hence Hint for Item Ibid incompressible inequality infinite binary sequence initial segment input integers Invariance Theorem Km(x Kolmogorov complexity Kraft's Inequality L.A. Levin Lemma log log logarithm logn Math mathematical natural numbers notion object Occam's razor outcome output pac-learnable partial recursive function polynomial prefix machine prefix-code prior probability priori probability probability distribution probability theory proof prove random infinite sequences random sequences random with respect real number recursive measure recursively enumerable set sample space satisfies sequential x-test shortest program Show Solomonoff Solovay source word strings of length subset symbols tape Theorem 2.1 tion total recursive Turing machine uniform distribution uniform measure universal enumerable zero