Extractors and Constructive Dimensions of Weak Truth-Table Degrees
No Thumbnail Available
Date
2007-01-17T08:08:52Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper examines the constructive Hausdorff and packing dimensions of weak truth-table degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dimH(S) and constructive packing dimension dimP(S)is weak truth-table equivalent to a sequence R with dimH(R)> dimH(S)/dimP(S)- ε, for arbitrary ε > 0. Furthermore, if dimP(S) > 0, then dimP(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 wtt degrees (and, by extension, Turing degrees). A lower bound of dimH(S)/dimP(S) is shown to hold for the wtt degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of wtt degrees. It is also shown that, for any regular sequence S (that is, dimH(S) = dimP(S)) such that dimH(S) > 0, the wtt degree of S has Hausdorff and packing dimension 1.