Algorithmic randomness over general spaces

Mathematical Logic Quarterly 60 (3):184-204 (2014)
  Copy   BIBTEX


The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT3 is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition.



    Upload a copy of this work     Papers currently archived: 89,491

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.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Lowness and Π₂⁰ nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.


Added to PP

16 (#765,030)

6 months
1 (#1,009,728)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Computable randomness and betting for computable probability spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.

Add more citations

References found in this work

Computable metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
Admissible representations for probability measures.Matthias Schröder - 2007 - Mathematical Logic Quarterly 53 (4):431-445.
Computability Theory.Barry Cooper - 2010 - Journal of the Indian Council of Philosophical Research 27 (1).

Add more references