An Introduction to Kolmogorov Complexity and Its Applications

• Main Authors: Li, Ming (Author), Vitányi, Paul (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: New York, NY : Springer New York : Imprint: Springer, 2008.
• Edition: Third Edition.
• Series: Texts in Computer Science,
• Subjects: Mathematics.; Coding theory.; Computers.; Pattern recognition.; Applied mathematics.; Engineering mathematics.; Algorithms.; Statistics.; Applications of Mathematics.; Coding and Information Theory.; Theory of Computation.; Statistical Theory and Methods.; Pattern Recognition.

This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects. New key features and topics in the 3rd edition: * New results on randomness * Kolmogorov's s...

Table of Contents:

• Preliminaries
• Algorithmic Complexity
• Algorithmic Prefix Complexity
• Algorithmic Probability
• Inductive Reasoning
• The Incompressibility Method
• Resource-Bounded Complexity
• Physics, Information, and Computation.