Remote Access Transactions of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9947-09-04910-1
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?)

  • 1. Bahareh Afshari, George Barmpalias, S. Barry Cooper and Frank Stephan, Post's programme for the Ershov hierarchy, Journal of Logic and Computation 17 (2007), 1025-1040. MR 2376073 (2008j:03059)
  • 2. George Barmpalias, Computability and applications to analysis, Ph.D. thesis, University of Leeds, U.K., 2004.
  • 3. George Barmpalias, Hypersimplicity and semicomputability in the weak truth table degrees, Archive for Math. Logic 44 (2005), 1045-1065. MR 2193189 (2006m:03069)
  • 4. George Barmpalias and Andrew E. M. Lewis, Random reals and Lipschitz continuity, Mathematical Structures in Computer Science, Volume 16 (2006), 737-749. MR 2268340 (2007h:03086)
  • 5. George Barmpalias and Andrew E. M. Lewis, The $ {ibT}$ degrees of computably enumerable sets are not dense, Annals of Pure and Applied Logic, Volume 141 (2006), 51-60. MR 2229929 (2007d:03068)
  • 6. George Barmpalias and Andrew E. M. Lewis, Randomness and the linear degrees of computability, Annals of Pure and Applied Logic 145 (2007), 252-257. MR 2286414 (2007j:03056)
  • 7. George Barmpalias and Andrew E. M. Lewis, A c.e. real that cannot be sw-computed by any $ \Omega$-number, Notre Dame Journal of Formal Logic, Volume 47 Issue 2 (2006), pp. 197-209. MR 2240619 (2008c:03046)
  • 8. John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Timothy McNicholl, and Sarah Pingrey, $ \Pi^0_1$ Classes and strong degree spectra of relations, Journal of Symbolic Logic 72 (2007), 1003-1018. MR 2354911
  • 9. Chris J. Conidis, Classifying Model-Theoretic Properties, Journal of Symbolic Logic, Vol. 73(3) (2008) 885-905. MR 2444274
  • 10. Barbara F. Csima and Robert I. Soare, Computability results used in differential geometry, Journal of Symbolic Logic 71 (2006), 1394-1410. MR 2275866 (2007g:03053)
  • 11. David Doty, Every sequence is decompressible from a random one. in Arnold Beckmann et al. (eds.), Logical approaches to computational barriers, Proceedings of the second conference on computability in Europe, Lecture Notes in Computer Science 3988, Springer-Verlag, 2006, 153-162.
  • 12. Rod Downey and Noam Greenberg, Totally $ <\omega^\omega$-computably enumerable degrees and embeddings of the 1-3-1 lattice, in preparation.
  • 13. Rod Downey and Noam Greenberg, Totally $ <\omega^\omega$-computably enumerable and $ m$-topped degrees, In Cai, Cooper, Li (eds.), Theory and Applications of Models of Computation (proceedings of TAMC 2006, Beijing), volume 3959 of Lecture Notes in Computer Science, Springer (2006), 46-60. MR 2277228 (2007i:03047)
  • 14. Rod Downey and Noam Greenberg, Turing degrees of reals of positive effective packing dimension, Information Processing Letters 108 (2008), 298-303. MR 2456604
  • 15. Rod Downey, Noam Greenberg and Rebecca Weber, Totally $ \omega$-computably enumerable degrees and bounding critical triples, J. Math. Log. 7 (2007), 145-171. MR 2423948
  • 16. Rod Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Springer, to appear.
  • 17. Rod Downey, Denis R. Hirschfeldt and Geoff LaForte, Randomness and reducibility. Mathematical foundations of computer science, 2001, 316-327, Lecture Notes in Comput. Sci. 2136, Springer, Berlin, 2001. MR 1907022 (2003j:03051)
  • 18. Rod Downey, Denis R. Hirschfeldt and Geoff LaForte, Randomness and reducibility. Journal of Computer and System Sciences 68 (2004), 96-114. MR 2030512 (2004m:03165)
  • 19. Rod Downey, Carl G. Jockusch, Jr., and Michael Stob, Array nonrecursive sets and multiple permitting arguments, Recursion Theory Week (Proceedings, Oberwolfach 1989) (K. Ambos-Spies, G.H. Müller and G.E. Sacks, eds.) Lecture Notes in Math. 1432, Springer-Verlag, 1990, 141-173. MR 1071516 (91k:03110)
  • 20. Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman, The atomic model theorem, Preprint.
  • 21. Rod Downey, Carl G. Jockusch, Jr., and Michael Stob, Array nonrecursive sets and genericity, in Computability, Enumerability, Unsolvability: Directions in Recursion Theory. London Mathematical Society Lecture Notes Series (Cambridge University Press) 224 (1996), 93-104. MR 1395876 (97f:03060)
  • 22. Stephen Fenner and Marcus Schaefer, Bounded immunity and btt-reductions. Mathematical Logic Quarterly 45 (1999), 3-21. MR 1669934 (2000d:03087)
  • 23. Peter Gács, Every sequence is reducible to a random one, Information and Control 70 (1986), 186-192. MR 859105 (87k:03043)
  • 24. Shamil Ishmukhametov, Weak recursive degrees and a problem of Spector, in Recursion Theory and Complexity (M. Arslanov and S. Lempp, eds.), de Gruyter, Berlin, 1999, 81-88. MR 1724934 (2001a:03089)
  • 25. Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan, Kolmogorov complexity and the recursion theorem, in STACS 2006: Twenty-Third Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings. Springer Lecture Notes in Computer Science 3884, 149-161, 2006. MR 2249365 (2008a:68100)
  • 26. Antonin Kučera, Measure, $ \Pi^0_1$-classes and complete extensions of PA. In: H.-D. Ebbinghaus et al. (eds.), Recursion Theory Week. Lecture Notes in Mathematics 1141:245-259, Springer, 1985. MR 820784 (87e:03102)
  • 27. Antonin Kučera, On the use of diagonally nonrecursive functions. In: H.-D. Ebbinghaus et al. (eds.), Logic Colloquium 1987. Studies in Logic and the Foundations of Mathematics 129:219-239, North-Holland, 1989. MR 1015310 (91c:03037)
  • 28. Antonin Kučera and Theodore A. Slaman, Randomness and recursive enumerability. SIAM Journal of Computing 31 (2001), 199-211. MR 1857396 (2002k:68078)
  • 29. Martin Kummer, Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM Journal on Computing 25 (1996), No. 6, 1123-1143. MR 1417892 (98h:03055)
  • 30. M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, Graduate Texts in Computer Science, Second Edition, Springer-Verlag, New York, 1997. MR 1438307 (97k:68086)
  • 31. Wolfgang Merkle and Nenad Mihailović, On the construction of effectively random sets, Journal of Symbolic Logic 69 (2004), 862-878. MR 2078927 (2005k:03103)
  • 32. André Nies.
    Computability and Randomness.
    Oxford University Press, in preparation, 2009.
  • 33. Keng Meng Ng, Frank Stephan and Guohua Wu, Degrees of weakly computable reals, Proceedings of ``Second Conference on Computability in Europe'', CiE 2006, Swansea (2006), 413-422.
  • 34.
    Piergiorgio Odifreddi, Classical recursion theory, Volume I, North-Holland Publ. Co., Amsterdam, 1989. MR 982269 (90d:03072)
  • 35. Liang Yu and Decheng Ding, There is no $ SW$-complete c.e. real. J. Symbolic Logic 69 (2004), 1163-1170. MR 2135660 (2006h:68075)

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: https://doi.org/10.1090/S0002-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.

American Mathematical Society