Using Almost-Everywhere Theorems from Analysis to Study Randomness

履歴
2016年10月10日　オンライン出版
2016年2月29日　BSL受理
2015年5月　再投稿
2014年11月3日　投稿

タイトル
Using Almost-Everywhere Theorems from Analysis to Study Randomness
(with Jing Zhang and Andre Nies)

種類
正論文

国際会議と雑誌
The Bulletin of Symbolic Logic, Volume 22, Issue 3
September 2016, pp. 305-331
arXiv
最新版.

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-Lo ̈f (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent.
(1) all effectively closed classes containing z have density 1 at z.
(2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z.
(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 $\Pi^0_n$ and $\Sigma^1_1$ classes.

ダウンロード