Constructive dimension equals Kolmogorov complexity

DOI10.1016/j.ipl.2004.09.023zbMath1173.68542OpenAlexW2046221643MaRDI QIDQ835015

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

Kolmogorov complexitytheory of computationconstructive dimensionLevin's universal semi-measure

Mathematics Subject Classification ID

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

Related Items

Randomness and reducibility, The Kolmogorov complexity of infinite words, Automatic Kolmogorov complexity, normality, and finite-state dimension revisited, Exact constructive and computable dimensions, Algorithmically Independent Sequences, Random sequences with respect to a measure defined by two linear fractional transformations, Fractal dimension versus process complexity, On Oscillation-free ε-random Sequences, Algorithmically independent sequences, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension, Randomness and Computability: Open Questions, Calibrating Randomness, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gales suffice for constructive dimension
• The complexity and effectiveness of prediction algorithms
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• The Kolmogorov complexity of real numbers.
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Dimension in Complexity Classes
• 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