ランダムネスとコルモゴロフ複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/04 23:13 UTC 版)
「ペール・マルティン＝レーフ」の記事における「ランダムネスとコルモゴロフ複雑性」の解説
詳細は「アルゴリズム的ランダムな無限列」を参照 「 コルモゴロフ複雑性」および「 アルゴリズム情報理論」を参照 1964年から1965年にかけて、マルティン=レーフはアンドレイ・コルモゴロフの指導の下モスクワに留学した。1966年に論文「ランダム列の定義（The definition of random sequences）」を書き、ランダム列の初めての適切な定義を与えた。 確率論の初期の研究者であるリヒャルト・フォン・ミーゼスなどは、全てのランダム性の検定に合格するランダム列を定義するためにランダム性検定の概念を定式化することを試みたが、結局それは曖昧なままであった。マルティン=レーフの鍵となる洞察は、ランダム性の検定の概念を形式的に定義するために計算理論を用いるということであった。これは、確率のランダム性の考え方とは対照的である。ただし、その理論の中では、標本空間の特定の元をランダムであると言うことはできない。 マルティン＝レーフ・ランダムネスは、元の定義とは外見上ほとんど類似していない多くの等価な特徴、すなわち、圧縮性、ランダム性検定、そして賭け事に関するもの、があることが示されている。しかし、それら特徴のそれぞれについて、ランダム列が持っているべき性質に対する直観的な感覚を満たしていなければならない。すなわち、ランダム列は非圧縮的であり、ランダム性に関する統計検定は通過するべきであるし、それで賭け事をしたとしてもお金を稼ぐことは不可能であるべきである。マルティン＝レーフ・ランダム性に複数の定義が存在することと、異なる計算モデルの下でのこれら定義の安定性は、マルティン＝レーフ・ランダムネスが数学の基本的な性質であり、マルティン＝レーフの特定のモデルによってもたらされた偶然ではないことの証拠となっている。マルティン＝レーフ・ランダムネスの定義が「正確に」ランダムネスの直観的概念を捉えているという論文は、「マルティン＝レーフ・チャイティン論文」と呼ばれている。これはチャーチ＝チューリングのテーゼに幾分か類似している提言である。 マルティン＝レーフの研究の後、アルゴリズム情報理論は、ランダム文字列を、その文字列よりも短いプログラムからは生成できないものとして定義した（チャイティン＝コルモゴロフ複雑性）。すなわち、ある文字列のコルモゴロフ複雑性はその文字列の長さよりは小さいということである。これは統計学における用語の用法とは異なる意味である。統計学的ランダムネスは文字列を生成するプロセスを指す（たとえば、コインを投げて各ビットを生成するとランダム文字列が生成される）が、アルゴリズム的ランダムネスは文字列自体を指す。アルゴリズム情報理論は、用いられている計算モデルに対して比較的不変な方法で、ランダムでない文字列からランダムな文字列を分離する。 アルゴリズム的ランダムな無限列は文字の「無限」列であり、その全ての接頭部（おそらく有限の数を除いて）は、アルゴリズム的ランダムに極めて近い文字列である（その長さはコルモゴロフ複雑性の定数以下となる）。
※この「ランダムネスとコルモゴロフ複雑性」の解説は、「ペール・マルティン＝レーフ」の解説の一部です。
「ランダムネスとコルモゴロフ複雑性」を含む「ペール・マルティン＝レーフ」の記事については、「ペール・マルティン＝レーフ」の概要を参照ください。
- ランダムネスとコルモゴロフ複雑性のページへのリンク
