アルゴリズム情報理論のソースを表示

'''アルゴリズム情報理論'''（あるごりずむじょうほうりろん、{{lang-en-short|Algorithmic information theory}}）は、[[情報理論]]と[[計算機科学]]の一分野であり、[[計算理論]]や[[情報科学]]とも関連がある。[[グレゴリー・チャイティン]]によれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である<ref>[http://www.cs.auckland.ac.nz/research/groups/CDMTCS/docs/ait.php Algorithmic Information Theory] [[オークランド大学]]</ref>。

== 概要 ==
アルゴリズム情報理論は、[[文字列]]（または他の[[データ構造]]）について[[コルモゴロフ複雑性]]や他の[[複雑性|複雑さ]]の尺度を研究する分野である。数学的オブジェクトの多くは文字列（または文字列の[[級数]]の極限）を使って表されるので、アルゴリズム情報理論は[[整数]]や[[実数]]を含む様々な数学的オブジェクトの研究に適用できる。

「情報」という用語は、圧縮性の概念に依存するので、その使用は少し誤解を招くかもしれない。アルゴリズム情報理論の観点から大雑把に言えば、文字列の情報量は、その文字列の最短の自己完結型表現の長さと等しい。自己完結型表現とは本質的には[[プログラム (コンピュータ)|プログラム]]であり、それを実行すると元の文字列が出力される。

百科事典は無作為な文字列よりもずっと有益だが、このような観点から見れば、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）。

== 正確な定義 ==
{{main|コルモゴロフ複雑性}}
バイナリ列がランダムであるとは、その文字列の[[コルモゴロフ複雑性]]が最低でもその文字列の長さである場合である。単純な数え上げでは任意長の文字列の一部はランダムであるとされ、その他の大部分もランダムに非常に近いとされる。コルモゴロフ複雑性は万能チューリング機械（大まかに言えば、「説明」が与えられる固定の「記述言語」）の固定された選択に依存するので、ランダムな文字列の集まりは固定の万能機械の選択に依存する。それにも関わらず、ランダムな文字列の集まりは全体として固定機械がどうであっても似たような性質を示すので、万能機械を最初に指定せずにランダムな文字列のグループの特性を論じることができ、実際そうすることが多い。

{{main|アルゴリズム的ランダムな無限列}}
無限バイナリ列がランダムであるとは、ある定数 ''c'' があり、全ての並びの最初のセグメント（長さ ''n''）の[[コルモゴロフ複雑性]]が最低でも ''n-c'' となる場合である。重要な点は、ここでの複雑性が接頭部のない複雑性だという点である。通常の複雑性を使うと、ランダムな列というものは存在しない。しかし、この定義では（標準的[[測度論]]、すなわち "fair coin" または[[ルベーグ測度]]の無限バイナリ列空間での観点での）ほとんど全ての並びがランダムとされる。また、2つの異なる万能機械があるとき、コルモゴロフ複雑性の差異は定数的なものに限られるため、無作為無限列の集まりは（有限文字列とは対照的に）万能機械の選択には依存しない。このような無作為性の定義を[[ペール・マルティン＝レーフ]]に因んでマルティン＝レーフ無作為性と呼び、他の無作為性の定義と区別する。

バイナリ（<math>\{0,1\}</math> をアルファベットとする文字列）以外にも同様の定義が可能である。

== 関連項目 ==
* [[コルモゴロフ複雑性]]
* [[アルゴリズム的ランダムな無限列]]
* [[チャイティンの定数]]
* [[アルゴリズム的確率]]
* [[認識論]]
* [[擬似乱数]]

== 脚注 ==
{{Reflist}}

== 外部リンク ==
* [http://www.scholarpedia.org/article/Algorithmic_information_theory Algorithmic Information Theory (Scholarpedia)]
* [http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/ch6.html Chaitin's account of the history of AIT].

{{DEFAULTSORT:あるこりすむしようほうりろん}}
[[Category:アルゴリズム的情報理論|*]]
[[Category:ランダム・アルゴリズム]]
[[Category:数学に関する記事]]