Computable randomness and betting for computable probability spaces

Mathematical Logic Quarterly 62 (4-5):335-366 (2016)
  Copy   BIBTEX


Unlike Martin‐Löf randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting “bit‐wise” definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness—endomorphism randomness—which the author hopes will shed light on the open question of whether Kolmogorov‐Loveland randomness is equivalent to Martin‐Löf randomness. The last section contains ideas for future research.



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Finite computable dimension does not relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
How much randomness is needed for statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2014 - Annals of Pure and Applied Logic 165 (9):1470-1483.
WHAT IS. . . a Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.
Π10 classes and orderable groups.Reed Solomon - 2002 - Annals of Pure and Applied Logic 115 (1-3):279-302.
H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.


Added to PP

15 (#919,495)

6 months
7 (#425,192)

Historical graph of downloads
How can I increase my downloads?