Kolmogorov Complexity and Algorithmic Randomness
- ISBN-10
- 1470431823
- ISBN-13
- 9781470431822
- Category
- Computational complexity
- Pages
- 511
- Language
- English
- Published
- 2017-11-02
- Publisher
- American Mathematical Soc.
- Authors
- A. Shen, V. A. Uspensky, N. Vereshchagin
Description
Looking 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? The answer is provided by algorithmic information theory: because the sequence is compressible, that is, it has small complexity or, equivalently, can be produced by a short program. This idea, going back to Solomonoff, Kolmogorov, Chaitin, Levin, and others, is now the starting point of algorithmic information theory. The first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part covers some recent work done by participants of the “Kolmogorov seminar” in Moscow (started by Kolmogorov himself in the 1980s) and their colleagues. This book contains numerous exercises (embedded in the text) that will help readers to grasp the material.
Get the book
Other editions
-
- 2022-05-18
- 511 pages
- Ebook
- American Mathematical Society
Similar books
-
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.
-
Algorithmic Randomness and Complexity
By Denis R. Hirschfeldt, Rodney G. DowneyComputability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.
-
Kolmogorov Complexity and Algorithmic Randomness
By A. ShenThe first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part cover.
-
An Introduction to Kolmogorov Complexity and Its Applications
By Ming Li, Paul VitanyiWe 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.
-
An Introduction to Kolmogorov Complexity and Its Applications
By Ming Li, Paul VitanyiThe text covers both the fundamental concepts and the most important practical applications, supported by a wealth of didactic features.
-
Computability and Randomness
By André NiesThe book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability.
-
Randomness Through Computation: Some Answers, More Questions
By Hector ZenilThis review volume consists of an indispensable set of chapters written by leading scholars, scientists and researchers in the field of Randomness, including related subfields specially but not limited to the strong developed connections to ...
-
Algorithmic Randomness: Progress and Prospects
By Johanna N. Y. Franklin, Christopher P. PorterSurveys on recent developments in the theory of algorithmic randomness and its interactions with other areas of mathematics.
-
Aspects of Kolmogorov Complexity the Physics of Information
By Bradley S. TiceThe text also examines monochromatic and chromatic symbols and both theoretical and applied aspects of data compression as they relate to the transmission and storage of information.
-
Randomness and Complexity: From Leibniz to Chaitin
By Gregory J. Chaitin, Cristian CaludeThe book is a collection of papers written by a selection of eminent authors from around the world in honour of Gregory Chaitin's 60th birthday. This is a unique volume including technical contributions, philosophical papers and essays.