Browsing by Author "BIENVENU, Laurent"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Extractors and Constructive Dimensions of Weak Truth-Table Degrees
    (2007-01-17T08:08:52Z) BIENVENU, Laurent; DOTY, David; STEPHAN, Frank
    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.