Randomness for noncomputable measures
Authors:
Adam R. Day and Joseph S. Miller
Journal:
Trans. Amer. Math. Soc. 365 (2013), 35753591
MSC (2010):
Primary 03D32; Secondary 68Q30, 03D30
Published electronically:
January 17, 2013
MathSciNet review:
3042595
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Different approaches have been taken to defining randomness for noncomputable 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 noncomputable 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 is an atom of a neutral measure if and only if it is computable from (every representation of) , 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 MartinLöf random atom.
 1.
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 WileyInterscience
Publication. MR
1700749 (2000e:60008)
 2.
Rodney
G. Downey and Denis
R. Hirschfeldt, Algorithmic randomness and complexity, Theory
and Applications of Computability, Springer, New York, 2010. MR 2732288
(2012g:03001)
 3.
Peter
Gács, Uniform test of algorithmic randomness over a general
space, Theoret. Comput. Sci. 341 (2005),
no. 13, 91–137. MR 2159646
(2006m:68057), 10.1016/j.tcs.2005.03.054
 4.
Mathieu
Hoyrup and Cristóbal
Rojas, Computability of probability measures and MartinLöf
randomness over metric spaces, Inform. and Comput.
207 (2009), no. 7, 830–847. MR 2519075
(2011b:03066), 10.1016/j.ic.2008.12.009
 5.
Carl
G. Jockusch Jr. and Robert
I. Soare, Π⁰₁ classes and
degrees of theories, Trans. Amer. Math.
Soc. 173 (1972),
33–56. MR
0316227 (47 #4775), 10.1090/S00029947197203162270
 6.
Shizuo
Kakutani, A generalization of Brouwer’s fixed point
theorem, Duke Math. J. 8 (1941), 457–459. MR 0004776
(3,60c)
 7.
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, NorthHolland Publishing Co.,
Amsterdam, 1959, pp. 129–158 (French). MR 0112838
(22 #3687)
 8.
L.
A. Levin, The concept of a random sequence, Dokl. Akad. Nauk
SSSR 212 (1973), 548–550 (Russian). MR 0366096
(51 #2346)
 9.
L.
A. Levin, Uniform tests for randomness, Dokl. Akad. Nauk SSSR
227 (1976), no. 1, 33–35 (Russian). MR 0414222
(54 #2325)
 10.
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 (46 #7004)
 11.
Per
MartinLöf, The definition of random sequences,
Information and Control 9 (1966), 602–619. MR 0223179
(36 #6228)
 12.
Joseph
S. Miller, Degrees of unsolvability of continuous functions,
J. Symbolic Logic 69 (2004), no. 2, 555–584. MR 2058189
(2005b:03102), 10.2178/jsl/1082418543
 13.
André
Nies, Computability and randomness, Oxford Logic Guides,
vol. 51, Oxford University Press, Oxford, 2009. MR 2548883
(2011i:03003)
 14.
Jan
Reimann, Effectively closed sets of measures and randomness,
Ann. Pure Appl. Logic 156 (2008), no. 1,
170–182. MR 2474448
(2010a:03043), 10.1016/j.apal.2008.06.015
 15.
Jan Reimann and Theodore A. Slaman.
Measures and their random reals. To appear.
 16.
M.
Rozinas, The semilattice of edegrees, Recursive functions
(Russian), Ivanov. Gos. Univ., Ivanovo, 1978, pp. 71–84
(Russian). MR
604944 (82i:03057)
 17.
Alan
L. Selman, Arithmetical reducibilities. I, Z. Math. Logik
Grundlagen Math. 17 (1971), 335–350. MR 0304150
(46 #3285)
 18.
A. M. Turing.
On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society. Second Series, 43:544546, 1937.
 19.
Klaus
Weihrauch, Computable analysis, Texts in Theoretical Computer
Science. An EATCS Series, SpringerVerlag, Berlin, 2000. An introduction.
MR
1795407 (2002b:03129)
 1.
 Patrick Billingsley.
Convergence of Probability Measures. Wiley, 2nd edition, 1999. MR 1700749 (2000e:60008)
 2.
 R.G. Downey and D.R. Hirschfeldt.
Algorithmic Randomness and Complexity. SpringerVerlag, New York, 2010. MR 2732288
 3.
 Peter Gács.
Uniform test of algorithmic randomness over a general space. Theoret. Comput. Sci., 341(13):91137, 2005. MR 2159646 (2006m:68057)
 4.
 Mathieu Hoyrup and Cristóbal Rojas.
Computability of probability measures and MartinLöf randomness over metric spaces. Inform. and Comput., 207(7):830847, 2009. MR 2519075 (2011b:03066)
 5.
 Carl G. Jockusch, Jr. and Robert I. Soare.
classes and degrees of theories. Trans. Amer. Math. Soc., 173:3356, 1972. MR 0316227 (47:4775)
 6.
 Shizuo Kakutani.
A generalization of Brouwer's fixed point theorem. Duke Mathematical Journal, 8:457459, 1941. MR 0004776 (3:60c)
 7.
 Daniel Lacombe.
Quelques procédés de définition en topologie recursive. In Constructivity in mathematics: Proceedings of the colloquium held at Amsterdam, 1957 (edited by A. Heyting), Studies in Logic and the Foundations of Mathematics, pages 129158. NorthHolland Publishing Co., 1959. MR 0112838 (22:3687)
 8.
 L. A. Levin.
The concept of a random sequence. Soviet Mathematics Doklady, 14(5):14131416, 1973. MR 0366096 (51:2346)
 9.
 L. A. Levin.
Uniform tests for randomness. Soviet Math. Dokl., 17(2):337340, 1976. MR 0414222 (54:2325)
 10.
 L.A. Levin and A.K. Zvonkin.
The complexity of finite objects and the development of the concepts of information and randomness of means of the theory of algorithms. Russian Math. Surveys, 25(6), 1970. MR 0307889 (46:7004)
 11.
 P. MartinLöf.
The definition of random sequences. Information and Control, 9:602619, 1966. MR 0223179 (36:6228)
 12.
 Joseph S. Miller.
Degrees of unsolvability of continuous functions. J. Symbolic Logic, 69(2):555584, 2004. MR 2058189 (2005b:03102)
 13.
 André Nies.
Computability and randomness. Oxford University Press, 2009. MR 2548883 (2011i:03003)
 14.
 Jan Reimann.
Effectively closed sets of measures and randomness. Ann. Pure Appl. Logic, 156(1):170182, 2008. MR 2474448 (2010a:03043)
 15.
 Jan Reimann and Theodore A. Slaman.
Measures and their random reals. To appear.
 16.
 M. Rozinas.
The semilattice of edegrees. In Recursive functions (Russian), pages 7184. Ivanov. Gos. Univ., Ivanovo, 1978. MR 604944 (82i:03057)
 17.
 Alan L. Selman.
Arithmetical reducibilities. I. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 17:335350, 1971. MR 0304150 (46:3285)
 18.
 A. M. Turing.
On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society. Second Series, 43:544546, 1937.
 19.
 Klaus Weihrauch.
Computable analysis, an introduction. SpringerVerlag, Berlin, 2000. MR 1795407 (2002b:03129)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2010):
03D32,
68Q30,
03D30
Retrieve articles in all journals
with MSC (2010):
03D32,
68Q30,
03D30
Additional Information
Adam R. Day
Affiliation:
School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington 6140, New Zealand
Email:
adam.day@msor.vuw.ac.nz
Joseph S. Miller
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 537061388
Email:
jmiller@math.wisc.edu
DOI:
http://dx.doi.org/10.1090/S000299472013056826
Received by editor(s):
November 21, 2010
Received by editor(s) in revised form:
August 10, 2011
Published electronically:
January 17, 2013
Additional Notes:
The second author was supported by the National Science Foundation under grants DMS0945187 and DMS0946325, the latter being part of a Focused Research Group in Algorithmic Randomness.
Article copyright:
© Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
