Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
From MaRDI portal
Publication:610681
DOI10.1016/j.aim.2010.06.024zbMath1214.03030OpenAlexW2042295707MaRDI QIDQ610681
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
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)
Related Items
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, Extracting randomness within a subset is hard, AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES, Propagation of partial randomness, Dimension 1 sequences are close to randoms, Growth and irreducibility in path-incompressible trees, On effectively closed sets of effective strong measure zero, Fractal dimension versus process complexity, Randomness for computable measures and initial segment complexity, Medvedev degrees of two-dimensional subshifts of finite type, Algorithmically independent sequences, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Optimal bounds for single-source Kolmogorov extractors, Mass problems associated with effectively closed sets, Cone avoiding closed sets, Strong Medvedev reducibilities and the KL-randomness problem
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
