Extractors and Constructive Dimensions of Weak Truth-Table Degrees
| dc.contributor.author | BIENVENU, Laurent | en_US |
| dc.contributor.author | DOTY, David | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2007-01-17T08:08:52Z | en_US |
| dc.date.accessioned | 2017-01-23T06:59:55Z | |
| dc.date.available | 2007-01-17T08:08:52Z | en_US |
| dc.date.available | 2017-01-23T06:59:55Z | |
| dc.date.issued | 2007-01-17T08:08:52Z | en_US |
| dc.description.abstract | 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. | en_US |
| dc.format.extent | 442104 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2312 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRC1/07 | en_US |
| dc.title | Extractors and Constructive Dimensions of Weak Truth-Table Degrees | en_US |
| dc.type | Technical Report | en_US |