アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。適切なランダムな列の定義を最初に与えたのはペール・マルティン＝レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ＝チャイティンのテーゼと呼ばれている。これは「チャーチ＝チューリングのテーゼ」と似たようなものである。マルティンレーフによるランダムな列の元の定義は構成可能なヌルの被覆によるものである。すなわちランダムな列とは、そのようなどんな被覆にも含まれないことを言う。レオニード・レビンやクラウス・ピーター・シュノアがコルモゴロフ複雑性による次のような特徴付けを与えた。ある列がランダムであるとはその最初の有限部分の圧縮可能性に一様な下限があることを言う。シュノアはマルチンゲール（賭の戦略の一つ）を使って3つ目の同値な定義を与えた。LiとVitanyiの"An Introduction to Kolmogorov Complexity and Its Applications"はこれらの良い入門書であろう。コルモゴロフ複雑性による特徴付けはランダムな列は圧縮不可能であるという直感を与える。すなわちどんな接頭辞もそれよりもはるかに短いプログラムからは作られない。ヌル被覆による特徴付けはランダムな実数は「普通でない」性質は持たないという直感を与える。測度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"に対してランダムであると言う。二つの列がそれぞれランダムでも似た情報を持っているために互いにランダムではないということは起こりうる。ある列からもう一方へのチューリング還元が存在すれば、後者の列は前者の列から見てランダムではない。それはちょうど計算可能な列がランダムではないようなものである。特にチャイティンの停止確率formula_18は停止性問題の集合から見てランダムではない。相対的なランダムネスに関して重要な結果の一つが、van Lambalgenの定理である。これは列"C"が列"A"と列"B"から"A"の最初のビット、"B"の最初のビット、"A"の２番目のビットと交互に取って作られる列だとすると、"C"がアルゴリズム的ランダムであるということと"A"がランダムで"B"が"A"から見てランダムであるということが同値であるという定理である。似た結論として"A"と"B"がそれぞれランダムとすると、"A"が"B"から見てランダムであるということと"B"が"A"から見てランダムであることが同値になる。相対的なランダムネスはマルティンレーフランダムよりも強い最初のランダムネスの概念を与えてくれる、つまりある固定した神託"A"からみたランダムネスである。どんな神託でも少なくとも同じくらい強いランダムであるし、多くの神託にとっては真に強いランダムネスである、なぜなら"A"から見てランダムではないマルティンレーフランダムがあるだろうから。重要な神託でよく考察されるのが停止問題、formula_29、"n"回ジャンプの神託、formula_30である。というのも、これらの神託が自然に起きる特定の問題に答えることができるからである。formula_31から見てランダムな列は"n"ランダムと呼ばれる。よって1ランダムとマルティンレーフランダムは同じである。すべての"n"に対して"n"ランダムである列は算術的ランダムと呼ばれる。"n"ランダムな列はもっと複雑な性質を考えるときによく出てくる。例えばformula_22集合は可算個しかないので、ランダムとすべきではないと考えるかもしれない。しかしチャイティンの停止確率formula_18はformula_22であり1ランダムである。2ランダムネス以上ならばランダムな集合がformula_22とはなり得ない。さらにマルティンレーフランダムより弱いランダムネスも存在する。例えば、弱1ランダムネス、シュノアランダムネス、計算可能ランダムネス、部分計算可能ランダムネスなどである。またコルモゴロフ・ラブランドランダムネスはマルティンレーフランダムネスより強くないランダムネスとして知られているが、真に弱いかどうかは知られていない。

出典:wikipedia