カテゴリー: Publication

投稿日:

Unified Characterizations of Lowness Properties via Kolmogorov Complexity

履歴
2014年1月19日投稿
2015年3月24日出版確認

タイトル
Unified Characterizations of Lowness Properties via Kolmogorov Complexity
(with T. Kihara)

種類
正論文

国際会議と雑誌
Archive for Mathematical Logic: Volume 54, Issue 3 (2015), Page 329-358
DOI: 10.1007/s00153-014-0413-8

Abstract
Consider a randomness notion $\mathcal C$.
A uniform test in the sense of $\mathcal C$ is a total computable procedure that each oracle $X$ produces a test relative to $X$ in the sense of $\mathcal C$.
We say that a binary sequence $Y$ is $\mathcal C$-random uniformly relative to $X$ if $Y$ passes all uniform $\mathcal C$ tests relative to $X$.

Suppose now we have a pair of randomness notions $\mathcal C$ and $\mathcal D$ where $\mathcal{C}\subseteq \mathcal{D}$, for instance Martin-L\”of randomness and Schnorr randomness. Several authors have characterized classes of the form Low($\mathcal C, \mathcal D$) which consist of the oracles $X$ that are so feeble that $\mathcal C \subseteq \mathcal D^X$. Our goal is to do the same when the randomness notion $\mathcal D$ is relativized uniformly: denote by Low$^\star$($\mathcal C, \mathcal D$) the class of oracles $X$ such that every $\mathcal C$-random is uniformly $\mathcal D$-random relative to $X$.

(1) We show that $X\in{\rm Low}^\star({\rm MLR},{\rm SR})$ if and only if $X$ is c.e.~tt-traceable if and only if $X$ is anticomplex if and only if $X$ is Martin-L\”of packing measure zero with respect to all computable dimension functions.

(2) We also show that $X\in{\rm Low}^\star({\rm SR},{\rm WR})$ if and only if $X$ is computably i.o.~tt-traceable if and only if $X$ is not totally complex if and only if $X$ is Schnorr Hausdorff measure zero with respect to all computable dimension functions.

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

投稿日:

Derandomization in Game-Theoretic Probability

履歴
2014年9月27日　Online
2014年8月3日　受理
2014年2月12日　投稿

タイトル
Derandomization in Game-Theoretic Probability
(with A. Takemura)

種類
正論文

国際会議と雑誌
Stochastic Processes and their Applications 125, 39-59, 2015

Abstract
We give a general method for constructing a deterministic strategy
of Reality from a randomized strategy in game-theoretic probability.
The construction can be seen as derandomization in game-theoretic probability.

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

投稿日:

Algorithmic randomness over general spaces

履歴
2014年5月出版
2013年12月受理
2012年5月改訂版を準備中
2011年9月改訂版を投稿
2010年5月25日ジャーナルに投稿中

タイトル
Algorithmic randomness over general spaces

種類
論文

ジャーナル
Math. Log. Quart. 60, No. 3, 184–204 (2014)
DOI 10.1002/malq.201200051

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