Proceedings of the American Mathematical Society

Author(s): Bjørn Kjos-Hanssen
Journal: Proc. Amer. Math. Soc. 135 (2007), 3703-3709.
MSC (2000): Primary 03D28, 68Q30
Posted: August 8, 2007
Retrieve article in: PDF

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.

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)

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

Bjørn Kjos-Hanssen
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: bjoern@math.cornell.edu

DOI: 10.1090/S0002-9939-07-08648-0
PII: S 0002-9939(07)08648-0
Received by editor(s): November 29, 2005
Received by editor(s) in revised form: January 21, 2006
Posted: 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 \emph{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
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS