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

Jing Zhang
University of Western Australia
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/bsl.2016.10
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,257
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Randomness Notions and Reverse Mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.

Add more citations

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.


Added to PP index

Total views
4 ( #1,274,400 of 2,499,748 )

Recent downloads (6 months)
1 ( #418,066 of 2,499,748 )

How can I increase my downloads?


My notes