Please use this identifier to cite or link to this item:
Title: Constructive dimension and turing degrees
Authors: Bienvenu, L.
Doty, D.
Stephan, F. 
Keywords: Constructive dimension
Issue Date: Aug-2009
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.
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
ISSN: 14324350
DOI: 10.1007/s00224-009-9170-1
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Sep 25, 2020


checked on Sep 25, 2020

Page view(s)

checked on Sep 26, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.