Turing degrees of reals of positive effective packing dimension

DOI10.1016/J.IPL.2008.05.028zbMath1191.68304OpenAlexW1978758779MaRDI QIDQ975475

Noam Greenberg, Rodney G. Downey

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.05.028

zbMATH Keywords

theory of computationeffective packing dimensionarray nonrecursive degrees

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items (11)

Bounded Randomness ⋮ AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Compressibility and Kolmogorov complexity ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Lowness for bounded randomness ⋮ Computable analogs of cardinal characteristics: prediction and rearrangement ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ A uniform version of non-\(\mathrm{low}_{2}\)-ness ⋮ Integer valued betting strategies and Turing degrees

Cites Work

• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• Dimension extractors and optimal decompression
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Computational randomness and lowness
• Algorithmic Randomness and Complexity
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Category and Measure in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Computability and Randomness
• Constructive Dimension and Weak Truth-Table Degrees
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Turing degrees of reals of positive effective packing dimension