Constructive dimension equals Kolmogorov complexity

DOI10.1016/J.IPL.2004.09.023MaRDI QIDQ835015zbMATH OpenOpenAlexFDO

Authors Ludwig Staiger

Publication date 27 August 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.09.023

zbMATH Keywords

theory of computationKolmogorov complexityconstructive dimensionLevin's universal semi-measure

Mathematics Subject Classification ID

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

Recommendations

• A Correspondence Principle for Exact Constructive Dimension
• Constructive dimension and Hausdorff dimension: the case of exact dimension
• Exact constructive and computable dimensions
• scientific article; zbMATH DE number 1670880
• The Kolmogorov complexity of infinite words

Cites work

• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 3930883 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1113628 (Why is no real title available?)
• scientific article; zbMATH DE number 3344793 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Dimension in Complexity Classes
• Gales suffice for constructive dimension
• Kolmogorov complexity and Hausdorff dimension
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• Relations between varieties of kolmogorov complexities
• STACS 2004
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Kolmogorov complexity of real numbers.
• The complexity and effectiveness of prediction algorithms
• The dimensions of individual strings and sequences

Cited in

(19)

• Random sequences with respect to a measure defined by two linear fractional transformations
• A perfect set of reals with finite self-information
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Exact constructive and computable dimensions
• On oscillation-free \(\varepsilon\)-random sequences
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy
• Kolmogorov complexity and Hausdorff dimension
• A characterization of constructive dimension
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• The Kolmogorov complexity of infinite words
• Finite state incompressible infinite sequences
• Fractal dimension versus process complexity
• Constructive dimension and Hausdorff dimension: the case of exact dimension
• Algorithmically independent sequences
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• Algorithmically Independent Sequences
• Randomness and reducibility

This page was built for publication: Constructive dimension equals Kolmogorov complexity

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