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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/27 10:19 UTC 版)

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

歴史

適切なランダムな列の定義を最初に与えたのはペール・マルティン＝レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。

マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。 マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ＝チャイティンのテーゼと呼ばれている。これは「チャーチ＝チューリングのテーゼ」と似たようなものである。

3つの同値な定義

マルティンレーフによるランダムな列の元の定義は構成可能なヌルの被覆によるものである。すなわちランダムな列とは、そのようなどんな被覆にも含まれないことを言う。レオニード・レビンやクラウス・ピーター・シュノアがコルモゴロフ複雑性による次のような特徴付けを与えた。ある列がランダムであるとはその最初の有限部分の圧縮可能性に一様な下限があることを言う。シュノアはマルチンゲール（賭の戦略の一つ）を使って3つ目の同値な定義を与えた。LiとVitanyiのAn Introduction to Kolmogorov Complexity and Its Applicationsはこれらの良い入門書であろう。

• コルモゴロフ複雑性（シュノア1973、レビン1973）: コルモゴロフ複雑性は(文字もしくはビットの)有限列のアルゴリズム的圧縮可能性の下限と考えることができ、有限列wに対して自然数K(w)を対応させる。直感的には(ある固定のプログラミング言語で書かれた)コンピュータプログラムで入力なしでwを出力するものの最小の長さを測っている。ある自然数cとwに対して、wがc圧縮不可能であるとは、 $K(w)\geq |w|-c$