Using Almost-everywhere theorems from Analysis to Study Randomness
Using Almost-everywhere theorems from Analysis to Study Randomness
复制标题
DOI：
10.1017/bsl.2016.10
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Kenshi Miyabe;A. Nies;Jing Zhang
中科院分区：
文献类型：
--
作者：
Kenshi Miyabe;A. Nies;Jing Zhang
我们通过分析和遍历理论中几乎处处定理的有效版本来研究算法随机性概念。有效性是根据由可计算可枚举集描述的对象，例如下半可计算函数。相应的随机性概念略强于ML(ML)随机性。我们建立了几个等价关系。给定ML-随机实数$z$，下列情况所需的附加随机性强度是相等的。\n(1)所有包含$z$的有效闭类在$z$处有密度$1$。\n(2)所有具有一致左C.E.增量的非减函数在$z$处可微。\n(3)$z$是每个下半可积函数的勒贝格点。我们还考虑了左C.E.\鞅的收敛，以及在Birkhoff逐点遍历定理意义下的收敛。最后，我们研究了$\Pi^0_n$和$\Sigma^1_1$类密度的随机性概念。
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 $\Pi^0_n$ and $\Sigma^1_1$ classes.