Paper Info
Title
Constructive Dimension and Turing Degrees
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))−ε, for arbitrary ε0. Furthermore, if dim P(S)0, then dim P(R)≥1−ε. 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.
Year
DOI
Venue
2009
10.1007/s00224-009-9170-1
Theory Comput. Syst.
Keywords
Field
DocType
Constructive dimension,Turing,Extractor,Degree,Randomness
Hausdorff dimension,Discrete mathematics,Probabilistic Turing machine,Combinatorics,Hyperarithmetical theory,Turing reduction,Description number,Packing dimension,Time hierarchy theorem,Mathematics,Post's theorem
Journal
Volume
Issue
ISSN
45
4
1432-4350
Citations 
PageRank 
References 
5
0.44
11
Authors
3
Name
Order
Citations
PageRank
Laurent Bienvenu116824.63
David Doty230823.80
Frank Stephan3493.79