履歴
2018年3月11日提出
タイトル
計算可能測度論
種類
総説論文
ジャーナル
数理解析研究所講究録
RIMS共同研究(公開型)証明論と証明活動
2017年12月25日〜27日
ダウンロード
rims
Null-additivity in the theory of algorithmic randomness
履歴
タイトル
Null-additivity in the theory of algorithmic randomness
種類
正論文
国際会議と雑誌
Abstract
ダウンロード
additive
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.
ダウンロード
Reducibilities relating to Schnorr randomness
履歴
2014年9月22日 受理
2014年3月24日 投稿
タイトル
Reducibilities relating to Schnorr randomness
種類
正論文
雑誌
Theory of Computing Systems, 58(3), 441-462, 2016.
DOI: 10.1007/s00224-014-9583-3
Abstract
Some measures of randomness have been introduced for Martin- L ̈of randomness such as K-reducibility, C-reducibility and vL-reducibility. In this paper we study Schnorr-randomness versions of these reducibilities. In particular, we characterize the computably-traceable reducibility via relative Schnorr randomness, which was asked in Nies’ book (Problem 8.4.22). We also show that Schnorr reducibility implies uniform-Schnorr-randomness version of vL-reducibility, which is the Schnorr-randomness version of the result that K-reducibility implies vL-reducibility.
ダウンロード
プレプリント