A C.E. Real That Cannot Be SW-Computed by Any Ω Number

Notre Dame Journal of Formal Logic 47 (2):197-209 (2006)
  Copy   BIBTEX

Abstract

The strong weak truth table (sw) reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky, and Weinberger on applications of computability to differential geometry. We study the sw-degrees of c.e. reals and construct a c.e. real which has no random c.e. real (i.e., Ω number) sw-above it

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,385

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
Maximal pairs of c.e. reals in the computably Lipschitz degrees.Yun Fan & Liang Yu - 2011 - Annals of Pure and Applied Logic 162 (5):357-366.
There is no SW-complete c.e. real.Decheng Ding & Liang Yu - 2004 - Journal of Symbolic Logic 69 (4):1163-1170.
There Is No SW-Complete C.E. Real.Liang Yu & Decheng Ding - 2004 - Journal of Symbolic Logic 69 (4):1163 - 1170.
Schnorr randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Effective Packing Dimension and Traceability.Rod Downey & Keng Meng Ng - 2010 - Notre Dame Journal of Formal Logic 51 (2):279-290.

Analytics

Added to PP
2010-08-24

Downloads
90 (#187,450)

6 months
12 (#310,009)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrew Lewis
Graduate Theological Union

Citations of this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
Randomness and the linear degrees of computability.Andrew Em Lewis & George Barmpalias - 2007 - Annals of Pure and Applied Logic 145 (3):252-257.
Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.

View all 8 citations / Add more citations

References found in this work

Computability theory and differential geometry.Robert I. Soare - 2004 - Bulletin of Symbolic Logic 10 (4):457-486.
There Is No SW-Complete C.E. Real.Liang Yu & Decheng Ding - 2004 - Journal of Symbolic Logic 69 (4):1163 - 1170.

Add more references