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

DOI:
https://doi.org/10.1090/S0002-9939-07-08648-0

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.

**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, -classes and complete extensions of*, 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

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

Email:
bjoern@math.cornell.edu

DOI:
https://doi.org/10.1090/S0002-9939-07-08648-0

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.