|
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
Posted:
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
(2006j:68051), http://dx.doi.org/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
(53 #15557)
- 4.
Peter
Cholak, Noam
Greenberg, and Joseph
S. Miller, Uniform almost everywhere domination, J. Symbolic
Logic 71 (2006), no. 3, 1057–1072. MR 2251556
(2007e:03071), http://dx.doi.org/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
(2005d:03079), http://dx.doi.org/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
(87e:03102), http://dx.doi.org/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
(2006j:68052), http://dx.doi.org/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
(2006i:68043), http://dx.doi.org/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
(50 #6808)
- 13.
Sebastiaan
A. Terwijn and Domenico
Zambella, Computational randomness and lowness, J. Symbolic
Logic 66 (2001), no. 3, 1199–1205. MR 1856736
(2002j:03044), http://dx.doi.org/10.2307/2695101
- 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)
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
Email:
bjoern@math.cornell.edu
DOI:
http://dx.doi.org/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 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.
|
