Kolmogorov Complexity and Algorithmic Randomness

DOI10.1090/surv/220zbMath1435.68015OpenAlexW2763382833MaRDI QIDQ4599290

Alexander Shen, Nikolai K. Vereshchagin, Vladimir A. Uspensky

Publication date: 28 December 2017

Published in: Mathematical Surveys and Monographs (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/surv/220

zbMATH Keywords

algorithmic information theoryalgorithmic randomnessdescriptive complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Descriptive complexity and finite models (68Q19) Algorithmic randomness and dimension (03D32)

Related Items (45)

Randomness extraction in computability theory ⋮ The Normalized Algorithmic Information Distance Can Not Be Approximated ⋮ The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite ⋮ Randomness Tests: Theory and Practice ⋮ Non-Algorithmic Theory of Randomness ⋮ Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ The Intersection of Algorithmically Random Closed Sets and Effective Dimension ⋮ Busy Beavers and Kolmogorov Complexity ⋮ Some properties of antistochastic strings ⋮ $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial ⋮ Continuous randomness via transformations of 2-random sequences ⋮ Bayesian definition of random sequences with respect to conditional probabilities ⋮ Approximating Kolmogorov complexity ⋮ Martingales in the Study of Randomness ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Conditional probabilities and van Lambalgen's theorem revisited ⋮ Some games on Turing machines and power from random strings ⋮ Inequalities for entropies and dimensions ⋮ Extraction rates of random continuous functionals ⋮ Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics) ⋮ Algorithmic Statistics: Forty Years Later ⋮ Information disclosure in the framework of Kolmogorov complexity ⋮ A new approach to mathematical statistics involving the number of degrees of freedom, temperature, and symplectically conjugate quantities ⋮ Unnamed Item ⋮ On the Complexity and Dimension of Continuous Finite-Dimensional Maps ⋮ Proofs of conservation inequalities for Levin's notion of mutual information of 1974 ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ An operational characterization of mutual information in algorithmic information theory ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Randomness deficiencies ⋮ Unnamed Item ⋮ Finite-state independence ⋮ Algorithmic search in group theory ⋮ Descriptive complexity of computable sequences revisited ⋮ Putnam's diagonal argument and the impossibility of a universal learning machine ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Vladimir Andreevich Uspensky (27/11/1930–27/6/2018) ⋮ A theory of incremental compression ⋮ Complexity-based permutation entropies: from deterministic time series to white noise ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Individual codewords ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ Predictions and algorithmic statistics for infinite sequences

This page was built for publication: Kolmogorov Complexity and Algorithmic Randomness