Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


Randomness for non-computable measures

Authors: Adam R. Day and Joseph S. Miller
Journal: Trans. Amer. Math. Soc. 365 (2013), 3575-3591
MSC (2010): Primary 03D32; Secondary 68Q30, 03D30
Published electronically: January 17, 2013
MathSciNet review: 3042595
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

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

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388

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 DMS-0945187 and DMS-0946325, 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.