Constructive dimension and Turing degrees

DOI10.1007/S00224-009-9170-1zbMATH Open1183.68281arXivcs/0701089OpenAlexW2082702745MaRDI QIDQ733739FDOQ733739

Authors: Laurent Bienvenu, David Doty, Frank Stephan 

Publication date: 19 October 2009

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

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.

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

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

zbMATH Keywords

degreerandomnessTuringextractorconstructive dimension

Mathematics Subject Classification ID

Cites Work

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

Cited In (13)

• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
• The natural hierarchy and quasi-hierarchy of constructibility degrees
• Limit computability and constructive measure
• How much randomness is needed for statistics?
• Constructive Dimension and Weak Truth-Table Degrees
• Title not available (Why is that?)
• Dimension extractors and optimal decompression
• Hausdorff-dimension and weak truth-table reducibility
• Dimension 1 sequences are close to randoms
• Logical Approaches to Computational Barriers
• AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. 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)