アルゴリズム的ランダムな無限列

アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、英: Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。

歴史

適切なランダムな列の定義を最初に与えたのはペール・マルティン＝レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。
マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。 マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ＝チャイティンのテーゼと呼ばれている。これは「チャーチ＝チューリングのテーゼ」と似たようなものである。

定義の解釈

コルモゴロフ複雑性による特徴付けはランダムな列は圧縮不可能であるという直感を与える。すなわちどんな接頭辞もそれよりもはるかに短いプログラムからは作られない。
ヌル被覆による特徴付けはランダムな実数は「普通でない」性質は持たないという直感を与える。測度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)の値から計算できるので、金額を計算することは賭けを計算することと同じである。マルチンゲールによる特徴付けはどんなコンピューターによって実装されるどんな賭け戦略も（たとえ必ずしも計算可能ではない弱い意味の構成可能な戦略であってでも）ランダムな列に対しては儲けることができないということを意味している。

相対的なランダムネス

マルティンレーフランダムの列のそれぞれの定義はチューリングマシンでの計算可能性を元にしているので、神託機械での計算可能性でも考えることができる。ある固定した神託Aに対して、列Bが、ランダムであるだけでなくAから見た計算可能性による同じ定義を満たすならば（例えばAから見た構成可能なマルチンゲールでBが成功しないならば）、BはAに対してランダムであると言う。二つの列がそれぞれランダムでも似た情報を持っているために互いにランダムではないということは起こりうる。ある列からもう一方へのチューリング還元が存在すれば、後者の列は前者の列から見てランダムではない。それはちょうど計算可能な列がランダムではないようなものである。特にチャイティンの停止確率\Omegaは停止性問題の集合から見てランダムではない。
相対的なランダムネスに関して重要な結果の一つが、van Lambalgenの定理である。これは列Cが列Aと列BからAの最初のビット、Bの最初のビット、Aの２番目のビットと交互に取って作られる列だとすると、Cがアルゴリズム的ランダムであるということとAがランダムでBがAから見てランダムであるということが同値であるという定理である。似た結論としてAとBがそれぞれランダムとすると、AがBから見てランダムであるということとBがAから見てランダムであることが同値になる。

マルティンレーフランダムより強いランダムネス

相対的なランダムネスはマルティンレーフランダムよりも強い最初のランダムネスの概念を与えてくれる、つまりある固定した神託Aからみたランダムネスである。どんな神託でも少なくとも同じくらい強いランダムであるし、多くの神託にとっては真に強いランダムネスである、なぜならAから見てランダムではないマルティンレーフランダムがあるだろうから。重要な神託でよく考察されるのが停止問題、\emptyset '、n回ジャンプの神託、\emptyset^{(n)}である。というのも、これらの神託が自然に起きる特定の問題に答えることができるからである。\emptyset^{(n-1)}から見てランダムな列はnランダムと呼ばれる。よって1ランダムとマルティンレーフランダムは同じである。すべてのnに対してnランダムである列は算術的ランダムと呼ばれる。nランダムな列はもっと複雑な性質を考えるときによく出てくる。例えば\Delta^0_2集合は可算個しかないので、ランダムとすべきではないと考えるかもしれない。しかしチャイティンの停止確率\Omegaは\Delta^0_2であり1ランダムである。2ランダムネス以上ならばランダムな集合が\Delta^0_2とはなり得ない。

マルティンレーフランダムより弱いランダムネス

さらにマルティンレーフランダムより弱いランダムネスも存在する。例えば、弱1ランダムネス、シュノアランダムネス、計算可能ランダムネス、部分計算可能ランダムネスなどである。またコルモゴロフ・ラブランドランダムネスはマルティンレーフランダムネスより強くないランダムネスとして知られているが、真に弱いかどうかは知られていない。