Constructive dimension and Turing degrees

DOI10.1007/S00224-009-9170-1MaRDI QIDQ733739zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, David Doty, Frank Stephan

Publication date 19 October 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0701089

zbMATH Keywords

degreerandomnessTuringextractorconstructive dimension

Mathematics Subject Classification ID

Abstract: This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim_H(S) and constructive packing dimension dim_P(S) is Turing equivalent to a sequence R with dim_H(R) <= (dim_H(S) / dim_P(S)) - epsilon, for arbitrary epsilon > 0. Furthermore, if dim_P(S) > 0, then dim_P(R) >= 1 - epsilon. The reduction thus serves as a *randomness extractor* that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim_H(S) / dim_P(S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim_H(S) = dim_P(S)) such that dim_H(S) > 0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.

Recommendations

• Constructive Dimension and Weak Truth-Table Degrees
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Dimension extractors and optimal decompression
• The arithmetical complexity of dimension and randomness
• Computer Science Logic

Cites work

• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 3930883 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 2216397 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Classical recursion theory. The theory of functions and sets of natural numbers
• Constructive Dimension and Weak Truth-Table Degrees
• Dimension extractors and optimal decompression
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Effective fractal dimensions
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Hausdorff-dimension and weak truth-table reducibility
• Logical Approaches to Computational Barriers
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• Recursively enumerable sets of positive integers and their decision problems
• Reducibility and Completeness for Sets of Integers
• Systems of Logic Based on Ordinals^†
• The dimensions of individual strings and sequences
• Two definitions of fractional dimension

Cited in

(15)

• Logical Approaches to Computational Barriers
• Hausdorff-dimension and weak truth-table reducibility
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Avoiding effective packing dimension 1 below array noncomputable c.e. degrees
• The natural hierarchy and quasi-hierarchy of constructibility degrees
• Limit computability and constructive measure
• Controlling effective packing dimension of \(\Delta_2^0\) degrees
• scientific article; zbMATH DE number 218598 (Why is no real title available?)
• A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
• Dimension extractors and optimal decompression
• Dimension 1 sequences are close to randoms
• Randomness extraction and asymptotic Hamming distance
• Bounded Turing reductions and data processing inequalities for sequences
• Constructive Dimension and Weak Truth-Table Degrees
• Optimal bounds for single-source Kolmogorov extractors

This page was built for publication: Constructive dimension and Turing degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733739)