Using almost-everywhere theorems from analysis to study randomness

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 $Π^0_n$ and $Σ^1_1$ classes.

No reviews yet.

No comments yet.