カテゴリー: Publication

履歴
2018年3月19日 オンライン
2018年3月5日　JLA受理

タイトル
Randomness and Solovay degrees
(with A. Nies and F. Stephan)

種類
正論文

国際会議と雑誌
Journal of Logic and Analysis, Vol 10, pp.1–13, 2018.
Open access

Abstract
We consider the behaviour of Schnorr randomness, a randomness notion weaker than Martin-L\”of’s, for left-r.e. reals under Solovay reducibility. Contrasting with results on Martin-L\”of-randomenss, we show that Schnorr randomness is not upward closed in the Solovay degrees. Next, some left-r.e. Schnorr random $\alpha$ is the sum of two left-r.e. reals that are far from random. We also show that the left-r.e. reals of effective dimension $>r$, for some rational $r$, form a filter in the Solovay degrees.

ダウンロード

coromandel_JLA_final

履歴
2018年3月11日提出

タイトル
計算可能測度論

種類
総説論文

ジャーナル
数理解析研究所講究録
RIMS共同研究(公開型)証明論と証明活動
2017年12月25日〜27日

ダウンロード
rims

履歴

タイトル
Null-additivity in the theory of algorithmic randomness

種類
正論文

国際会議と雑誌

Abstract

ダウンロード
additive

履歴
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.

ダウンロード

履歴
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.

ダウンロード
プレプリント