Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-22T20:37:33.038Z Has data issue: false hasContentIssue false
  • English
  • Français

Lowness for Kurtz randomness

Published online by Cambridge University Press:  12 March 2014

Noam Greenberg  and
Joseph S. Miller
Noam Greenberg
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand, E-mail: [email protected]
Joseph S. Miller
Affiliation:
Department of Mathematics, University of Wisconsin, Madison. Wi 53706-1388., USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity.

We also consider Low(ℳ, Kurtz), the class of degrees a such that every element of ℳ is a-Kurtz random. These are characterised when ℳ is the class of Martin-Löf random, computably random, or Schnorr random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 2 , June 2009 , pp. 665 - 678
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Downey, Rod, Hirschfeldt, Denis R., Nies, André, and Terwijn, Sebastiaan A., Calibrating randomness, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 411–491.CrossRefGoogle Scholar
[2]Downey, Rod, Nies, André, Weber, Rebecca, and Yu, Liang, Lowness and Π20 nullsets, this Journal, vol. 71 (2006), no. 3, pp. 1044–1052.Google Scholar
[3]Downey, Rodney G., Griffiths, Evan J., and Reid, Stephanie, On Kurtz randomness. Theoretical Computer Science, vol. 321 (2004), no. 2-3, pp. 249–270.CrossRefGoogle Scholar
[4]Kjos-Hanssen, Bjørn and Diamondstone, David, Members of random closed sets, to appear.Google Scholar
[5]Kjos-Hanssen, Bjørn, Merkle, Wolfgang, and Stephan, Frank, Kolmogorov complexity and the recursion theorem, arXiv 0901.3933 [math. LO]Google Scholar
[6]Kjos-Hanssen, Bjørn, Miller, Joseph S., and Solomon, Reed, Lowness notions, measure and domination.Google Scholar
[7]Kjos-Hanssen, Bjørn, Nies, André, and Stephan, Frank, Lowness for the class of Schnorr random reals, SIAM Journal on Computing, vol. 35 (2005), no. 3, pp. 647–657 (electronic).CrossRefGoogle Scholar
[8]Kurtz, Stewart, Randomness andgenericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1981.Google Scholar
[9]Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1. pp. 274–305.CrossRefGoogle Scholar
[10]Nies, André, Computability and randomness, Oxford University Press, 2009, in preparation.CrossRefGoogle Scholar
[11]Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A., Randomness, relativization and Turing degrees, this Journal, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
[12]Nitzpon, Daniel, On ‘low for’: A few examples of lowness in recursion theory, Doctoraalexamen. University of Amsterdam, 2002.Google Scholar
[13]Simpson, Stephen and Cole, Joshua, Mass problems and hyperarithmeticity, Journal of Mathematical Logic, vol. 7 (2007), no. 2, pp. 125–143.Google Scholar
[14]Slaman, Theodore A. and Solovay, Robert, When oracles do not help, COLT '91: Proceedings of the fourth annual workshop on Computational Learning Theory (Valiant, Leslie G. and Warmuth, Manfred K., editors), Morgan Kaufmann Publishers Inc., San Francisco. CA, USA. 1991, pp. 379–383.CrossRefGoogle Scholar
[15]Spector, Clifford, On degrees of recursive unsolvability, Annals of Mathematics, (2), vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[16]Stephan, Frank and Yu, Liang, Lowness for weakly 1-generic and Kurtz-random. Theory and applications of models of computation (Cai, Jin yi, Cooper, S. Barry, and Li, Angsheng, editors), Lecture Notes in Computer Science, vol. 3959, Springer, Berlin, 2006, pp. 756–764.CrossRefGoogle Scholar
[17]Terwijn, Sebastiaan A. and Zambella, Domenico, Computational randomness and lowness, this Journal, vol. 66 (2001), no. 3, pp. 1199–1205.Google Scholar
[18]Yu, Liang, Lowness for genericity, Archive for Mathematical Logic, vol. 45 (2006), no. 2, pp. 233–238.CrossRefGoogle Scholar