アルゴリズム情報理論
アルゴリズム情報理論は、文字列(または他のデータ構造)についてコルモゴロフ複雑性や他の複雑さの尺度を研究する分野である。数学的オブジェクトの多くは文字列(または文字列の級数の極限)を使って表されるので、アルゴリズム情報理論は整数や実数を含む様々な数学的オブジェクトの研究に適用できる。
「情報」という用語は、圧縮性の概念に依存するので、その使用は少し誤解を招くかもしれない。アルゴリズム情報理論の観点から大雑把に言えば、文字列の情報量は、その文字列の最短の自己完結型表現の長さと等しい。自己完結型表現とは本質的にはプログラムであり、それを実行すると元の文字列が出力される。
百科事典は無作為な文字列よりもずっと有益だが、このような観点から見れば、3000ページの百科事典と3000ページの完全に無作為な文字列とで、情報量に大きな差はない。これは、無作為の文字列を完全に再現するプログラムを考えたとき、多かれ少なかれ、個々の全ての文字を知る必要があるためである。一方、百科事典から全ての母音を削除したとき、英語をそれなりに知っていれば、それを再構築できる。それは例えば、適当な文脈と子音から成る "Ths sntnc hs lw nfrmtn cntnt" という一節から元の文を再構築できるようにである。このため、情報量の多い文字列は「ランダム」と呼ばれることがある。
また、「情報」と「有益な情報」を区別するために、無作為な文字列が百科事典よりも情報量が多いという考え方から「有益な情報」を厳密に定義することがあるが、百科事典がより「有益な」情報を持つことは明らかである。
古典的情報理論とは異なり、アルゴリズム情報理論はコルモゴロフ複雑性と無作為無限列に形式的かつ厳密な定義を与える。その定義は、非決定性や尤度についての物理的または哲学的直観に依存しない。
アルゴリズム情報理論の結果の幾つか、例えばチャイティンの不完全性定理など、は一般的な数学的・哲学的直観を脅かすように見える。中でも特筆すべきはチャイティンの定数Ωの構成である。これは実数であり、self-delimiting な万能チューリングマシンに歪みの無いコインを次々にトスした裏表の結果を入力として与えたときに、そのチューリングマシンが停止する確率を表している(ランダムなコンピュータプログラムが最終的に停止する確率、と考える場合もある)。Ωを定義することは容易だが、無矛盾で公理的な如何なる理論を用いてもΩの有限個の桁しか計算できないので、ある意味不可知であり、凡そ知識というものに絶対的な限界を与える。これはゲーデルの不完全性定理を思い起こさせる。Ωの値を決定することは出来ないが、様々な性質は知られている。例えば、これはアルゴリズム的ランダム列であり、従ってこれを 0 と 1 の並びで表した場合の 0 と 1 の出現回数は均等(実際に正規数)である。