定義の解釈
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/04/21 00:17 UTC 版)
「アルゴリズム的ランダムな無限列」の記事における「定義の解釈」の解説
コルモゴロフ複雑性による特徴付けはランダムな列は圧縮不可能であるという直感を与える。すなわちどんな接頭辞もそれよりもはるかに短いプログラムからは作られない。 ヌル被覆による特徴付けはランダムな実数は「普通でない」性質は持たないという直感を与える。測度0の集合は普通はない性質と思うことができる。列がどの測度0の集合にも入らないことは不可能である、なぜなら1点集合は測度0であるからである。マルティンレーフの発想は測度0の集合を構成的に記述可能なものに制限することであった。すなわち構成可能なヌル被覆の定義は可算個の構成可能で記述可能な測度0の集合を与え、ランダムな列をそのような特別な測度0の集合に含まれないと定義したのである。測度0の集合の可算和は測度0であるから、この定義からランダムな列の測度1の集合があることが分かる。ここで二進列のカントール空間を[0,1]の実数区間と同一視すれば、カントール空間の測度はルベーグ測度に一致することに注意して欲しい。 マルチンゲールによる特徴付けはどんな構成可能なものでもランダムな列に対して儲けることができないという直感を与える。マルチンゲールdは賭けの戦略である。マルチンゲールdは有限文字列wを読んで次のビットにある金額を賭ける。持っている金額のいくらかを次のビットが0であることに賭け、残りを1であることに賭ける。dは実際に起こったビットに賭けた金額の2倍を受け取り、残りは失う。d(w)はw見た後の所持金である。文字列wを見た後の賭けはd(w)、d(w0)、d(w1)の値から計算できるので、金額を計算することは賭けを計算することと同じである。マルチンゲールによる特徴付けはどんなコンピューターによって実装されるどんな賭け戦略も（たとえ必ずしも計算可能ではない弱い意味の構成可能な戦略であってでも）ランダムな列に対しては儲けることができないということを意味している。
※この「定義の解釈」の解説は、「アルゴリズム的ランダムな無限列」の解説の一部です。
「定義の解釈」を含む「アルゴリズム的ランダムな無限列」の記事については、「アルゴリズム的ランダムな無限列」の概要を参照ください。
- 定義の解釈のページへのリンク
