Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00224-009-9170-1
Title: Constructive dimension and turing degrees
Authors: Bienvenu, L.
Doty, D.
Stephan, F. 
Keywords: Constructive dimension
Degree
Extractor
Randomness
Turing
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. 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
URI: http://scholarbank.nus.edu.sg/handle/10635/103058
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.

SCOPUSTM   
Citations

8
checked on Aug 17, 2018

WEB OF SCIENCETM
Citations

7
checked on Aug 8, 2018

Page view(s)

31
checked on Aug 3, 2018

Google ScholarTM

Check

Altmetric


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