Randomness for non-computable measures

Day, Adam; Miller, Joseph

doi:10.1090/S0002-9947-2013-05682-6

Randomness for non-computable measures
HTML articles powered by AMS MathViewer

by Adam R. Day and Joseph S. Miller PDF

Trans. Amer. Math. Soc. 365 (2013), 3575-3591 Request permission

Abstract:

Different approaches have been taken to defining randomness for non-computable probability measures. We will explain the approach of Reimann and Slaman, along with the uniform test approach first introduced by Levin and also used by Gács, Hoyrup and Rojas. We will show that these approaches are fundamentally equivalent.

Having clarified what it means to be random for a non-computable probability measure, we turn our attention to Levin’s neutral measures, for which all sequences are random. We show that every PA degree computes a neutral measure. We also show that a neutral measure has no least Turing degree representation and explain why the framework of the continuous degrees (a substructure of the enumeration degrees studied by Miller) can be used to determine the computational complexity of neutral measures. This allows us to show that the Turing ideals below neutral measures are exactly the Scott ideals. Since $X\in 2^\omega$ is an atom of a neutral measure $\mu$ if and only if it is computable from (every representation of) $\mu$, we have a complete understanding of the possible sets of atoms of a neutral measure. One simple consequence is that every neutral measure has a Martin-Löf random atom.

References

Patrick Billingsley, Convergence of probability measures, 2nd ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999. A Wiley-Interscience Publication. MR 1700749, DOI 10.1002/9780470316962
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
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
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
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
Shizuo Kakutani, A generalization of Brouwer’s fixed point theorem, Duke Math. J. 8 (1941), 457–459. MR 4776
Daniel Lacombe, Quelques procédés de définition en topologie recursive, Constructivity in mathematics: Proceedings of the colloquium held at Amsterdam, 1957 (edited by A. Heyting), Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1959, pp. 129–158 (French). MR 0112838
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
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
Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179
Joseph S. Miller, Degrees of unsolvability of continuous functions, J. Symbolic Logic 69 (2004), no. 2, 555–584. MR 2058189, DOI 10.2178/jsl/1082418543
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
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
Jan Reimann and Theodore A. Slaman. Measures and their random reals. To appear.
M. Rozinas, The semilattice of e-degrees, Recursive functions (Russian), Ivanov. Gos. Univ., Ivanovo, 1978, pp. 71–84 (Russian). MR 604944
Alan L. Selman, Arithmetical reducibilities. I, Z. Math. Logik Grundlagen Math. 17 (1971), 335–350. MR 304150, DOI 10.1002/malq.19710170139
A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society. Second Series, 43:544–546, 1937.
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