Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Working with strong reducibilities above totally $ \omega$-c.e. and array computable degrees


Authors: George Barmpalias, Rod Downey and Noam Greenberg
Journal: Trans. Amer. Math. Soc. 362 (2010), 777-813
MSC (2000): Primary 03D25, 03D30
Published electronically: September 11, 2009
MathSciNet review: 2551506
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate the connections between the complexity of a c.e. set, as calibrated by its strength as an oracle for Turing computations of functions in the Ershov hierarchy, and how strong reducibilities allow us to compute such sets. For example, we prove that a c.e. degree is totally $ \omega$-c.e. iff every set in it is weak truth-table reducible to a hypersimple, or ranked, set. We also show that a c.e. degree is array computable iff every left-c.e. real of that degree is reducible in a computable Lipschitz way to a random left-c.e. real (an $ \Omega$-number).


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D25, 03D30

Retrieve articles in all journals with MSC (2000): 03D25, 03D30


Additional Information

George Barmpalias
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: George.Barmpalias@mcs.vuw.ac.nz

Rod Downey
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: downey@mcs.vuw.ac.nz

Noam Greenberg
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: greenberg@mcs.vuw.ac.nz

DOI: http://dx.doi.org/10.1090/S0002-9947-09-04910-1
PII: S 0002-9947(09)04910-1
Received by editor(s): December 19, 2007
Published electronically: September 11, 2009
Additional Notes: We wish to thank Frank Stephan for his permission to include Theorem \ref{thm: Stephan} and its proof. All authors were supported by the Marsden fund of New Zealand.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.