Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension

DOI10.1016/j.aim.2010.06.024zbMath1214.03030MaRDI QIDQ610681

Joseph S. Miller

Publication date: 10 December 2010

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2010.06.024

zbMATH Keywords

Turing degrees; effective Hausdorff dimension

Mathematics Subject Classification ID

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

03D32: Algorithmic randomness and dimension

Related Items

AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES, Optimal bounds for single-source Kolmogorov extractors, Medvedev degrees of two-dimensional subshifts of finite type, Cone avoiding closed sets, Propagation of partial randomness, Fractal dimension versus process complexity, Randomness for computable measures and initial segment complexity, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Mass problems associated with effectively closed sets, Algorithmically independent sequences, Dimension 1 sequences are close to randoms, Strong Medvedev reducibilities and the KL-randomness problem, On effectively closed sets of effective strong measure zero, Extracting randomness within a subset is hard, A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, Randomness, Computation and Mathematics, MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY, Degrees of Unsolvability: A Tutorial

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructive dimension and Turing degrees
• Effectively closed sets of measures and randomness
• Turing degrees of reals of positive effective packing dimension
• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• Generating quasi-random sequences from semi-random sources
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Kolmogorov complexity and the Recursion Theorem
• Effective fractal dimensions
• Algorithmic Randomness and Complexity
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• A Theory of Program Size Formally Identical to Information Theory
• Diagonally non-recursive functions and effective Hausdorff dimension
• STACS 2004
• The definition of random sequences
• Independent minimum length programs to translate between given strings