Effective fractal dimensions

DOI10.1002/malq.200310127zbMath1058.03044OpenAlexW1973073907WikidataQ29399428 ScholiaQ29399428MaRDI QIDQ3159402

Jack H. Lutz

Publication date: 16 February 2005

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310127

zbMATH Keywords

entropycomputational complexitymartingalesHausdorff dimensionKolmogorov complexitypacking dimensionrandom sequencesconstructive dimensionresource-bounded dimensiongalescircuit-size complexityAlgorithmic information theorypolynomial-time degrees

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hausdorff and packing measures (28A78) Theory of numerations, effectively presented structures (03D45)

Related Items

Computability versus exact computability of martingales, The Typical Constructible Object, 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, Dimension is compression, Bounded Pushdown Dimension vs Lempel Ziv Information Density, ALGORITHMS FOR FRACTAL DIMENSION CALCULATION, Base invariance of feasible dimension, Representation of maxitive measures: An overview, Martingale families and dimension in P, Solovay reducibility and continuity, The power of backtracking and the confinement of length, Generic density and small span theorem, Completeness, Compactness, Effective Dimensions, Complex network dimension and path counts, Dimension, entropy rates, and compression, Unnamed Item, Constructive dimension and Turing degrees, Relative Kolmogorov complexity and geometry, Calibrating Randomness, Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• Small Spans in Scaled Dimension