Randomness and the linear degrees of computability

Annals of Pure and Applied Logic 145 (3):252-257 (2007)
  Copy   BIBTEX

Abstract

We show that there exists a real α such that, for all reals β, if α is linear reducible to β then β≤Tα. In fact, every random real satisfies this quasi-maximality property. As a corollary we may conclude that there exists no ℓ-complete Δ2 real. Upon realizing that quasi-maximality does not characterize the random reals–there exist reals which are not random but which are of quasi-maximal ℓ-degree–it is then natural to ask whether maximality could provide such a characterization. Such hopes, however, are in vain since no real is of maximal ℓ-degree

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

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

A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.

Analytics

Added to PP
2013-12-30

Downloads
16 (#851,323)

6 months
6 (#417,196)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrew Lewis
Graduate Theological Union

Citations of this work

Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
A uniform version of non-low2-ness.Yun Fan - 2017 - Annals of Pure and Applied Logic 168 (3):738-748.
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.

Add more citations

References found in this work

Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
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.

View all 7 references / Add more references