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: 74,310

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

Some Restrictions on Simple Fixed Points of the Integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
The Broad Conception of Computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
Wittgenstein and the Real Numbers.Daesuk Han - 2010 - History and Philosophy of Logic 31 (3):219-245.
Is the Church-Turing Thesis True?Carol E. Cleland - 1993 - Minds and Machines 3 (3):283-312.
Groundwork for Weak Analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
Color Experience in Blindsight?Berit Brogaard - 2011 - Philosophical Psychology 24 (6):767 - 786.
Frege Meets Dedekind: A Neologicist Treatment of Real Analysis.Stewart Shapiro - 2000 - Notre Dame Journal of Formal Logic 41 (4):335--364.

Analytics

Added to PP
2010-08-24

Downloads
72 (#165,321)

6 months
3 (#209,676)

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