カテゴリー: Publication

履歴
2012年11月30日提出

タイトル
アルゴリズム的ランダムネスへの解析学的アプローチ
Analytical approach to algorithmic randomness

種類
論文

ジャーナル
数理解析研究所講究録
1832
Proof theory and complexity
証明論と複雑性
2013.4
2012/09/12–2012/09/14
pp.114-126

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

履歴
2013年2月受理
2012年9月26日arXivにアップロード
2012年8月投稿

タイトル
Van Lambalgen’s Theorem for uniformly relative Schnorr and computable randomness
(with Jason Rute)

種類
査読ありの事後会議録

国際会議と雑誌
Proceedings of the Twelfth Asian Logic Conference, World Scientific, 251-270

Abstract
We correct Miyabe’s proof of van Lambalgen’s Theorem for truth-table Schnorr randomness (which we will call uniformly rela- tive Schnorr randomness). An immediate corollary is one direction of van Lambalgen’s theorem for Schnorr randomness. It has been claimed in the literature that this corollary (and the analogous result for com- putable randomness) is a “straightforward modification of the proof of van Lambalgen’s Theorem.” This is not so, and we point out why. We also point out an error in Miyabe’s proof of van Lambalgen’s Theorem for truth-table reducible randomness (which we will call uniformly rel- ative computable randomness). While we do not fix the error, we do prove a weaker version of van Lambalgen’s Theorem where each half is computably random uniformly relative to the other.

ダウンロード
Download from arXiv

履歴
2013年3月　CiEにて発表受理，LNCSには非採択
2013年1月15日　投稿

タイトル
Lowness for uniform Kurtz randomness

種類
会議
T. Kiharaとの共著

雑誌
Sumitted

Abstract
We propose studying uniform Kurtz randomness, which is the uniform relativization of Kurtz randomness. One advantage of this notion is that lowness for uniform Kurtz randomness has many character- izations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.

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

この論文の結果は他の結果と一緒に別の論文に含める予定です．