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.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,353

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

Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Lebesgue density and classes.Mushfeq Khan - 2016 - Journal of Symbolic Logic 81 (1):80-95.
Deep classes.Laurent Bienvenu & Christopher P. Porter - 2016 - Bulletin of Symbolic Logic 22 (2):249-286.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.

Analytics

Added to PP
2017-12-07

Downloads
16 (#1,078,263)

6 months
6 (#736,609)

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