Maximal pairs of c.e. reals in the computably Lipschitz degrees
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. realsAuthor's Profile
Other Versions
No versions found
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.
Randomness, Lowness and Degrees.George Barmpalias,Andrew E. M. Lewis &Mariya Soskova -2008 -Journal of Symbolic Logic 73 (2):559 - 577.
Analytics
Added to PP
2013-10-27
Downloads
64 (#361,768)
6 months
6 (#725,072)
2013-10-27
Downloads
64 (#361,768)
6 months
6 (#725,072)
Historical graph of downloads
How can I increase my downloads?Author's Profile
Citations of this work
References found in this work
The ibT degrees of computably enumerable sets are not dense.George Barmpalias &Andrew E. M. Lewis -2006 -Annals of Pure and Applied Logic 141 (1):51-60.
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.
Home |New books and articles |Bibliographies |Philosophy journals |About PhilPapers |API |Contact us |Code of conduct
PhilPapers logo byAndrea Andrews andMeghan Driscoll.
This site uses cookies and Google Analytics (see ourterms & conditions for details regarding the privacy implications).Use of this site is subject toterms & conditions.
All rights reserved byThe PhilPapers Foundation
Server: philpapers-web-54b44b69b7-k24bk uwo