投稿

投稿日:

アルゴリズム的情報理論

アルゴリズム的情報理論について日本語で触れられている書物を，思い出せる範囲でまとめておきましょう．

日経サイエンス 2006年6月号
「ゲーデルを超えて　オメガ数が示す数学の限界」
2006年なので，私が修士2年の時に読んだもの．
たぶん，この記事でランダムネスの理論を知った．

まずは，チャイティンの本
『数学の限界 』(2001)
『セクシーな数学―ゲーデルから芸術・科学まで』(2003)
『知の限界』(2006)
『メタマス!―オメガをめぐる数学の冒険』(2007)
やはり，こういう広報は重要だと感じる．

あと，ランダムの方向性から，触れられているものとして，
『ランダム―数学における偶然と秩序』ベルトラミ（2002)の第４章

情報の方向性から，
『インフォメーション: 情報技術の人類史』の第12章

数学的な解説としては，
渡辺治『計算論から見たランダムネス』(2006)
や
私の『ランダムネスの一般化』
などでしょうか．

他にもあったと思いますが，思い出したら，気がついたら，加えます．

投稿日:

$L^1$-computability, layerwise computability and Solovay reducibility

履歴
2013年7月17日出版
2013年3月27日受理
2012年9月19日投稿

タイトル
L1-computability, layerwise computability and Solovay reducibility

種類
正論文

国際会議と雑誌
Computability, 2:15-29, 2013.

Abstract
The class of the differences between two integral tests for Schnorr ran- domness is an important class related to Schnorr randomness. In this paper we study other randomness versions. We also claim that Solovay reducibility for lower semicomputable functions generalizes layerwise com- putability.

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

投稿日:

Uniform Kurtz randomness

履歴
2013年11月4日　オンライン
2013年5月16日　投稿

タイトル
Uniform Kurtz randomness
(with Takayuki Kihara)

種類
論文

雑誌
Journal of Logic and Computation, 24 (4): 863-882, 2014
doi: 10.1093/logcom/ext054

アブストラクト
We propose studying uniform Kurtz randomness, which is the uni- form relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen’s theorem holds for uniform Kurtz randomness while not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.

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