Cover Image

Kolmogorov complexity and algorithmic randomness /

Bibliographic Details
Main Authors: Shen, A. (Alexander), 1958- (Author), Uspenskiĭ, V. A. (Vladimir Andreevich) (Author), Vereshchagin, Nikolai Konstantinovich, 1958- (Author)
Format: Book
Language:English
Published: Providence, Rhode Island : American Mathematical Society, [2017]
Series:Mathematical surveys and monographs ; no. 220.
Subjects:
Kolmogorov complexity.
Computational complexity.
Information theory.
Computer science > Theory of computing > Algorithmic information theory (Kolmogorov complexity, etc.)
Mathematical logic and foundations > Computability and recursion theory > Algorithmic randomness and dimension.
Probability theory and stochastic processes > Foundations of probability theory > None of the above, but in this section.
Mathematics education > Combinatorics, graph theory, probability theory, statistics > Foundations and methodology of statistics.
Table of Contents:
  • Preface
  • Basic notions and notation
  • Introduction : What is this book about?
  • Plain Kolmogorov complexity - Complexity of pairs and conditional complexity
  • Martin-Löf randomness
  • A priori probability and prefix complexity
  • Monotone complexity
  • General scheme for complexities
  • Shannon entropy and Kolmogorov complexity
  • Some applications
  • Frequency and game approaches to randomness
  • Inequalities for entropy, complexity, and size
  • Common information
  • Multisource algorithmic information theory
  • Information and logic
  • Algorithmic statistics
  • Appendix 1. Complexity and foundations of probability
  • Appendix 2. Four algorithmic faces of randomness.