Using almost-everywhere theorems from analysis to study randomness

Bulletin of Symbolic Logic 22 (3):305-331 (2016)
  Copy   BIBTEX

Abstract

We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin–Löf randomness.We establish several equivalences. Given a ML-random realz, the additional randomness strengths needed for the following are equivalent.all effectively closed classes containingzhave density 1 atz.all nondecreasing functions with uniformly left-c.e. increments are differentiable atz.zis a Lebesgue point of each lower semicomputable integrable function.We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff’s pointwise ergodic theorem. Lastly, we study randomness notions related to density of${\rm{\Pi }}_n^0$and${\rm{\Sigma }}_1^1$classes at a real.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Lowness and Π₂⁰ nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Continuous higher randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
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.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Algorithmic randomness over general spaces.Kenshi Miyabe - 2014 - Mathematical Logic Quarterly 60 (3):184-204.

Analytics

Added to PP
2017-12-07

Downloads
5 (#1,344,576)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Jing Zhang
University of Western Australia

Citations of this work

Bayesian merging of opinions and algorithmic randomness.Francesca Zaffora Blando - forthcoming - British Journal for the Philosophy of Science.
Randomness notions and reverse mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.

Add more citations

References found in this work

No references found.

Add more references