A Kolmogorov complexity characterization of constructive Hausdorff dimension.
From MaRDI portal
Publication:1853096
DOI10.1016/S0020-0190(02)00343-5zbMath1045.68570OpenAlexW2076165639WikidataQ29011744 ScholiaQ29011744MaRDI QIDQ1853096
Publication date: 21 January 2003
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00343-5
Related Items
Randomness and reducibility ⋮ Constructive dimension equals Kolmogorov complexity ⋮ The dimensions of individual strings and sequences ⋮ Randomness, Computation and Mathematics ⋮ The Intersection of Algorithmically Random Closed Sets and Effective Dimension ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ Dimension spectra of lines1 ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ On zeros of Martin-Löf random Brownian motion ⋮ AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Capacitability for Co-Analytic Sets ⋮ A divergence formula for randomness and dimension ⋮ Dimension spectra of random subfractals of self-similar fractals ⋮ Strict process machine complexity ⋮ Compressibility and Kolmogorov complexity ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Projection theorems using effective dimension ⋮ Exact constructive and computable dimensions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dimension is compression ⋮ Connectivity properties of dimension level sets ⋮ Algorithmically Independent Sequences ⋮ Bounding the dimension of points on a line ⋮ Fractal Intersections and Products via Algorithmic Dimension ⋮ Computability theory. Abstracts from the workshop held January 7--13, 2018 ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Solovay reducibility and continuity ⋮ Randomness and Solovay degrees ⋮ Nonlinear dynamics of two-dimensional cardiac action potential duration mapping model with memory ⋮ Fractal dimension versus process complexity ⋮ Connectivity Properties of Dimension Level Sets ⋮ A Divergence Formula for Randomness and Dimension ⋮ Algorithmically independent sequences ⋮ Translating the Cantor set by a random real ⋮ Kolmogorov-Loveland stochasticity and Kolmogorov complexity ⋮ Lowness for effective Hausdorff dimension ⋮ Completeness, Compactness, Effective Dimensions ⋮ Dimension spectra of lines ⋮ Connectedness properties of dimension level sets ⋮ The Dynamics of Cellular Automata in Shift-Invariant Topologies ⋮ Information measures for infinite sequences ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Dimension, entropy rates, and compression ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences ⋮ Bounded Turing reductions and data processing inequalities for sequences ⋮ Pushdown dimension ⋮ Constructive dimension and Turing degrees ⋮ Depth as randomness deficiency ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Dimension extractors and optimal decompression ⋮ Monotonous betting strategies in warped casinos ⋮ Mutual Dimension ⋮ Relative Kolmogorov complexity and geometry ⋮ Randomness and Computability: Open Questions ⋮ Calibrating Randomness ⋮ Cone avoiding closed sets ⋮ Π10 classes with complex elements ⋮ Effective symbolic dynamics, random points, statistical behavior, complexity and entropy ⋮ Kolmogorov-Loveland randomness and stochasticity ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ KL-randomness and effective dimension under strong reducibility
Cites Work
