An Introduction to Kolmogorov Complexity and Its Applications
- ISBN-10
- 1475738609
- ISBN-13
- 9781475738605
- Series
- An Introduction to Kolmogorov Complexity and Its Applications
- Category
- Computers
- Pages
- 550
- Language
- English
- Published
- 2013-04-18
- Publisher
- Springer Science & Business Media
- Authors
- Ming Li, Paul Vitanyi
Description
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.
Get the book
Other editions
-
- 2013-03-09
- 637 pages
- Ebook
- Springer Science & Business Media
-
- 2009-03-18
- 792 pages
- Ebook
- Springer Science & Business Media
-
- 1997-02-27
- 670 pages
- Paperback
- Springer Science & Business Media
-
- 2019-06-26
- 834 pages
- Paperback
- Springer
Similar books
-
An Introduction to Kolmogorov Complexity and Its Applications
By Ming Li, Paul Vitanyi“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 ...
-
Algorithmic Randomness and Complexity
By Denis R. Hirschfeldt, Rodney G. DowneyTheorem 2.18.5 (Yates [410], Cooper [76]). Every nonzero c.e. degree bounds a minimal degree. In particular, there are minimal degrees below 0 (which was first shown by Sacks [342]), and hence hyperimmune minimal degrees.
-
An Introduction to Kolmogorov Complexity and Its Applications
By Bernd Reusch“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...
-
Kolmogorov Complexity and Computational Complexity
By Osamu WatanabeIn response, five speakers from the sessions contributed the papers which appear in this book.
-
Kolmogorov Complexity and Algorithmic Randomness
By A. Shen, V. A. Uspensky, N. VereshchaginLooking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why?...
-
Information Theory and Statistical Learning
By Matthias Dehmer, Frank Emmert-StreibThis interdisciplinary text offers theoretical and practical results of information theoretic methods used in statistical learning.
-
Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability
By Marcus HutterDecision Theory = Probability + Utility Theory + + Universal Induction = Ockham + Bayes + Turing = = A Unified View of Artificial Intelligence This book presents sequential decision theory from a novel algorithmic information theory ...
-
The Minimum Description Length Principle
By Peter D. GrünwaldThis introduction to the MDL Principle provides a reference accessible to graduate students and researchers in statistics, pattern classification, machine learning, and data mining, to philosophers interested in the foundations of ...
-
Computation, Physics and Beyond: International Workshop on Theoretical Computer Science, WTCS 2012, Dedicated to Cristian S. Calude on the Occasion...
By Michael J. Dinneen, Bakhadyr Khoussainov, Prof. Andre NiesThis Festschrift volume has been published in honor of Cristian Calude on the occasion of his 60th birthday and contains contributions from invited speakers and regular papers presented at the International Workshop on Theoretical Computer ...
-
Computational Complexity: A Modern Approach
By Sanjeev Arora, Boaz BarakNew and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students.