Using almost-everywhere theorems from analysis to study randomness

2014/11/03 by Miyabe, Kenshi, Nies, André, Zhang, Jing · 1 citation
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1411.0732

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 \ML (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent. \n (1) all effectively closed classes containing z have density 1 at z. \n (2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z. \n (3) z is 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 for density of Π⁰_n and Σ¹₁ classes.

Cited by

• A Variant Of Chaitin's Omega function

Related

• Ergodic theorems for algorithmically random points
• Randomness and Non-ergodic Systems
• Algorithmically random functions and effective capacities
• Separations of non-monotonic randomness notions
• On the close interaction between algorithmic randomness and constructive/computable measure theory