Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Low for random reals and positive-measure domination

Author: Bjørn Kjos-Hanssen
Journal: Proc. Amer. Math. Soc. 135 (2007), 3703-3709
MSC (2000): Primary 03D28, 68Q30
Published electronically: August 8, 2007
MathSciNet review: 2336587
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The low for random reals are characterized topologically, as well as in terms of domination of Turing functionals on a set of positive measure.

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

  • 1. A. Nies, B. Kjos-Hanssen and F. Stephan, Lowness for the class of Schnorr random reals, SIAM J. Computing 35 (2006), no. 3, 647-657. MR 2201451
  • 2. S. Binns, B. Kjos-Hanssen, M. Lerman, and D.R. Solomon, On a question of Dobrinen and Simpson concerning almost everywhere domination, J. Symbolic Logic 71 (2006), no. 1, 119-136.
  • 3. G.J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329-340. MR 0411829 (53:15557)
  • 4. P. Cholak, N. Greenberg, and J.S. Miller, Uniform almost everywhere domination, J. Symbolic Logic 71 (2006), no. 3, 1057-1072. MR 2251556
  • 5. N.L. Dobrinen and S.G. Simpson, Almost everywhere domination, J. Symbolic Logic 69 (2004), 914-922. MR 2078930 (2005d:03079)
  • 6. D.R. Hirschfeldt, A. Nies, and F. Stephan, Using random sets as oracles, to appear.
  • 7. Antonín Kucera, Measure, $ \Pi\sp 0\sb 1$-classes and complete extensions of $ {\rm PA}$, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245-259. MR 0820784 (87e:03102)
  • 8. S.A. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1981, pp. VII+131 pages.
  • 9. A. Nies, Low for random reals: the story, unpublished.
  • 10. -, Lowness properties and randomness, Adv. Math. 197 (2005), 274-305.MR 2166184
  • 11. A. Nies, F. Stephan, and S.A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515-535. MR 2140044
  • 12. C.P. Schnorr, A unified approach to the definition of a random sequence, Mathematical Systems Theory 5 (1971), 246-258. MR 0354328 (50:6808)
  • 13. S.A. Terwijn and D. Zambella, Computational randomness and lowness, J. Symbolic Logic 66 (2001), 1199-1205. MR 1856736 (2002j:03044)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D28, 68Q30

Retrieve articles in all journals with MSC (2000): 03D28, 68Q30

Additional Information

Bjørn Kjos-Hanssen
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Received by editor(s): November 29, 2005
Received by editor(s) in revised form: January 21, 2006
Published electronically: August 8, 2007
Additional Notes: The author thanks the Institute for Mathematical Sciences of the National University of Singapore for support during the preparation of this manuscript at the Computational Prospects of Infinity conference in Summer 2005. The author also thanks Denis R. Hirschfeldt for proving upon request a lemma used in an earlier proof of the case $B\le_{T} 0’$ of Theorem \ref{jada}.
Communicated by: Julia Knight
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society