Constructive dimension equals Kolmogorov complexity

DOI10.1016/J.IPL.2004.09.023zbMATH Open1173.68542OpenAlexW2046221643MaRDI QIDQ835015FDOQ835015

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

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

zbMATH Keywords

theory of computationKolmogorov complexityconstructive dimensionLevin's universal semi-measure

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

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

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)