On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line

DOI10.1016/S0022-0000(05)80073-XzbMath0824.68054OpenAlexW2033617538MaRDI QIDQ1342862

Juris Hartmanis, Jin-Yi Cai

Publication date: 15 January 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80073-x

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

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

Related Items

Finite-state dimension, Constructive dimension equals Kolmogorov complexity, The dimensions of individual strings and sequences, A Correspondence Principle for Exact Constructive Dimension, The Kolmogorov complexity of infinite words, Exact constructive and computable dimensions, Dimensions of Points in Self-similar Fractals, Dimension is compression, Fractal Intersections and Products via Algorithmic Dimension, Subcomputable Hausdorff function dimension, Irrationality exponent, Hausdorff dimension and effectivization, Translating the Cantor set by a random real, Effective Hausdorff dimension in general metric spaces, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, On the Kolmogorov Complexity of Continuous Real Functions, Calibrating Randomness, On the computability of fractal dimensions and Hausdorff measure, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Kolmogorov-Loveland randomness and stochasticity, Algorithmic Fractal Dimensions in Geometric Measure Theory, The Kolmogorov complexity of real numbers.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On the sum of digits of real numbers represented in the dyadic system. (On sets of fractional dimensions II.)
• Complex analytic dynamics on the Riemann sphere
• A Theory of Program Size Formally Identical to Information Theory
• On the Length of Programs for Computing Finite Binary Sequences
• Differentiable dynamical systems
• A formal theory of inductive inference. Part II