Around Kolmogorov complexity: basic notions and results

DOI10.1007/978-3-319-21852-6_7MaRDI QIDQ2805718zbMATH OpenOpenAlexWikidataFDO

Authors A. Shen

Publication date 13 May 2016

Published in Measures of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.04955

zbMATH Keywords

survey paperKolmogorov complexityalgorithmic randomnesscomputabilityeffective Hausdorff dimension

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. There are several textbooks and monographs devoted to this theory where one can find the detailed exposition of many difficult results as well as historical references. However, it seems that a short survey of its basic notions and main results relating these notions to each other, is missing. This report attempts to fill this gap and covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness (Martin-L"of randomness, Mises--Church randomness), effective Hausdorff dimension. We prove their basic properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity, complexity characterization for effective dimension) and show some applications (incompressibility method in computational complexity theory, incompleteness theorems). It is based on the lecture notes of a course at Uppsala University given by the author.

Recommendations

• Kolmogorov complexity in perspective. I: Information theory and randomness
• Kolmogorov complexity as a language
• scientific article; zbMATH DE number 107774
• scientific article; zbMATH DE number 176218
• Algorithmic Complexity and Randomness: Recent Developments

Cited in

(26)

• An additivity theorem for plain Kolmogorov complexity
• Kolmogorov Complexity and Algorithmic Randomness
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• Complexity and randomness
• Kolmogorov Complexity: Sources, Theory and Applications
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• scientific article; zbMATH DE number 2196513 (Why is no real title available?)
• A note on the Kolmogorov data complexity and nonuniform logical definitions
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• Kolmogorov complexity as a language
• Normality, randomness and Kolmogorov complexity of continued fractions
• Busy beavers and Kolmogorov complexity
• scientific article; zbMATH DE number 3930881 (Why is no real title available?)
• scientific article; zbMATH DE number 7378319 (Why is no real title available?)
• Why Kolmogorov complexity?
• The deluge of spurious correlations in big data
• Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers
• Kolmogorov complexity in perspective. I: Information theory and randomness
• Towards an axiomatic system for Kolmogorov complexity
• Dimension 1 sequences are close to randoms
• Universal probability-free prediction
• Algorithmic statistics: forty years later
• scientific article; zbMATH DE number 176218 (Why is no real title available?)
• scientific article; zbMATH DE number 4086981 (Why is no real title available?)
• Randomness Tests: Theory and Practice
• Some notes on Rissanen's stochastic complexity

This page was built for publication: Around Kolmogorov complexity: basic notions and results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805718)