アルゴリズム情報理論
概要
編集
アルゴリズム情報理論は、文字列︵または他のデータ構造︶についてコルモゴロフ複雑性や他の複雑さの尺度を研究する分野である。数学的オブジェクトの多くは文字列︵または文字列の級数の極限︶を使って表されるので、アルゴリズム情報理論は整数や実数を含む様々な数学的オブジェクトの研究に適用できる。
﹁情報﹂という用語は、圧縮性の概念に依存するので、その使用は少し誤解を招くかもしれない。アルゴリズム情報理論の観点から大雑把に言えば、文字列の情報量は、その文字列の最短の自己完結型表現の長さと等しい。自己完結型表現とは本質的にはプログラムであり、それを実行すると元の文字列が出力される。
百科事典は無作為な文字列よりもずっと有益だが、このような観点から見れば、3000ページの百科事典と3000ページの完全に無作為な文字列とで、情報量に大きな差はない。これは、無作為の文字列を完全に再現するプログラムを考えたとき、多かれ少なかれ、個々の全ての文字を知る必要があるためである。一方、百科事典から全ての母音を削除したとき、英語をそれなりに知っていれば、それを再構築できる。それは例えば、適当な文脈と子音から成る "Ths sntnc hs lw nfrmtn cntnt" という一節から元の文を再構築できるようにである。このため、情報量の多い文字列は﹁ランダム﹂と呼ばれることがある。また、﹁情報﹂と﹁有益な情報﹂を区別するために、無作為な文字列が百科事典よりも情報量が多いという考え方から﹁有益な情報﹂を厳密に定義することがあるが、百科事典がより﹁有益な﹂情報を持つことは明らかである。
古典的情報理論とは異なり、アルゴリズム情報理論はコルモゴロフ複雑性と無作為無限列に形式的かつ厳密な定義を与える。その定義は、非決定性や尤度についての物理的または哲学的直観に依存しない。
アルゴリズム情報理論の結果の幾つか、例えばチャイティンの不完全性定理など、は一般的な数学的・哲学的直観を脅かすように見える。中でも特筆すべきはチャイティンの定数Ωの構成である。これは実数であり、self-delimiting な万能チューリングマシンに歪みの無いコインを次々にトスした裏表の結果を入力として与えたときに、そのチューリングマシンが停止する確率を表している︵ランダムなコンピュータプログラムが最終的に停止する確率、と考える場合もある︶。Ωを定義することは容易だが、無矛盾で公理的な如何なる理論を用いてもΩの有限個の桁しか計算できないので、ある意味不可知であり、凡そ知識というものに絶対的な限界を与える。これはゲーデルの不完全性定理を思い起こさせる。Ωの値を決定することは出来ないが、様々な性質は知られている。例えば、これはアルゴリズム的ランダム列であり、従ってこれを 0 と1の並びで表した場合の 0 と1の出現回数は均等︵実際に正規数︶である。
歴史
編集
この分野は、アンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンが1960年代に創始した。いくつかの派生があり、最も広く使われているのは Leonid Levin (1974年︶による self-delimiting program に基づくものである。ペール・マルティン＝レーフもこの分野に多大な貢献をしている。ブラムの公理︵Blum 1967年︶に基づくアルゴリズム情報理論の公理的アプローチは、Mark Burgin が1982年、アンドレイ・コルモゴロフの著作についての論文で提示した。アルゴリズム情報理論への公理的アプローチはその後本にまとめられ︵Burgin 2005︶、ソフトウェア測定法に応用されている︵Burgin and Debnath, 2003; Debnath and Burgin, 2003︶。
正確な定義
編集詳細は「コルモゴロフ複雑性」を参照
バイナリ列がランダムであるとは、その文字列のコルモゴロフ複雑性が最低でもその文字列の長さである場合である。単純な数え上げでは任意長の文字列の一部はランダムであるとされ、その他の大部分もランダムに非常に近いとされる。コルモゴロフ複雑性は万能チューリング機械︵大まかに言えば、﹁説明﹂が与えられる固定の﹁記述言語﹂︶の固定された選択に依存するので、ランダムな文字列の集まりは固定の万能機械の選択に依存する。それにも関わらず、ランダムな文字列の集まりは全体として固定機械がどうであっても似たような性質を示すので、万能機械を最初に指定せずにランダムな文字列のグループの特性を論じることができ、実際そうすることが多い。
詳細は「アルゴリズム的ランダムな無限列」を参照
無限バイナリ列がランダムであるとは、ある定数 cがあり、全ての並びの最初のセグメント︵長さ n︶のコルモゴロフ複雑性が最低でも n-c となる場合である。重要な点は、ここでの複雑性が接頭部のない複雑性だという点である。通常の複雑性を使うと、ランダムな列というものは存在しない。しかし、この定義では︵標準的測度論、すなわち "fair coin" またはルベーグ測度の無限バイナリ列空間での観点での︶ほとんど全ての並びがランダムとされる。また、2つの異なる万能機械があるとき、コルモゴロフ複雑性の差異は定数的なものに限られるため、無作為無限列の集まりは︵有限文字列とは対照的に︶万能機械の選択には依存しない。このような無作為性の定義をペール・マルティン＝レーフに因んでマルティン＝レーフ無作為性と呼び、他の無作為性の定義と区別する。
バイナリ︵
をアルファベットとする文字列︶以外にも同様の定義が可能である。
をアルファベットとする文字列︶以外にも同様の定義が可能である。