Low for random reals and positive-measure domination
HTML articles powered by AMS MathViewer
- by Bjørn Kjos-Hanssen PDF
- Proc. Amer. Math. Soc. 135 (2007), 3703-3709 Request permission
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
- 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, DOI 10.1137/S0097539704446323
- 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.
- Gregory J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329–340. MR 411829, DOI 10.1145/321892.321894
- Peter Cholak, Noam Greenberg, and Joseph S. Miller, Uniform almost everywhere domination, J. Symbolic Logic 71 (2006), no. 3, 1057–1072. MR 2251556, DOI 10.2178/jsl/1154698592
- Natasha L. Dobrinen and Stephen G. Simpson, Almost everywhere domination, J. Symbolic Logic 69 (2004), no. 3, 914–922. MR 2078930, DOI 10.2178/jsl/1096901775
- D.R. Hirschfeldt, A. Nies, and F. Stephan, Using random sets as oracles, to appear.
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- 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.
- A. Nies, Low for random reals: the story, unpublished.
- André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
- André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515–535. MR 2140044, DOI 10.2178/jsl/1120224726
- C.-P. Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory 5 (1971), 246–258. MR 354328, DOI 10.1007/BF01694181
- Sebastiaan A. Terwijn and Domenico Zambella, Computational randomness and lowness, J. Symbolic Logic 66 (2001), no. 3, 1199–1205. MR 1856736, DOI 10.2307/2695101
Additional Information
- Bjørn Kjos-Hanssen
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- Email: bjoern@math.cornell.edu
- 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 3.2.
- Communicated by: Julia Knight
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2336587