Randomness and the linear degrees of computability
Lewis-Pye, A. & Barmpalias, G.
(2007).
Randomness and the linear degrees of computability.
Annals of Pure and Applied Logic,
145(3), 252-257.
https://doi.org/10.1016/j.apal.2006.08.001
We show that there exists a real α such that, for all reals β, if α is linear reducible to β (α≤ℓβ, previously denoted as α≤swβ) 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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2006 Elsevier B.V. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.apal.2006.08.001 |
| Date Deposited | 06 Aug 2013 |
| URI | https://researchonline.lse.ac.uk/id/eprint/51423 |
Explore Further
- https://www.scopus.com/pages/publications/33845910105 (Scopus publication)
- http://www.journals.elsevier.com/annals-of-pure-an... (Official URL)