Portal de Periódicos da CAPES

Constructive Dimension and Weak Truth-Table Degrees

2007; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-73001-9_7

1611-3349

Laurent Bienvenu, David Doty, Frank Stephan,

Algorithms and Data Compression

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 \({\rm dim_H}({\it R}) \geq {\rm dim_H}(S) / {\rm dim_P}(S) - \epsilon\), 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 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.