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 Free Access

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.**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**, 10.1137/S0097539704446323**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.**Gregory J. Chaitin,*A theory of program size formally identical to information theory*, J. Assoc. Comput. Mach.**22**(1975), 329–340. MR**0411829****4.**Peter Cholak, Noam Greenberg, and Joseph S. Miller,*Uniform almost everywhere domination*, J. Symbolic Logic**71**(2006), no. 3, 1057–1072. MR**2251556**, 10.2178/jsl/1154698592**5.**Natasha L. Dobrinen and Stephen G. Simpson,*Almost everywhere domination*, J. Symbolic Logic**69**(2004), no. 3, 914–922. MR**2078930**, 10.2178/jsl/1096901775**6.**D.R. Hirschfeldt, A. Nies, and F. Stephan,*Using random sets as oracles*, to appear.**7.**Antonín Kučera,*Measure, Π⁰₁-classes and complete extensions of 𝑃𝐴*, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR**820784**, 10.1007/BFb0076224**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.**André Nies,*Lowness properties and randomness*, Adv. Math.**197**(2005), no. 1, 274–305. MR**2166184**, 10.1016/j.aim.2004.10.006**11.**André Nies, Frank Stephan, and Sebastiaan A. Terwijn,*Randomness, relativization and Turing degrees*, J. Symbolic Logic**70**(2005), no. 2, 515–535. MR**2140044**, 10.2178/jsl/1120224726**12.**C.-P. Schnorr,*A unified approach to the definition of random sequences*, Math. Systems Theory**5**(1971), 246–258. MR**0354328****13.**Sebastiaan A. Terwijn and Domenico Zambella,*Computational randomness and lowness*, J. Symbolic Logic**66**(2001), no. 3, 1199–1205. MR**1856736**, 10.2307/2695101

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:
http://dx.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.