Maximal pairs of c.e. reals in the computably Lipschitz degrees

&
Annals of Pure and Applied Logic 162 (5):357-366 (2011)
  Copy   BIBTEX

Abstract

Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2010.10.003

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,941

External links

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

Through your library

My notes

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.
Continuity of capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
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.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.
Degree spectra of relations on structures of finite computable dimension.Denis R. Hirschfeldt - 2002 - Annals of Pure and Applied Logic 115 (1-3):233-277.
The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent.Klaus Ambos-Spies, Philipp Bodewig, Yun Fan & Thorsten Kräling - 2013 - Annals of Pure and Applied Logic 164 (5):577-588.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
A classification of low c.e. sets and the Ershov hierarchy.Marat Faizrahmanov - forthcoming - Mathematical Logic Quarterly.

Analytics

Added to PP
2013-10-27

Downloads
60 (#349,789)

6 months
9 (#449,254)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

A uniform version of non-low2-ness.Yun Fan - 2017 - Annals of Pure and Applied Logic 168 (3):738-748.

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.
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 and the linear degrees of computability.Andrew Em Lewis & George Barmpalias - 2007 - Annals of Pure and Applied Logic 145 (3):252-257.

Add more references