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