アルゴリズム情報理論

アルゴリズム情報理論( AIT ) は、理論計算機科学の一分野であり、文字列やその他のデータ構造など、計算可能オブジェクト (確率的に生成されるオブジェクトとは対照的に)の計算と情報の関係を扱います。言い換えれば、アルゴリズム情報理論では、計算の非圧縮性が (選択された汎用プログラミング言語にのみ依存する定数を除いて)情報理論に見られる関係や不等式を「模倣」することが示されています。^{[ 1 ]}グレゴリー・チャイティンによれば、それは「シャノンの情報理論とチューリングの計算可能性理論をカクテルシェーカーに入れて激しく振った結果」です。 ^{[ 2 ]}

計算可能なオブジェクトの還元不可能な情報内容の普遍的な尺度の形式化に加えて、AITの主な成果のいくつかは、次のようなことを示すことでした。実際、アルゴリズムの複雑さは、（自己限定的な場合）古典的な情報理論と同様に、エントロピーと同じ不等式（定数^{[ 3 ]}を除く）に従います。 ^{[ 1 ]}ランダム性は非圧縮性です。^{[ 4 ]}また、ランダムに生成されたソフトウェアの領域では、任意のデータ構造の発生確率は、ユニバーサルマシンで実行されたときにそれを生成する最短のプログラムのオーダーです。^{[ 5 ]}

AITは主に文字列（またはその他のデータ構造）の既約情報量の尺度を研究します。ほとんどの数学的対象は文字列、または文字列のシーケンスの極限として記述できるため、整数を含むさまざまな数学的対象を研究するために使用できます。AITの主な動機の1つは、メタ数学の分野のように、数学的対象が持つ情報そのものの研究です。たとえば、以下で述べた不完全性の結果が示すとおりです。その他の主な動機は、単一で固定された対象に対する古典的な情報理論の限界を超え、ランダム性の概念を形式化し、確率分布の事前知識（たとえば、独立同分布、マルコフ性、または定常性など）なしに意味のある確率的推論を見つけることから生じました。このように、AITは基本的に、アルゴリズム的複雑性、アルゴリズム的ランダム性、およびアルゴリズム的確率という3つの主要な数学的概念とそれらの間の関係に基づいていることが知られています。^{[ 6 ] [ 4 ]}

アルゴリズム情報理論は、主にデータ構造（最も一般的には文字列）の複雑性尺度を研究する分野です。ほとんどの数学的対象は文字列、あるいは文字列列の極限として記述できるため、整数を含む幅広い数学的対象を研究するために利用できます。

非公式に言えば、アルゴリズム情報理論の観点からすると、文字列の情報量は、その文字列を可能な限り圧縮した自己完結型表現の長さに相当する。自己完結型表現とは、本質的には、何らかの固定された（ただしそれ以外は無関係な）汎用プログラミング言語で記述されたプログラムであり、実行すると元の文字列を出力するものである。

この観点からすると、3000ページの百科事典は、3000ページにわたる完全にランダムな文字の羅列よりも情報量が少ないと言えます。百科事典の方がはるかに有用であるにもかかわらずです。なぜなら、ランダムな文字の羅列全体を再構築するには、すべての文字が何であるかを知っている必要があるからです。一方、百科事典からすべての母音を取り除けば、英語をある程度理解している人であればそれを再構築できます。ちょうど、文脈と残っている子音から「Ths sntnc hs lw nfrmtn cntnt」という文を再構築できるのと同じようにです。

古典情報理論とは異なり、アルゴリズム情報理論は、非決定性や尤度に関する物理的または哲学的直観に依存しない、ランダム文字列とランダム無限列の形式的かつ厳密な定義を与える。（ランダム文字列の集合は、コルモゴロフ複雑性を定義するために使用される汎用チューリングマシンの選択に依存するが、文字列のコルモゴロフ複雑性は汎用チューリングマシンの選択のみに依存する加法定数を除いて不変であるため、どの選択でも漸近結果は同一となる。このため、ランダム無限列の集合は汎用マシンの選択に依存しない。）

チャイティンの不完全性定理など、アルゴリズム情報理論の結果の中には、一般的な数学的および哲学的直観に挑戦するように見えるものがある。その中でも最も注目すべきは、チャイティン定数Ωの構成である。Ωは、自己限定型ユニバーサルチューリングマシンが、公平なコイン投げによって入力されたときに停止する確率を表す実数である（ランダムなコンピュータプログラムが最終的に停止する確率と考えることもある）。Ωは容易に定義できるが、一貫性のある公理化可能な理論では、 Ωの有限桁しか計算できないため、ある意味では知ることができない。これは、ゲーデルの不完全性定理を彷彿とさせる知識の絶対的な限界を提供する。Ωの桁を決定することはできないが、 Ωの多くの性質は知られている。例えば、Ωはアルゴリズム的にランダムな数列であり、したがってその2進数の桁は均等に分布している（実際には正規分布である）。

アルゴリズム情報理論は、^レイ・ソロモノフ[ ^{7 ]}によって創始されました。彼は、統計学におけるベイズの規則の適用に伴う深刻な問題を克服する方法であるアルゴリズム確率の発明の一部として、この分野の基礎となる基本的なアイデアを発表しました。彼は、1960年にカリフォルニア工科大学で開催された会議^{[ 8 ]}と、1960年2月の報告書「帰納的推論の一般理論に関する予備報告」^{[ 9 ]}で、その成果を初めて発表しました。アルゴリズム情報理論は、その後、1965年にアンドレイ・コルモゴロフ、 1966年頃にグレゴリー・チャイティン によって独立に発展しました。

コルモゴロフ複雑性またはアルゴリズム情報にはいくつかのバリエーションがあり、最も広く使用されているものは自己限定プログラムに基づくもので、主にレオニード・レヴィン（1974）によるものです。ペル・マルティン＝レーフも無限シーケンスの情報理論に大きく貢献しました。ブルム公理（ブルム 1967）に基づくアルゴリズム情報理論への公理的アプローチは、アンドレイ・コルモゴロフが出版のために提出した論文（ブルギン 1982）の中でマーク・バーギンによって導入されました。この公理的アプローチは、アルゴリズム情報理論における他のアプローチを包含しています。アルゴリズム情報のさまざまな尺度を、公理的に定義されたアルゴリズム情報の尺度の特殊なケースとして扱うことができます。基本的な不変性定理などの類似の定理を各特定の尺度について証明する代わりに、公理的設定で証明された1つの対応する定理から、そのようなすべての結果を容易に導出することができます。これは、数学における公理的アプローチの一般的な利点です。アルゴリズム情報理論への公理的アプローチは、書籍（Burgin 2005）でさらに発展し、ソフトウェアメトリクスに適用されました（Burgin and Debnath、2003; Debnath and Burgin、2003）。

バイナリ文字列は、その文字列のコルモゴロフ複雑度が文字列の長さ以上である場合にランダムであると言われます。簡単な数え上げの議論により、任意の長さの文字列の中にはランダムなものがあり、ほとんどすべての文字列はランダムに非常に近いことがわかります。コルモゴロフ複雑度は、固定された汎用チューリングマシン（非公式には、「記述」が与えられる固定された「記述言語」）の選択に依存するため、ランダム文字列の集合は、固定された汎用マシンの選択に依存します。しかしながら、ランダム文字列の集合全体としては、固定されたマシンに関係なく同様の特性を持つため、汎用マシンを最初に指定することなく、ランダム文字列の特性をグループとして議論することができます（そして実際によく議論されます）。

無限二進数列は、ある定数cに対して、すべてのnについて、その数列の長さnの最初のセグメントのコルモゴロフ複雑度が少なくともn − cである場合にランダムであると言われます。ほぼすべての数列 (無限二進数列の空間における標準的な測度、すなわち「公平なコイン」またはルベーグ測度の観点から) はランダムであることが示せます。また、2 つの異なるユニバーサル マシンに関するコルモゴロフ複雑度は最大で定数だけ異なることが示せるため、ランダムな無限数列の集合は (有限文字列とは対照的に) ユニバーサル マシンの選択に依存しません。このランダム性の定義は、他の類似したランダム性の概念と区別するために、通常、ペル・マルティン＝レーフにちなんでマルティン＝レーフランダム性と呼ばれます。また、他のより強いランダム性の概念 (2-ランダム性、3-ランダム性など) と区別するために、 1-ランダ​​ム性と呼ばれることもあります。マーティン・レーフのランダム性の概念に加えて、再帰的ランダム性、シュノールランダム性、クルツランダム性なども存在する。Yongge Wangは^{[ 10 ]}で、これらのランダム性の概念はすべて異なることを示した。  

（関連する定義は、このセット以外のアルファベットについても作成できます）${\displaystyle \{0,1\}}$）

アルゴリズム情報理論（AIT）は、コンピュータ科学を用いて個々の対象物の情報理論を研究するものであり、計算、情報、ランダム性の関係性に関心を寄せている。

オブジェクトの情報量や複雑さは、その最短記述の長さで測定できます。例えば、文字列

"0101010101010101010101010101010101010101010101010101010101010101"

短い説明には「'01' の 32 回繰り返し」とありますが、

"1100100001100001110111101110110011111010010000100101011110010110"

おそらく、文字列そのものを書き留める以外に簡単な説明はないだろう。

より厳密に言えば、文字列xのアルゴリズム的複雑度 (AC)は、固定された基準となる汎用コンピュータ上で実行される、 x を計算または出力する最短のプログラムの長さとして定義されます。

これと密接に関連する概念として、汎用コンピュータにランダムに選択されたプログラムを入力した際に、何らかの文字列xを出力する確率がある。このアルゴリズム的な「ソロモノフ」確率（AP）は、古くからある哲学的帰納法の問題を形式的に解決する上で重要な鍵となる。

ACとAPの主な欠点は、計算不可能であることです。時間制限付き「レヴィン」複雑性は、実行時間の対数をプログラムの長さに加算することで、遅いプログラムにペナルティを与えます。これにより、ACとAPの計算可能な変種が生まれ、普遍的な「レヴィン」探索（US）は、（非現実的に大きな乗法定数を除いて）すべての逆問題を最適時間で解決します。

ACとAPは、個々の文字列のランダム性を、非決定性や尤度に関する物理的または哲学的直観に依存しない、形式的かつ厳密な定義を可能にする。大まかに言えば、文字列のアルゴリズム的複雑性がその長さに等しいという意味で圧縮不可能であれば、その文字列はアルゴリズム的「マーティン＝レーフ」ランダム（AR）である。

AC、AP、ARはAITの中核となる分野ですが、AITは他にも多くの分野に広がっています。最小記述長（MDL）原理の基礎となり、計算複雑性理論における証明を簡略化したり、オブジェクト間の普遍的な類似性尺度を定義するために用いられたり、マクスウェルデーモン問題を解決したりするなど、多岐にわたる応用例があります。

• Scholarpediaのアルゴリズム情報理論
• チャイティンによるAITの歴史に関する記述。