低いKolmogorov complexityを持つ無限ビット列の特徴付け
スポンサーリンク
概要
- 論文の詳細を見る
無限ビット列のランダムネスの定義には、Kolmogorov complexityによる定義(Chaitin randomness)とtestによる定義(Martin-Lof randomness)がある。Chaitin randomnessとMartin-Lof randomnessは同値であることが知られている。したがって、高いKolmogorov complexityを持つ無限ビット列はtestにより特徴付けられる。本稿では、部分的にランダムな無限ビット列の、Martin-Lof randomenessに類似したある特徴付けを提案する。またこの特徴付けと、低いKolmogorov complexityを持つ無限ビット列との関係について考察する。
- 社団法人電子情報通信学会の論文
- 1995-04-21
著者
関連論文
- universal distributionの構成について
- 42. あつかいにくい問題 (アルゴリズムの最近の動向)
- 低いKolmogorov complexityを持つ無限ビット列の特徴付け
- On Malign Input Distributions for Algorithms(Mathematical Logic and Applications'92)
- malign measureによるa priori measureの特徴づけについて(理論計算機科学とその周辺)
- A Note on Collapsing Bounded Query Classes
- 無限列の圧縮可能性 (数理情報科学の研究)