Please use this identifier to cite or link to this item:
|Title:||Constructive dimension and turing degrees|
|Citation:||Bienvenu, L., Doty, D., Stephan, F. (2009-08). Constructive dimension and turing degrees. Theory of Computing Systems 45 (4) : 740-755. ScholarBank@NUS Repository. https://doi.org/10.1007/s00224-009-9170-1|
|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 dimH(S) and constructive packing dimension dimP(S) is Turing 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 Turing degrees. A lower bound of dimH(S)/dimP(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, dimH(S)=dimP(S)) such that dimH(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. © 2009 Springer Science+Business Media, LLC.|
|Source Title:||Theory of Computing Systems|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 17, 2018
WEB OF SCIENCETM
checked on May 9, 2018
checked on May 18, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.