Measures and their random reals
HTML articles powered by AMS MathViewer
- by Jan Reimann and Theodore A. Slaman PDF
- Trans. Amer. Math. Soc. 367 (2015), 5081-5097 Request permission
Abstract:
We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-computable real is non-trivially random with respect to some measure. The probability measures constructed in the proof may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for any continuous measure can be found throughout the hyperarithmetical Turing degrees.References
- Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, and Stanley S. Wainer, Members of countable $\Pi ^0_1$ classes, Ann. Pure Appl. Logic 31 (1986), no. 2-3, 145–163. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 854290, DOI 10.1016/0168-0072(86)90067-9
- A. Day, Randomness and computability, PhD thesis, Victoria University of Wellington, 2011.
- Adam R. Day and Joseph S. Miller, Randomness for non-computable measures, Trans. Amer. Math. Soc. 365 (2013), no. 7, 3575–3591. MR 3042595, DOI 10.1090/S0002-9947-2013-05682-6
- Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin’s halting probability, J. Math. Log. 5 (2005), no. 2, 167–192. MR 2188515, DOI 10.1142/S0219061305000468
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186–192. MR 859105, DOI 10.1016/S0019-9958(86)80004-3
- Peter Gács, Uniform test of algorithmic randomness over a general space, Theoret. Comput. Sci. 341 (2005), no. 1-3, 91–137. MR 2159646, DOI 10.1016/j.tcs.2005.03.054
- Eli Glasner, Ergodic theory via joinings, Mathematical Surveys and Monographs, vol. 101, American Mathematical Society, Providence, RI, 2003. MR 1958753, DOI 10.1090/surv/101
- Paul R. Halmos, Measure Theory, D. Van Nostrand Co., Inc., New York, N. Y., 1950. MR 0033869, DOI 10.1007/978-1-4684-9440-2
- Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput. 207 (2009), no. 7, 830–847. MR 2519075, DOI 10.1016/j.ic.2008.12.009
- S. M. Kautz, Degrees of random sequences, PhD thesis, Cornell University, 1991.
- Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
- B. Kjos-Hanssen and A. Montalbán, Personal communication, March 2005.
- G. Kreisel, Analysis of the Cantor-Bendixson theorem by means of the analytic hierarchy, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 7 (1959), 621–626. (unbound insert) (English, with Russian summary). MR 0118673
- 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
- L. A. Levin, The concept of a random sequence, Dokl. Akad. Nauk SSSR 212 (1973), 548–550 (Russian). MR 0366096
- L. A. Levin, Uniform tests for randomness, Dokl. Akad. Nauk SSSR 227 (1976), no. 1, 33–35 (Russian). MR 0414222
- Leonid A. Levin, Randomness conservation inequalities: information and independence in mathematical theories, Inform. and Control 61 (1984), no. 1, 15–37. MR 764286, DOI 10.1016/S0019-9958(84)80060-1
- Richard Mansfield, Perfect subsets of definable sets of real numbers, Pacific J. Math. 35 (1970), 451–457. MR 280380, DOI 10.2140/pjm.1970.35.451
- Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179, DOI 10.1016/S0019-9958(66)80018-9
- Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
- Andrei A. Muchnik, Alexei L. Semenov, and Vladimir A. Uspensky, Mathematical metaphysics of randomness, Theoret. Comput. Sci. 207 (1998), no. 2, 263–317. MR 1643438, DOI 10.1016/S0304-3975(98)00069-3
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI 10.2307/2273221
- Jan Reimann, Effectively closed sets of measures and randomness, Ann. Pure Appl. Logic 156 (2008), no. 1, 170–182. MR 2474448, DOI 10.1016/j.apal.2008.06.015
- J. Reimann and T. A. Slaman, Randomness for continuous measures, in preparation.
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225, DOI 10.1007/BFb0112458
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Robert M. Solovay, On the cardinality of $\sum _{2}^{1}$ sets of reals, Foundations of Mathematics (Symposium Commemorating Kurt Gödel, Columbus, Ohio, 1966) Springer, New York, 1969, pp. 58–73. MR 0277382
- Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
- W. Hugh Woodin, A tt version of the Posner-Robinson theorem, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 355–392. MR 2449474, DOI 10.1142/9789812796554_{0}019
- A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspehi Mat. Nauk 25 (1970), no. 6(156), 85–127 (Russian). MR 0307889
Additional Information
- Jan Reimann
- Affiliation: Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
- MR Author ID: 667958
- ORCID: 0000-0003-1156-8390
- Email: reimann@math.psu.edu
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California at Berkeley, Berkeley, California 94720
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Received by editor(s): February 19, 2008
- Received by editor(s) in revised form: May 14, 2013
- Published electronically: January 30, 2015
- Additional Notes: The first author was partially supported by NSF grants DMS-0801270 and DMS-1201263.
The second author was partially supported by NSF grants DMS-0501167 and DMS-1001551. - © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 367 (2015), 5081-5097
- MSC (2010): Primary 03D32, 68Q30
- DOI: https://doi.org/10.1090/S0002-9947-2015-06184-4
- MathSciNet review: 3335411