$K$-trivial degrees and the jump-traceability hierarchy
HTML articles powered by AMS MathViewer
- by George Barmpalias, Rod Downey and Noam Greenberg PDF
- Proc. Amer. Math. Soc. 137 (2009), 2099-2109 Request permission
Abstract:
For every order $h$ such that $\sum _n 1/h(n)$ is finite, every $K$-trivial degree is $h$-jump-traceable. This motivated Cholak, Downey and Greenberg to ask whether this traceability property is actually equivalent to $K$-triviality, thereby giving the hoped for combinatorial characterisation of lowness for Martin-Löf randomness. We show however that the $K$-trivial degrees are properly contained in those that are $h$-jump-traceable for every convergent order $h$.References
- George Barmpalias, Andrew E. M. Lewis, and Mariya Soskova, Randomness, lowness and degrees, J. Symbolic Logic 73 (2008), no. 2, 559–577. MR 2414465, DOI 10.2178/jsl/1208359060
- Peter Cholak, Rod Downey, and Noam Greenberg, Strong jump-traceabilty. I. The computably enumerable case, Adv. Math. 217 (2008), no. 5, 2045–2074. MR 2388085, DOI 10.1016/j.aim.2007.09.008
- Rod Downey and Noam Greenberg. Strong jump-traceability, II: The general case, in preparation.
- Rod Downey and Denis Hirshfeldt. Algorithmic Randomness and Complexity. Springer-Verlag, in preparation, 2009.
- Santiago Figueira, André Nies, and Frank Stephan, Lowness properties and approximations of the jump, Proceedings of the 12th Workshop on Logic, Language, Information and Computation (WoLLIC 2005), Electron. Notes Theor. Comput. Sci., vol. 143, Elsevier Sci. B. V., Amsterdam, 2006, pp. 45–57. MR 2270232, DOI 10.1016/j.entcs.2005.05.025
- Bjørn Kjos-Hanssen, Low for random reals and positive-measure domination, Proc. Amer. Math. Soc. 135 (2007), no. 11, 3703–3709. MR 2336587, DOI 10.1090/S0002-9939-07-08648-0
- Bjørn Kjos-Hanssen, André Nies, and Frank Stephan, Lowness for the class of Schnorr random reals, SIAM J. Comput. 35 (2005), no. 3, 647–657. MR 2201451, DOI 10.1137/S0097539704446323
- Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590, DOI 10.2178/bsl/1154698740
- André Nies, Reals which compute little, Logic Colloquium ’02, Lect. Notes Log., vol. 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp. 261–275. MR 2258710
- André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
- André Nies. Eliminating concepts. In Proceedings of the IMS workshop on computational aspects of infinity, Singapore, to appear, 2008.
- André Nies. Computability and Randomness. Oxford University Press, in preparation, 2009.
- Keng-Meng Ng. Beyond jump traceability, preprint.
- Sebastiaan A. Terwijn and Domenico Zambella, Computational randomness and lowness, J. Symbolic Logic 66 (2001), no. 3, 1199–1205. MR 1856736, DOI 10.2307/2695101
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
- MR Author ID: 59535
- 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
- MR Author ID: 757288
- ORCID: 0000-0003-2917-3848
- Email: greenberg@mcs.vuw.ac.nz
- Received by editor(s): March 20, 2008
- Received by editor(s) in revised form: September 11, 2008
- Published electronically: January 22, 2009
- Additional Notes: All authors were supported by the Marsden Fund of New Zealand.
- Communicated by: Julia Knight
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 137 (2009), 2099-2109
- MSC (2000): Primary 03D80
- DOI: https://doi.org/10.1090/S0002-9939-09-09761-5
- MathSciNet review: 2480292