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

アルゴリズム的ランダムな無限列、または単にランダムな列とは、どのアルゴリズムに対しても見え方がランダムである二進数の無限列を指します。この概念は有限の文字列にも当てはまり、計算理論や情報理論において重要な役割を果たしています。

定義と概念

アルゴリズム的ランダム性は、特定の条件を満たす列を指し、特に情報圧縮や統計的テストなどで明確化されます。ここで一般に知られるのは、ペール・マルティン＝レーフによって定義された「マルティンレーフランダムネス」であり、他にも「強いランダムネス」や「弱いランダムネス」といったさまざまな概念があります。ランダムな列はしばしば「マルティンレーフランダム」と理解されます。

二進無限列は、単位区間の実数と同一視されるため、ランダムな二進無限列は時に「ランダムな実数」とも呼ばれます。さらに、二進列は自然数の集合の特性関数としても考えられ、自然数の集合として理解することもできます。

歴史

アルゴリズム的ランダム性の定義は1966年にペール・マルティン＝レーフによって初めて示されました。マルティン＝レーフ以前の研究者たち、特にリヒャルト・フォン・ミーゼスは、ランダムネスを定義するためにテストの概念を考えましたが、ランダムネスを正確に捉えるための試みには限界がありました。マルティン＝レーフは、計算理論を利用してランダムネスの定義を形式化したことで、より明確な基盤を提供しました。この定義は確率論におけるランダム性とは異なり、確率論では標本空間の特定の元をランダムと見なさないからです。

同値な定義

マルティン＝レーフによる初期の定義は、構成可能なヌル被覆を用いたものであり、ランダムな列がどのようなヌル被覆にも含まれないことを示しています。さらに、コルモゴロフ複雑性により、ランダムな列はその最初の有限部分の圧縮可能性に一様な下限が存在することが特徴づけられます。シュノアはマルチンゲールを用いて三つ目の同値な定義を導入しました。

コルモゴロフ複雑性

コルモゴロフ複雑性は、有限列がどれほど圧縮できるかを評価する指標であり、具体的には、特定のプログラミング言語に基づくコンピュータプログラムが与えられた有限列を生成するための最小の長さを考えます。一方、無限列がマルティンレーフランダムであるためには、全ての有限接頭辞が圧縮不可能である必要があります。

構成可能なヌル被覆

マルティン＝レーフの元の定義において、無限列がランダムであるためには、可算無限の構成可能なヌル被覆に含まれない必要があります。これは、構成可能な開集合が互いに包含関係を持つという特性から導かれています。

構成可能なマルチンゲール

マルチンゲールは賭けにおける戦略をモデル化したものであり、有限文字列に基づいて次のビットに対して賭けを行います。マルチンゲールdが無限列Sで成功するためには、最初のnビットに基づく評価が無限大に発散する必要があります。

定義の解釈

コルモゴロフ複雑性による特徴付けは、ランダムな列が圧縮不可能であるとの直感を与え、条件付きヌル被覆による特色は、ランダムな実数が普通でない性質を持たないことを示します。また、どんな構成可能なマルチンゲールもランダムな列で儲けられないことを示すことからも、マルティン＝レーフランダムの性質が浮かび上がります。

具体例と関連性

例えば、マルティン＝レーフランダム性の理論を元にしたチャイティンの停止確率Ωは有名なランダムな列の例です。また、ランダムな列は任意の高いチューリング次数に対してチューリング還元可能であることが示されており、さまざまな計算理論の側面からの重要な性質を持っています。相対的なランダム性についても考察があり、特定の神託から見たランダム性の定義も重要です。

最終的には、相対的なランダム性が提供する新しい視点からの研究が進められ、計算可能性や情報理論における新たな理解が深まることでしょう。

もう一度検索