Repository logo
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
Repository logo
  • Communities & Collections
  • All of DSpace
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
  1. Home
  2. Browse by Author

Browsing by Author "BIENVENU, Laurent"

Now showing 1 - 1 of 1
Results Per Page
Sort Options
  • No Thumbnail Available
    Item
    Extractors and Constructive Dimensions of Weak Truth-Table Degrees
    (2007-01-17T08:08:52Z) BIENVENU, Laurent; DOTY, David; STEPHAN, Frank
    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.

DSpace software copyright © 2002-2025 LYRASIS

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback