𝐾-trivial degrees and the jump-traceability hierarchy

Barmpalias, George; Downey, Rod; Greenberg, Noam

doi:10.1090/S0002-9939-09-09761-5

$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