コルモゴロフ複雑性

アルゴリズム情報理論（コンピュータ科学と数学のサブ分野）では、テキストなどのオブジェクトのコルモゴロフ複雑度は、そのオブジェクトを出力として生成する最短のコンピュータプログラム（あらかじめ定められたプログラミング言語）の長さです。これは、オブジェクトを指定するために必要な計算リソースの尺度であり、アルゴリズム複雑度、ソロモノフ・コルモゴロフ・チャイティン複雑度、プログラムサイズ複雑度、記述的複雑度、またはアルゴリズムエントロピーとしても知られています。これは、 1963年にこの主題について初めて発表したアンドレイ・コルモゴロフにちなんで名付けられており^{[ 1 ]}^{[注1 ]}、古典的な情報理論の一般化です。

コルモゴロフ複雑性の概念は、カントールの対角線論法、ゲーデルの不完全性定理、チューリングの停止問題に類似した不可能性の結果を述べ、証明するために使用できます。特に、各テキストのコルモゴロフ複雑性の下限を計算するプログラムPは、 P自身の長さよりも本質的に大きい値を返すことはできません (セクション § チャイティンの不完全性定理を参照)。したがって、単一のプログラムで無限に多くのテキストの正確なコルモゴロフ複雑性を計算することはできません。

意味

直感

次の2つの文字列は、それぞれ32個の小文字の英字と数字で構成されています。

abababababababababababababababab、そして

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

最初の文字列には、「write ab 16 times」という短い英語の説明があり、これは17文字です。2番目の文字列には、文字列自体を書き出す以外に（同じ文字セットを使用して）明確な簡単な説明はありません。つまり、「write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7」という文字列は38文字です。したがって、最初の文字列を書き出す操作は、2番目の文字列を書き出す操作よりも「複雑さが少ない」と言えます。

より厳密に言えば、文字列の複雑性とは、ある固定された普遍的な記述言語で文字列を記述した最短の長さのことである（記述言語の選択に対する複雑性の感度については後述する）。任意の文字列のコルモゴロフ複雑性は、文字列自体の長さより数バイト以上大きくなることはないことが示される。上記のababの例のように、コルモゴロフ複雑性が文字列のサイズに比べて小さい文字列は、複雑とはみなされない。

コルモゴロフ複雑性は任意の数学的対象に対して定義できますが、簡潔にするため、この記事では文字列に限定します。まず、文字列の記述言語を指定する必要があります。このような記述言語は、Lisp、Pascal、Javaなどの任意のコンピュータプログラミング言語に基づいて作成できます。Pが文字列xを出力するプログラムである場合、Pはxの記述です。記述の長さは、文字文字列としてのPの長さに、文字のビット数（ASCIIの場合は7 ）を掛けたものです。

あるいは、チューリングマシンのエンコーディングを選択することもできます。エンコーディングとは、各チューリングマシンMにビット列<M>を対応付ける関数です。Mが入力wに対して文字列xを出力するチューリングマシンである場合、連結された文字列<M> wはxの記述となります。理論的な分析においては、このアプローチは詳細な形式的証明の構築に適しており、研究文献では一般的に好まれています。本稿では、非形式的なアプローチについて議論します。

任意の文字列sには少なくとも1つの説明があります。たとえば、上記の2番目の文字列は、次の擬似コードによって出力されます。

def generate_string2 (): return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

一方、最初の文字列は（はるかに短い）擬似コードによって出力されます。

def generate_string1 (): return "ab" × 16

文字列sの記述d ( s ) が最小長 (つまり、使用するビット数が最小) である場合、それはsの最小記述と呼ばれ、 d ( s )の長さ(つまり、最小記述のビット数) はsのコルモゴロフ複雑度K ( s ) と呼ばれます。記号的には、

K ( s ) = | d ( s )|。

最短記述の長さは記述言語の選択によって決まりますが、言語を変更することによる影響は限定されます（これは不変性定理と呼ばれる結果です。下記参照）。

単純なコルモゴロフ複雑度C

コルモゴロフ複雑性には、プレーンとプレフィックスフリーの 2 つの定義があります。プレーン複雑性とは、任意のプログラムの最小記述長であり、次のように表されます。 $C(x)$ プレフィックスフリー複雑度は、プレフィックスフリーコードでエンコードされた任意のプログラムの最小記述長であり、次のように表される。 $K(x)$ 単純な複雑性の方が直感的だが、接頭辞のない複雑性の方が研究しやすい。

デフォルトでは、すべての式は加法定数を除いてのみ成り立ちます。たとえば、 $f(x)=g(x)$ つまり、 $f(x)=g(x)+O(1)$ つまり、 $\exists c,\forall x,|f(x)-g(x)|\leq c$ 。

させて $U:2^{*}\to 2^{*}$ 有限バイナリ文字列をバイナリ文字列にマッピングする計算可能な関数である。任意の計算可能なに対して、が成り立つ場合に限り、は普遍関数である。 $f:2^{*}\to 2^{*}$ 関数を「プログラム」としてエンコードすることができます $s_f$ 、したがって $\forall x\in 2^{*},U(s_{f}x)=f(x)$ 考えてみましょう $U$ プログラムインタプリタとして、プログラムの説明を記述した最初のセグメントと、それに続いてプログラムが処理すべきデータを受け取ります。

単純な複雑さの問題の1つは、 $C(xy)\not <C(x)+C(y)$ 直感的に言えば、連結された文字列を見ただけで出力文字列をどこで分割するかを判断する一般的な方法はないからです。長さを指定することで分割できます。 $x$ または $y$ しかし、それには $O(\min(\ln x,\ln y))$ 追加のシンボル。実際、どんな $c>0$ 存在する $x,y$ そのため $C(xy)\geq C(x)+C(y)+c$ [ ²^]

通常、単純な複雑さを持つ不等式には次のような項があります。 $O(\min(\ln x,\ln y))$ 一方、接頭辞のない複雑さを持つ同じ不等式は、 $O(1)$ 。

単純な複雑さの主な問題は、プログラムに何か余分なものがこっそりと忍び込んでいるということです。プログラムはコードで何かを表現するだけでなく、その長さも表現します。特に、プログラムは $x$ バイナリ数を表すことができる $\log _{2}|x|$ 単にその長さによるものです。言い換えれば、単語の終わりを示すために終端記号を使用しているようなもので、2 つの記号ではなく 3 つの記号を使用していることになります。この欠点を修正するために、接頭辞のないコルモゴロフ複雑性を導入します。^{[ 3 ]}

接頭辞なしコルモゴロフ複雑度K

接頭辞のない普遍チューリングマシンは普遍部分計算可能関数である $U:2^{*}\rightarrow 2^{*}$ そのドメインは、接頭辞のないバイナリ文字列の集合です。同様に、有効なプログラムは存在しません。 $U$ が他の任意の接頭辞である場合、ドメインは接頭辞特性を満たします。たとえば、ユニバーサルチューリングマシンのすべての有効なプログラムが $U$ プログラムの他の場所では出現できない終了文字列で終了しました。 $U$ 接頭辞は不要になります。

文字列の接頭辞なしコルモゴロフ複雑度 $x$ 定義される $K(x):=\min\{|c|:U(c)=x\}$ 最短の自己限定プログラムの長さ $U$ 出力 $x$ 。

接頭辞のない汎用マシンのさまざまな選択肢が $K(x)$ 最大で加算定数による。^{[ 4 ]}

不変性定理

非公式な治療

次のような意味で最適な記述言語がいくつか存在する。すなわち、ある記述言語でオブジェクトを記述した場合、その記述は一定のオーバーヘッドで最適な記述言語に利用できる。この一定のオーバーヘッドは、関連する言語のみに依存し、オブジェクトの記述内容や記述対象のオブジェクト自体には依存しない。

最適な記述言語の例を以下に示します。記述は2つの部分から構成されます。

最初の部分では、別の記述言語について説明します。
2つ目の部分は、その言語でオブジェクトを説明するものです。

より技術的な用語で言うと、記述の最初の部分はコンピュータプログラム（具体的には、記述言語で書かれた、対象物の言語用のコンパイラ）であり、2番目の部分は、そのコンピュータプログラムへの入力であり、出力として対象物を生成する。

不変性定理は次の通りである。任意の記述言語Lが与えられた場合、最適な記述言語は、一定のオーバーヘッドを伴うものの、少なくともLと同等の効率性を持つ。

証明：L内の任意の記述D は、まずL をコンピュータプログラムPとして記述し（パート 1）、次に元の記述D をそのプログラムへの入力として使用することによって（パート 2）、最適言語での記述に変換できます。この新しい記述D ′の全長は（おおよそ）次のようになります。

| D ′ | = | P | + | D |

Pの長さは定数であり、Dに依存しません。したがって、記述対象に関わらず、オーバーヘッドは最大でも定数です。そのため、最適な言語はこの加算定数を除いて普遍的です。

より正式な扱い

定理： K ₁とK _{2 が}チューリング完全記述言語L ₁とL ₂に関する複雑性関数である場合、選択された言語L ₁とL ₂のみに依存する定数cが存在し、

\forall s.-c\leq K_{1}(s)-K_{2}(s)\leq c

。

証明：対称性により、すべての文字列sに対して、ある定数cが存在し、

K_{1}(s)\leq K_{2}(s)+c

。

ここで、言語L1で書かれたプログラムが_、_言語L2のインタプリタとして機能すると仮定します。

def interpret_language ( p : str )

ここで、pはL2_のプログラムである。インタプリタは以下の特性によって特徴付けられる。

interpret_language入力pに対して実行すると、 pを実行した結果が返されます。

したがって、P がsの最小記述であるL ₂のプログラムである場合、( P ) は文字列sを返します。このsの記述の長さは、interpret_language

プログラムの長さはinterpret_language定数cとみなすことができます。
Pの長さは定義によりK ₂ ( s ) です。

これは、望ましい上限値を証明するものである。

歴史と背景

アルゴリズム情報理論は、文字列（またはその他のデータ構造）におけるコルモゴロフ複雑度やその他の複雑度尺度を研究するコンピュータ科学の分野です。

コルモゴロフ複雑性の概念と理論は、レイ・ソロモノフが最初に発見した重要な定理に基づいています。ソロモノフは1960年にこの定理を発表し、「帰納的推論の一般理論に関する予備報告」^{[ 5 ]}の中で、アルゴリズム確率の発明の一部としてこの定理を説明しました。彼は1964年の出版物「帰納的推論の形式理論」、Information and Controlのパート1とパート2で、より完全な説明を与えました。^{[ 6 ]}^{[ 7 ]}

アンドレイ・コルモゴロフは後にこの定理を1965年にProblems Inform. Transmissionで独自に発表した。 ^[⁸^]グレゴリー・チャイティンもこの定理をJournal of the ACMで発表している。チャイティンの論文は1966年10月に提出され、1968年12月に改訂され、ソロモノフとコルモゴロフの論文の両方を引用している。^[⁹^]

この定理は、文字列をその記述（コード）から復号するアルゴリズムの中で、最適なアルゴリズムが存在することを述べている。このアルゴリズムは、あらゆる文字列に対して、他のどのアルゴリズムでも許容される最短のコードを、アルゴリズムに依存するが文字列自体には依存しない加算定数を除いて許容する。ソロモノフはこのアルゴリズムと、それが許容するコード長を用いて、文字列の「普遍的確率」を定義し、それに基づいて文字列の次の桁を帰納的に推論できるとした。コルモゴロフはこの定理を用いて、文字列の複雑性、ランダム性、情報量など、いくつかの関数を定義した。

コルモゴロフはソロモノフの研究を知ったとき、ソロモノフの優先権を認めた。^{[ 10 ]}数年間、ソロモノフの研究は西側諸国よりもソ連でよく知られていた。しかし、科学界の一般的な見解は、この種の複雑性を、数列のランダム性に関心を持っていたコルモゴロフと結びつけることであり、アルゴリズム的確率は、普遍事前確率分布の発明を用いた予測に焦点を当てたソロモノフと結びつけられるようになった。記述的複雑性と確率を含むより広い領域は、しばしばコルモゴロフ複雑性と呼ばれる。コンピュータ科学者のミン・リーはこれをマタイ効果の一例と見なしている。「持っている者には、さらに与えられるだろう」^{[ 11 ]}

コルモゴロフ複雑性またはアルゴリズム情報には、他にもいくつかのバリエーションが存在する。最も広く用いられているのは自己限定プログラムに基づくもので、主にレオニード・レヴィン（1974）によるものである。

マーク・バーギンは、アンドレイ・コルモゴロフが発表のために提出した論文の中で、ブルムの公理（ブルム 1967）に基づくコルモゴロフ複雑性への公理的アプローチを紹介した。 ^{[ 12 ]}

基本的な結果

私たちは書く $K(x,y)$ である $K((x,y))$ 、どこ $(x,y)$ これは、文字列のタプル x と y をコード化するための何らかの固定された方法を意味します。

不平等

加算因子を省略します $O(1)$ ^{このセクションは、 [}⁴^]に基づいています。

定理。 $K(x)\leq C(x)+2\log _{2}C(x)$

証明。単純な複雑性を定義するために使用される汎用チューリングマシンの任意のプログラムを取り上げ、まずプログラムの長さをバイナリで符号化し、次にその長さをプレフィックスフリーの符号化に変換することによって、プレフィックスフリーのプログラムに変換します。たとえば、プログラムの長さが9であると仮定すると、次のように変換できます。 $9\mapsto 1001\mapsto 11-00-00-11-\color {red}{01}$ ここでは各桁を2倍にし、終端コードを追加します。プレフィックスフリーの汎用チューリングマシンは、他のマシン用のプログラムを次のように読み込むことができます。 $[{\text{他のマシンをシミュレートするためのコード}}][{\text{プログラムのコード化された長さ}}][{\text{プログラム}}]$ 最初の部分は、別のマシンをシミュレートするようにマシンをプログラムするもので、一定のオーバーヘッドとなる。 $O(1)$ 2番目の部分は長さが $\displaystyle \leq 2\log _{2}C(x)+3}$ 3番目の部分は長さが $C(x)$ 。

定理：存在する $c$ そのため $\forall x,C(x)\leq |x|+c$ より簡潔に言うと、 $C(x)\leq |x|$ 同様に、 $K(x)\leq |x|+2\log _{2}|x|$ 、そして $K(x||x|)\leq |x|$ 。

証明。単純な計算量については、入力をそのまま出力にコピーするだけのプログラムを書けばよい。接頭辞不要の計算量については、文字列自体を書き出す前に、まず文字列の長さを記述する必要がある。

定理。（追加情報限界、劣加法性）

$K(x|y)\leq K(x)\leq K(x,y)\leq \max(K(x|y)+K(y),K(y|x)+K(x))\leq K(x)+K(y)$
$K(xy)\leq K(x,y)$

比較する方法がないことに注意してください $K(xy)$ そして $K(x|y)$ または $K(x)$ または $K(y|x)$ または $K(y)$ 文字列全体が $xy$ は簡単に説明できるが、その部分文字列を説明するのは非常に難しい。

定理（情報の対称性） $K(x,y)=K(x|y,K(y))+K(y)=K(y,x)$ 。

証明。片側は簡単。もう片側は $K(x,y)\geq K(x|y,K(y))+K(y)$ そのため、数え上げの議論を用いる必要がある（38ページ^{[ 13 ]}）。

定理（情報非増加）任意の計算可能な関数に対して $f$ 、我々は持っています $K(f(x))\leq K(x)+K(f)$ 。

証明。チューリングマシンに、関数を記述するプログラムと文字列を記述するプログラムの2つを連続して読み込むようにプログラムする。次に、両方のプログラムをワークテープ上で実行して、 $f(x)$ そして、それを書き出してください。

コルモゴロフ複雑性の計算不可能性

Kを計算するプログラムの素朴な試み

一見すると、次のような任意のsに対してK ( s )を計算できるプログラムを書くのは簡単そうに見えるかもしれません。

def kolmogorov_complexity ( s : str ): for i = 1 to infinity : for each string p of length exactly i if is_valid_program ( p ) and evaluate ( p ) == s return i

このプログラムは、最短のプログラムから順に、考えられるすべてのプログラム（考えられるすべての文字列を順に調べ、有効なプログラムのみを考慮する）を順番に処理します。各プログラムを実行して、その結果を入力sと比較します。結果が一致すれば、プログラムの長さが返されます。

しかし、テスト対象のプログラムの中には、例えば無限ループを含むものなど、終了しないものがあるため、この方法はうまくいきません。停止問題の計算不可能性のため、実行前に何らかの方法でテストすることで、これらのプログラムをすべて回避する方法はありません。

さらに、どんなに高度なプログラムであっても、関数Kを計算することは不可能である。これは以下で証明される。

Kの計算不能性の形式的証明

定理：コルモゴロフ複雑度が任意に大きい文字列が存在する。形式的には、任意の自然数nに対して、 K ( s ) ≥ nとなる文字列sが存在する。^[^{注 2}^]

証明:そうでなければ、無限に存在するすべての可能な有限文字列は、nビット未満の複雑さを持つ有限個の^{[注 3 ]}プログラムによって生成されてしまうことになる。

定理： Kは計算可能な関数ではない。言い換えれば、任意の文字列sを入力として受け取り、整数K ( s )を出力するプログラムは存在しない。

以下の背理法による 証明では、プログラムを表すために単純なPascalライクな言語を使用します。証明を簡潔にするために、その記述（つまりインタプリタ）の長さをと仮定します。1,400,000ビット。矛盾を導くために、プログラムが存在すると仮定します。

def kolmogorov_complexity ( s : str )

これは文字列sを入力として受け取り、K ( s ) を返します。すべてのプログラムは有限長なので、証明を簡単にするために、次のように仮定します。7,000,000,000ビット。次に、長さの次のプログラムを考えてみましょう。1288ビット:

def generate_complex_string (): str for i = 1 to infinity : for each string s of length exactly i if kolmogorov_complexity ( s ) >= 8000000000 return s

サブルーチンとしてkolmogorov_complexity、プログラムは最短の文字列から始めて、少なくともコルモゴロフ複雑度を持つ文字列を返すまで、すべての文字列を試します。8,000,000,000ビット、^[注4 ]^つまり、それより短いプログラムでは生成できない文字列8,000,000,000ビット。ただし、 sを生成した上記のプログラムの全体の長さはわずかです。7,001,401,288ビット[^注5^]は矛盾して^いる。（のコードがKolmogorovComplexity短い場合は矛盾は残る。長い場合は、で使用される定数を適切GenerateComplexStringに変更することができる。）^{[注6 ]}

_{上記の証明は、}ベリーのパラドックスと同様の矛盾を利用している。「₁ 2最小の₃正の4_整数5 ₆_定義できない_{7 8}₉₁₀₁₁₂₀未満の英語の単語で定義できない₁₂ 13 ₁₄ 」。KとH は_{チューリング}等価であるため、停止問題Hの計算不能性から還元することによってKの計算不能性を示すことも可能である。^[¹⁴^]

プログラミング言語コミュニティでは、ユーモラスに「完全雇用定理」と呼ばれる派生的な法則があり、それは完璧なサイズ最適化コンパイラは存在しないというものである。

コルモゴロフ複雑性に対する連鎖律

コルモゴロフ複雑性に関する連鎖律^{[ 15 ]}は、すべてのXとYに対して、定数cが存在し、次のようになると述べている。

K(X,Y)=K(X)+K(Y|X)+c\cdot max(1,log(K(X,Y)))

。

これは、 XとYを再現する最短プログラムは、Xを再現するプログラムと、Xが与えられた場合にYを再現するプログラムの合計よりも対数的に小さい項だけ大きい、ということを述べている。この記述を用いることで、コルモゴロフ複雑性に対する相互情報量の類似概念を定義できる。

圧縮

K ( s )の上限を計算するのは簡単です。文字列sを何らかの方法で圧縮し、選択した言語で対応する解凍器を実装し、解凍器を圧縮された文字列に連結し、結果として得られる文字列の長さ、具体的には、指定された言語での自己解凍アーカイブのサイズを測定します。

文字列s は、その記述の長さが | s | - cビットを超えない場合、数cで圧縮可能である。これは、 $K$ $($ $s$ $) \leq$ $|$ $s$ $|$ $-$ $c$ と同等である。そうでない場合、sはcで圧縮不可能である。1 で圧縮不可能な文字列は、単に圧縮不可能であると言われる。これは、圧縮された文字列はすべて 1 つの非圧縮文字列にマッピングされるため適用される鳩の巣原理により、長さnの²ⁿビットの文字列が存在するが、長さが n より短い文字列、つまり長さがn未満の文字列(長さ 0、1、...、n - 1) は²ⁿ - 1 個しかないため、圧縮不可能な文字列が存在する必要があるからである。^[^{注 7}^]

同じ理由で、ほとんどの文字列は、大幅に圧縮できないという意味で複雑です。つまり、 K ( s )は、 sのビット長である | s |よりそれほど小さくありません。これを正確にするために、 nの値を固定します。長さnのビット列は²ⁿ個あります。これらのビット列の空間上の一様確率分布は、長さnの各文字列に正確に等しい重み 2 ^-ⁿを割り当てます。

定理：長さnのビット列の空間における一様確率分布では、文字列がcによって圧縮されない確率は少なくとも $1 - 2 - c +1 + 2 - n$ である。

この定理を証明するために、長さがn − cを超えない記述の数は、等比数列で与えられることに注意してください。

1 + 2 + 2 ² + ... + 2 ^{n − c} = 2 ^{n − c +1} − 1。

少なくとも

2n ⁻ 2n ⁻^c^{+1 +} 1

cで圧縮できない長さnのビット列。確率を求めるには、2 ⁿで割ります。

チャイティンの不完全性定理

上記の定理（§ 圧縮）によれば、ほとんどの文字列は、著しく「圧縮」された方法で記述できないという意味で複雑です。しかし、文字列の複雑さが一定の閾値を超えると、特定の文字列が複雑であるという事実を形式的に証明できないことが判明しました。正確な形式化は次のとおりです。まず、自然数に関する特定の公理系Sを固定します。この公理系は、文字列の複雑さに関する特定の主張 Aに対して、 S内の式FA_を関連付けることができるほど強力でなければなりません。この関連付けは次の性質を持たなければなりません。

FA_がSの公理から証明可能であれば、対応する主張Aは真でなければならない。この「形式化」はゲーデル番号付けに基づいて実現できる。

定理：定数Lが存在し、(L はSと記述言語の選択のみに依存する)文が成り立つような文字列s は存在しない。

K(s)\geq L

（ Sで形式化されたもの）

S内で証明できる。^{[ 16 ]}^{[ 17 ]}

証明のアイデア：この結果の証明は、ベリーのパラドックスで使用されている自己参照的な構成をモデルにしています。まず、 S内の証明を列挙するプログラムを取得し、整数Lを入力として受け取り、 S内の命題K ( x ) ≥ Lの証明に含まれる文字列xを出力する手続きPを指定します。次に、L をこの手続きPの長さよりも大きく設定すると、 K ( x ) ≥ Lで述べられているように、少なくともLであるx を出力するために必要なプログラムの長さは、手続きPによって文字列xが出力されたため、 Lより小さくなります。これは矛盾です。したがって、証明システムSでは、 Lが任意に大きい場合、特に手続き P の長さ (有限) よりも大きい場合、K ( x ) ≥ Lを証明することはできません。

証拠：

Sに含まれるすべての形式的証明の有効な列挙は、何らかの手順によって見つけることができる。

def nth_proof ( n : int )

これは入力としてn を受け取り、何らかの証明を出力します。この関数はすべての証明を列挙します。これらの証明の中には、ここでは重要でない式の証明も含まれています。なぜなら、Sの言語におけるすべての可能な証明は、何らかのnに対して生成されるからです。これらの証明の中には、 Sの言語における定数sとnを含むK ( s ) ≥ nの形式の複雑性式も含まれています。手順があります。

def nth_proof_proves_complexity_formula ( n : int ): bool

これは、n番目の証明が実際に複雑性式K ( s ) ≥ Lを証明しているかどうかを判定する。文字列sと整数Lは、それぞれ次の手順で計算できる。

def string_nth_proof ( n : int )

def complexity_lower_bound_nth_proof ( n : int ): int

以下の手順を検討してください。

def generate_provably_complex_string ( n : int ): for i = 1 to infinity : if nth_proof_proves_complexity_formula ( i ) and complexity_lower_bound_nth_proof ( i ) ≥ n return string_nth_proof ( i )

与えられた $n$ この手順では、式を表す形式体系Sにおいて文字列と証明が見つかるまで、すべての証明を試します。 $K(s)\geq L$ 一部の人にとって $L\geq n$ ; そのような証明が存在しない場合は、無限ループに陥ります。

最後に、これらすべての手続き定義とメイン関数呼び出しから構成されるプログラムを考えてみましょう。

generate_provably_complex_string ( n ₀ )

定数 $n_{0}$ 後ほど決定します。プログラム全体の長さは次のように表すことができます。 $U+log_{2}(n_{0})$ 、どこ $U$ は定数であり、 $log_{2}(n_{0})$ 整数値の長さを表します $n_{0}$ バイナリ数字でエンコードされているという妥当な仮定の下で、 $n_{0}$ プログラムの長さよりも大きい、つまり、 $n_{0}>U+log_{2}(n_{0})$ これは明らかに次のとおりです。 $n_{0}$ 十分に大きいので、左辺は線形に増加する。 $n_{0}$ 右辺は対数的に増加するが、 $n_{0}$ 固定定数まで $U$ 。

すると、次の形式の証明は得られない。 $K(s)\geq L$ " と $L\geq n_{0}$ 間接的な引数からわかるように、Sで取得できます。complexity_lower_bound_nth_proof(i) $\displaystyle \geq n_{0}}$ すると、内部のループはgenerate_provably_complex_string最終的に終了し、その手順は次のような文字列sを返します。

これは矛盾である、証明終了

その結果、上記のプログラムは、選択された値で $n_{0}$ 、永遠にループする必要があります。

同様の考え方は、チャイティン定数の性質を証明するためにも用いられる。

最小メッセージ文字数

統計的推論と帰納的推論および機械学習の最小メッセージ長原理は、 1968 年にCS Wallaceと DM Boulton によって開発されました。MML はベイズ的（つまり、事前の信念を取り入れている）かつ情報理論的です。統計的不変性（つまり、極座標からデカルト座標への再パラメータ化などによって推論が変換される）、統計的一貫性（つまり、非常に難しい問題であっても、MML は任意の基礎モデルに収束する）、および効率性（つまり、MML モデルは可能な限り速く任意の真の基礎モデルに収束する）という望ましい特性を備えています。CS Wallace と DL Dowe（1999）は、MML とアルゴリズム情報理論（またはコルモゴロフ複雑性）との形式的な関連性を示しました。^{[ 18 ]}

コルモゴロフランダム性

コルモゴロフのランダム性では、文字列（通常はビット列）がランダムであるとは、その文字列を生成できる最短のコンピュータプログラムの長さが、文字列自体の長さとほぼ同じである場合を指します。これを厳密にするために、文字列は $x$ 長さ $n$ コルモゴロフランダムと呼ばれるのは、 $K(x)\geq n+O(1)$ どこ $K$ は、上記で定義した接頭辞フリーのコルモゴロフ複雑度です。この意味でのランダム文字列は、文字列自体よりも短いプログラムに文字列を「圧縮」することが不可能であるという意味で、圧縮不可能です。各長さのコルモゴロフランダム文字列が少なくとも1つ存在します。^{[ 19 ]}

この定義は、有限アルファベットからの無限シーケンスのランダム性の概念を定義するように拡張できます。これらのアルゴリズム的にランダムなシーケンスは、 3 つの同等な方法で定義できます。1 つの方法は、測度論の有効な類似物を使用し、もう 1 つは有効なマルチンゲールを使用します。3 番目の方法は、無限シーケンスの初期セグメントの接頭辞なしコルモゴロフ複雑性が十分に速く増加する場合に、そのシーケンスがランダムであると定義します。つまり、長さnの初期セグメントの複雑性が常に少なくともn − cとなるような定数c が存在しなければなりません。^[²⁰^]

エントロピーとの関係

動的システムの場合、軌道のエントロピー率とアルゴリズムの複雑さは、Brudno の定理によって関連付けられ、等式が成り立つ。 $K(x;T)=h(T)$ ほぼすべてに当てはまる $x$ [ ²¹^]

マルコフ情報源の出力の場合、コルモゴロフ複雑度は情報源のエントロピーと関連していることが^{[ 22 ]}で示されている。より正確には、出力の長さで正規化されたマルコフ情報源の出力のコルモゴロフ複雑度は、（出力の長さが無限大に近づくにつれて）情報源のエントロピーにほぼ確実に収束する。

定理。（定理14.2.5 ^{[ 23 ]}）バイナリ文字列の条件付きコルモゴロフ複雑度 $x_{1:n}$ 満たす ${\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)$ どこ $H_{b}$ これは二値エントロピー関数です（エントロピー率と混同しないでください）。

停止問題

コルモゴロフ複雑度関数は、停止問題の判定と同等である。

停止オラクルがあれば、文字列のコルモゴロフ複雑度は、停止プログラムを辞書式順序で順番に実行し、そのうちの1つが文字列を出力するまで試行するだけで計算できます。

反対方向ははるかに複雑です。^{[ 24 ]}^{[ 25 ]}コルモゴロフ複雑性関数が与えられた場合、関数を構築できることが示されています。 $p$ 、したがって $p(n)\geq BB(n)$ すべての大きな $n$ 、どこ $BB$ Busy Beaverシフト関数 (別名: $S(n)$ ）より低い値で関数を修正することにより $n$ 上限値が得られます $BB$ これは停止問題を解決する。

このプログラムを検討してください ${\textstyle p_{K}}$ 入力として受け取る ${\textstyle n}$ 、そして使用する ${\textstyle K}$ 。

長さの文字列をすべてリストします ${\textstyle \leq 2n+1}$ 。
そのような文字列ごとに ${\textstyle x}$ 長さの (接頭辞なし) 全てのプログラムを列挙する $K(x)$ どちらか一方が出力するまで ${\textstyle x}$ 実行時間を記録する ${\textstyle n_{x}}$ 。
最大出力 ${\textstyle n_{x}}$ 。

背理法によって証明する ${\textstyle p_{K}(n)\geq BB(n)}$ すべての大きな ${\textstyle n}$ 。

させて ${\textstyle p_{n}}$ 長文の働き者 $n$ 入力を受け付けない、この（接頭辞のない）プログラムを考えてみましょう。

プログラムを実行する ${\textstyle p_{n}}$ そして、その実行時間を記録する。 $BB(n)$ 。
長さのすべてのプログラムを生成する ${\textstyle \leq 2n}$ それぞれを最大で実行します $BB(n)$ 手順。停止した手順の出力に注目してください。
それらのいずれによっても出力されていない文字列の中で、辞書順で最も低い文字列を出力してください。

プログラムが出力する文字列を ${\textstyle x}$ 。

このプログラムの長さは ${\textstyle \leq n+2\log _{2}n+O(1)}$ 、どこ $n$ ビジービーバーの長さから来ています ${\textstyle p_{n}}$ 、 $2\log _{2}n$ 番号に（接頭辞なしの）エリアスデルタコードを使用することから来ています $n$ 、そして $O(1)$ プログラムの残りの部分から来ています。したがって、 $K(x)\leq n+2\log _{2}n+O(1)\leq 2n$ すべての大きな ${\textstyle n}$ さらに、長さの可能なプログラムは限られているため ${\textstyle \leq 2n}$ 、我々は持っています ${\textstyle l(x)\leq 2n+1}$ 鳩の巣原理により。仮定により、 ${\textstyle p_{K}(n)<BB(n)}$ 長さが 1 の文字列はすべて ${\textstyle \leq 2n+1}$ 実行時動作を備えた最小限のプログラムがあります ${\textstyle <BB(n)}$ したがって、弦は ${\textstyle x}$ 実行時動作を備えた最小限のプログラムがあります ${\textstyle <BB(n)}$ さらに、そのプログラムの長さは ${\textstyle K(x)\leq 2n}$ これは、 ${\textstyle x}$ 建設された。

普遍的確率

万能チューリングマシンを修正する $U$ （接頭辞なし）コルモゴロフ複雑性を定義する際に使用されるものと同じ。文字列の（接頭辞なし）普遍確率を定義する。 $x$ である $P(x)=\sum _{U(p)=x}2^{-l(p)}$ 言い換えれば、これは、一様ランダムなバイナリストリームを入力として与えられたとき、ユニバーサルチューリングマシンがストリームの特定のプレフィックスを読み取った後に停止し、出力する確率である。 $x$ 。

注記。 $U(p)=x$ 入力ストリームが $p000\cdots$ しかし、万能チューリングマシンは最初のセグメントを読み込んだ後、どこかの時点で停止するだろう。 $p$ それ以上の入力を読み込まず、停止したときに書き込んだ $x$ 出力テープへ。

定理。（定理 14.11.1 ^{[ 23 ]}） $\log {\frac {1}{P(x)}}=K(x)+O(1)$

生物学における意義

生物学の文脈では、コルモゴロフ複雑度は、複数の種で観察される対称性とモジュール構造は、進化が最小限のコルモゴロフ複雑度を好む傾向から生じるという議論に用いられてきた。^{[ 26 ]}ゲノムを、タスクを解決したり一連の機能を実装したりしなければならないプログラムと考えると、進化のメカニズムによって見つけやすいという理由から、より短いプログラムが好まれるだろう。^{[ 27 ]}このアプローチの一例として、昆虫種全体に見られるコンパス回路の8重対称性が挙げられる。これは、機能的であると同時に、自己複製ユニットから生成されるために最小限のコルモゴロフ複雑度を必要とする回路に対応する。^{[ 28 ]}

条件付きバージョン

2つの文字列の条件付きコルモゴロフ複雑度 $K(x|y)$ 大まかに言えば、それは、手続きへの補助入力としてyが与えられたときのxのコルモゴロフ複雑度として定義されます。 ^[²⁹^]^[³⁰^]したがって、（無条件の）コルモゴロフ複雑度は、 $K(x)$ シーケンスの $x$ は、出力を行う最短のバイナリプログラムの長さです。 $x$ 汎用コンピュータ上で、生成に必要な最小限の情報量と考えることができる $x$ 条件付きコルモゴロフ複雑度 $K(x|y)$ は、計算を行う最短のバイナリプログラムの長さとして定義されます。 $x$ いつ $y$ 汎用コンピュータを使用して入力として与えられます。^{[ 31 ]}

長さ条件付き複雑性も存在する $K(x|L(x))$ これは、 xの長さが既知/入力である場合のxの複雑さです。 ^[³²^]^[³³^]

時間制約付き複雑性

時間制限付きコルモゴロフ複雑度は、解を求めるプログラムの空間が、あらかじめ定義されたステップ数内で実行できるプログラムのみに限定されるコルモゴロフ複雑度の修正版です。^{[ 34 ]}近似的な時間制限付きコルモゴロフ複雑度を決定する効率的なアルゴリズムが存在する可能性は、真の一方向関数が存在するかどうかの問題に関連していると仮説が立てられています。^{[ 35 ]}^{[ 36 ]}

注記

↑これは、コルモゴロフの 1963 年のロシア語オリジナル論文「О таблицах случайных чисел」の英語版再版です。
↑ただし、 K ( s ) = nとなるsは、すべてのnに対して存在するとは限りません。たとえば、 nが 7 の倍数でない場合、長さがちょうどnビットのASCIIプログラムはありません。
↑長さがnビットまでの異なるプログラムテキストは^{1 + 2 + 2 2} + 2³ + ... + 2ⁿ = 2ⁿ⁺¹ − 1通りあります。等比数列を参照してください。プログラムの長さが 7 ビットの倍数である場合、プログラムテキストの種類はさらに少なくなります。
↑前の定理により、そのような文字列が存在するため、forループは最終的に終了します。
↑言語インタープリタとサブルーチンコードを含むKolmogorovComplexity
↑長さがnビットの場合で使用される定数m はn + を満たすように調整する必要があります。KolmogorovComplexityGenerateComplexString1,400,000以上1218 + 7·log ₁₀ ( m ) < m、これは常に可能です。なぜなら、m はlog₁₀ ( m ) よりも速く増加するからです。
↑長さ $L$ の文字列は $NL$ $=$ $2L$ $個$ あるので $、長さL = 0, 1, ..., n - 1の文字列の数はN0 + N1 + ... + Nn -1$ = $20$ $+$ $21$ + $...$ $+$ $2n$ $-1$ $となり$ $、$ これ $は$ $有限$ $等$ $比$ $数列$ $で$ 、その和は $20$ $+$ $21$ $+$ $...$ $+$ $2n$ $-1$ = $20$ $\times$ $(1 - 2n$ $)$ $/ (1 - 2) = 2n$ $-$ $1と$ $なります$ $。$

参考文献

↑コルモゴロフ、アンドレイ N. (1998) [1963]. 「乱数表について」 .理論計算機科学. 207 (2): 387– 395. doi : 10.1016/S0304-3975(98)00075-9 . 2026年1月14日取得.
↑（ダウニーとヒルシュフェルト、2010年）、定理3.1.4
↑（ダウニーとハーシュフェルト、2010）、第3.5節
1 2 Hutter, Marcus (2007-03-06). "アルゴリズム情報理論" . Scholarpedia . 2 (3): 2519. Bibcode : 2007SchpJ...2.2519H . doi : 10.4249/scholarpedia.2519 . hdl : 1885/15015 . ISSN 1941-6016 .
↑ソロモノフ、レイ（1960年2月4日）。帰納的推論の一般理論に関する予備報告（PDF）。報告書V-131（報告書）。1960年11月に改訂版が発行されました。2022年10月9日にオリジナルからアーカイブ（PDF）。
↑ Solomonoff, Ray (1964 年 3 月). "帰納的推論の形式理論パート I" (PDF) . Information and Control . 7 (1): 1– 22. doi : 10.1016/S0019-9958(64)90223-2 . 2022 年 10 月 9 日にオリジナルからアーカイブ(PDF) 。
↑ Solomonoff, Ray (1964年6月). "帰納的推論の形式理論パートII" (PDF) . Information and Control . 7 (2): 224– 254. doi : 10.1016/S0019-9958(64)90131-7 . 2022年10月9日にオリジナルからアーカイブ(PDF) 。
↑コルモゴロフ、AN (1965)。「情報の定量的定義への3つのアプローチ」。情報伝達の問題。1 ( 1): 1–7 。2011年9月28日にオリジナルからアーカイブ。
↑ Chaitin, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers". Journal of the ACM . 16 (3): 407–422 . CiteSeerX 10.1.1.15.3821 . doi : 10.1145/321526.321530 . S2CID 12584692 .
↑コルモゴロフ、A . ( 1968). 「情報理論と確率理論の論理的基礎」。IEEE Transactions on Information Theory。14 ( 5): 662–664。doi : 10.1109 / TIT.1968.1054210。S2CID 11402549。
↑ Li, Ming; Vitányi, Paul (2008). "予備知識".コルモゴロフ複雑性とその応用入門. Texts in Computer Science. pp. 1 –99. doi : 10.1007/978-0-387-49820-1_1 . ISBN 978-0-387-33998-6。
↑ Burgin, M. (1982). "計算理論における一般化コルモゴロフ複雑性と双対性" .ロシア科学アカデミー紀要. 25 (3): 19– 23.
↑フッター、マーカス（2005）。ユニバーサル人工知能：アルゴリズム確率に基づく逐次決定。理論計算機科学テキスト。ベルリン、ニューヨーク：シュプリンガー。ISBN 978-3-540-26877-2。
↑証明なしに以下のように述べられている: PB Miltersen (2005). "データ圧縮 - コルモゴロフ複雑性に関する講義ノート" (PDF) . p. 7. 2009年9月9日にオリジナル(PDF)からアーカイブ済み。
↑ Zvonkin, A.; L. Levin (1970). "有限オブジェクトの複雑性とアルゴリズム理論による情報とランダム性の概念の発展" (PDF) . Russian Mathematical Surveys . 25 (6): 83– 124. Bibcode : 1970RuMaS..25...83Z . doi : 10.1070/RM1970v025n06ABEH001269 . S2CID 250850390 .
↑ Gregory J. Chaitin (1974年7月)。「形式システムの情報理論的限界」(PDF)。Journal of the ACM。21 ( 3 ): 403–434。doi : 10.1145 /321832.321839。S2CID 2142553。ここ：Thm.4.1b
↑カルード、クリスティアン S. (2002年9月12日).情報とランダム性：アルゴリズム的視点. スプリンガー. ISBN 978-3-540-43466-5。
↑ Wallace, CS; Dowe, DL (1999). "最小メッセージ長とコルモゴロフ複雑度". Computer Journal . 42 (4): 270–283 . CiteSeerX 10.1.1.17.321 . doi : 10.1093/comjnl/42.4.270 .
↑ Venkataramanan, Venkat; Gács, Peter (2020). "Kolmogorov Complexity" (PDF) . 15-252 講義ノート (2020 年春) . カーネギーメロン大学. 2026 年1 月 14 日取得.長さnのバイナリ文字列は 2 ⁿ個ありますが、長さが厳密にnより小さいバイナリ文字列は2 ⁿ -1 個しかありません。
↑ Martin-Löf, Per (1966). "ランダムシーケンスの定義" . Information and Control . 9 (6): 602– 619. doi : 10.1016/s0019-9958(66)80018-9 .
↑ Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal (2010). "Effective symbolic dynamics, random points, statistical behavior, complexity and entropy" (PDF) . Information and Computation . 208 : 23– 41. arXiv : 0801.0209 . doi : 10.1016/j.ic.2009.05.001 . S2CID 5555443 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。
↑ Alexei Kaltchenko (2004). "バイオインフォマティクスと言語学への応用を伴う情報距離推定アルゴリズム". arXiv : cs.CC/0404039 .
1 2カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ワイリー・インターサイエンス. ISBN 0-471-24195-4。
↑ Chaitin, G.; Arslanov, A.; Calude, Cristian S. (1995-09-01). "プログラムサイズの複雑性により停止問題が計算される". Bull. EATCS . S2CID 39718973 .
↑ Li, Ming; Vitányi, Paul (2008). An Introduction to Kolmogorov Complexity and Its Applications . Texts in Computer Science. Exercise 2.7.7. Bibcode : 2008ikca.book.....L . doi : 10.1007/978-0-387-49820-1 . ISBN 978-0-387-33998-6ISSN 1868-0941
↑ Johnston, Iain G.; Dingle, Kamaludin; Greenbury, Sam F.; Camargo, Chico Q.; Doye, Jonathan PK; Ahnert, Sebastian E.; Louis, Ard A. (2022-03-15). "Symmetry and simples spontaneously emerge from the algorithmic nature of evolution" . Proceedings of the National Academy of Sciences . 119 (11) e2113883119. Bibcode : 2022PNAS..11913883J . doi : 10.1073/pnas.2113883119 . PMC 8931234. PMID 35275794 .
↑ Alon, Uri (2007年3月). "生物学における単純性" . Nature . 446 (7135): 497. Bibcode : 2007Natur.446..497A . doi : 10.1038/446497a . ISSN 1476-4687 . PMID 17392770 .
↑ Vilimelis Aceituno, Pau; Dall'Osto, Dominic; Pisokas, Ioannis (2024-05-30). Colgin, Laura L; Vafidis, Pantelis (eds.). "Theoretical principles explain the structure of the insect head direction circuit" . eLife . 13 e91533 . doi : 10.7554/eLife.91533 . ISSN 2050-084X . PMC 11139481. PMID 38814703 .
↑ Jorma Rissanen (2007).統計モデリングにおける情報と複雑性. 情報科学と統計. Springer S. p. 53. doi : 10.1007 /978-0-387-68812-1 . ISBN 978-0-387-68812-1。
↑ミン・リー;ポール MB ヴィタニー (2009)。コルモゴロフ複雑性とその応用の紹介。スプリンガー。105 ～106ページ。土井：10.1007/978-0-387-49820-1。ISBN 978-0-387-49820-1。
↑ケレメン、アルパード。アブラハム、アジト。リャン、ユラン編。（2008年）。医療情報学における計算知能。ニューヨーク;ロンドン：スプリンガー。 p. 160.ISBN 978-3-540-75766-5OCLC 181069666
↑ミン・リー;ポール MB ヴィタニー (2009)。コルモゴロフ複雑性とその応用の紹介。スプリンガー。 p. 119 . ISBN 978-0-387-49820-1。
↑ Vitányi, Paul MB (2013). "条件付きコルモゴロフ複雑性と普遍確率" . Theoretical Computer Science . 501 : 93–100 . arXiv : 1206.0983 . doi : 10.1016/j.tcs.2013.07.009 . S2CID 12085503 .
↑平原秀一；カバネット、バレンタイン。ルー、ジェンジャン。オリベイラ、イーゴリ C. (2024)。「時間制限のあるコルモゴロフ複雑性に対する正確な検索から決定までの短縮」。第 39 回計算複雑性会議 (CCC 2024)。ライプニッツ国際情報学会議 (LIPIcs)。300。 Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 29:1–29:56。土井：10.4230/LIPIcs.CCC.2024.29。ISBN 978-3-95977-331-7。
↑ Klarreich, Erica (2022-04-06). "研究者らがすべての暗号化の根底にある「マスター問題」を特定" . Quanta Magazine . 2024-11-16に取得.
↑ Liu, Yanyi; Pass, Rafael (2020-09-24), On One-way Functions and Kolmogorov Complexity , arXiv : 2009.11514

さらに読む

Blum, M. (1967). 「機械のサイズについて」 . Information and Control . 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
ブルドノ、A. (1983). 「エントロピーと力学系の軌跡の複雑性」.モスクワ数学会紀要. 2 : 127– 151.
Cover, Thomas M.; Thomas, Joy A. (2006).情報理論の基礎（第2 版）. Wiley-Interscience. ISBN 0-471-24195-4。
ラホス、ロンヤイ。ガボール、イワニョス。レカ、サボ (1999)。アルゴリズムムソーク。タイポテックス。ISBN 963-279-014-6。
リー、ミン。ヴィタニー、ポール (1997)。コルモゴロフ複雑性とその応用の紹介。スプリンガー。ISBN 978-0-387-33998-6。
Yu, Manin (1977).数理論理学入門. Springer-Verlag. ISBN 978-0-7204-2844-5。
Sipser, Michael (1997).計算理論入門. PWS. ISBN 0-534-95097-3。
Downey, Rodney G.; Hirschfeldt, Denis R. (2010). "アルゴリズムのランダム性と複雑性" . Theory and Applications of Computability . doi : 10.1007/978-0-387-68441-3 . ISBN 978-0-387-95567-4ISSN 2190-619X

外部リンク

アンドレイ・ニコラエヴィチ・コルモゴロフの遺産
チャイティンのオンライン出版物
ソロモノフのIDSIAページ
J.シュミットフーバーによるアルゴリズム情報の一般化
「リ・ヴィターニ1997のレビュー」。
トランプ、ジョン。「ジョンのラムダ計算と組み合わせ論理の遊び場」。トロンプのラムダ計算コンピュータモデルは、K()の具体的な定義を提供する。
コルモゴロフ複雑性に基づく汎用AI ISBN 3-540-22139-5M. Hutter著： ISBN 3-540-22139-5
デビッド・ダウの最小メッセージ長（MML）とオッカムの剃刀に関するページ。
Grunwald, P.; Pitt, MA (2005). Myung, IJ (編). Advances in Minimum Description Length: Theory and Applications . MIT Press. ISBN 0-262-07262-9。

[2] これは、コルモゴロフの 1963 年のロシア語オリジナル論文「О таблицах случайных чисел」の英語版再版です。

[15] ただし、 K ( s ) = nとなるsは、すべてのnに対して存在するとは限りません。たとえば、 nが 7 の倍数でない場合、長さがちょうどnビットのASCIIプログラムはありません。

[16] 長さがnビットまでの異なるプログラムテキストは^{1 + 2 + 2 2} + 2³ + ... + 2ⁿ = 2ⁿ⁺¹ − 1通りあります。等比数列を参照してください。プログラムの長さが 7 ビットの倍数である場合、プログラムテキストの種類はさらに少なくなります。

[17] 前の定理により、そのような文字列が存在するため、forループは最終的に終了します。

[18] 言語インタープリタとサブルーチンコードを含むKolmogorovComplexity

[19] 長さがnビットの場合で使用される定数m はn + を満たすように調整する必要があります。KolmogorovComplexityGenerateComplexString1,400,000以上1218 + 7·log ₁₀ ( m ) < m、これは常に可能です。なぜなら、m はlog₁₀ ( m ) よりも速く増加するからです。

[22] 長さ $L$ の文字列は $NL$ $=$ $2L$ $個$ あるので $、長さL = 0, 1, ..., n - 1の文字列の数はN0 + N1 + ... + Nn -1$ = $20$ $+$ $21$ + $...$ $+$ $2n$ $-1$ $となり$ $、$ これ $は$ $有限$ $等$ $比$ $数列$ $で$ 、その和は $20$ $+$ $21$ $+$ $...$ $+$ $2n$ $-1$ = $20$ $\times$ $(1 - 2n$ $)$ $/ (1 - 2) = 2n$ $-$ $1と$ $なります$ $。$

[Kolmogorov1963-1] コルモゴロフ、アンドレイ N. (1998) [1963]. 「乱数表について」 .理論計算機科学. 207 (2): 387– 395. doi : 10.1016/S0304-3975(98)00075-9 . 2026年1月14日取得.

[3] （ダウニーとヒルシュフェルト、2010年）、定理3.1.4

[4] （ダウニーとハーシュフェルト、2010）、第3.5節

[hutter-5] 1 2 Hutter, Marcus (2007-03-06). "アルゴリズム情報理論" . Scholarpedia . 2 (3): 2519. Bibcode : 2007SchpJ...2.2519H . doi : 10.4249/scholarpedia.2519 . hdl : 1885/15015 . ISSN 1941-6016 .

[6] ソロモノフ、レイ（1960年2月4日）。帰納的推論の一般理論に関する予備報告（PDF）。報告書V-131（報告書）。1960年11月に改訂版が発行されました。2022年10月9日にオリジナルからアーカイブ（PDF）。

[7] Solomonoff, Ray (1964 年 3 月). "帰納的推論の形式理論パート I" (PDF) . Information and Control . 7 (1): 1– 22. doi : 10.1016/S0019-9958(64)90223-2 . 2022 年 10 月 9 日にオリジナルからアーカイブ(PDF) 。

[8] Solomonoff, Ray (1964年6月). "帰納的推論の形式理論パートII" (PDF) . Information and Control . 7 (2): 224– 254. doi : 10.1016/S0019-9958(64)90131-7 . 2022年10月9日にオリジナルからアーカイブ(PDF) 。

[9] コルモゴロフ、AN (1965)。「情報の定量的定義への3つのアプローチ」。情報伝達の問題。1 ( 1): 1–7 。2011年9月28日にオリジナルからアーカイブ。

[10] Chaitin, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers". Journal of the ACM . 16 (3): 407–422 . CiteSeerX 10.1.1.15.3821 . doi : 10.1145/321526.321530 . S2CID 12584692 .

[11] コルモゴロフ、A . ( 1968). 「情報理論と確率理論の論理的基礎」。IEEE Transactions on Information Theory。14 ( 5): 662–664。doi : 10.1109 / TIT.1968.1054210。S2CID 11402549。

[12] Li, Ming; Vitányi, Paul (2008). "予備知識".コルモゴロフ複雑性とその応用入門. Texts in Computer Science. pp. 1 –99. doi : 10.1007/978-0-387-49820-1_1 . ISBN 978-0-387-33998-6。

[Burgin1982-13] Burgin, M. (1982). "計算理論における一般化コルモゴロフ複雑性と双対性" .ロシア科学アカデミー紀要. 25 (3): 19– 23.

[14] フッター、マーカス（2005）。ユニバーサル人工知能：アルゴリズム確率に基づく逐次決定。理論計算機科学テキスト。ベルリン、ニューヨーク：シュプリンガー。ISBN 978-3-540-26877-2。

[20] 証明なしに以下のように述べられている: PB Miltersen (2005). "データ圧縮 - コルモゴロフ複雑性に関する講義ノート" (PDF) . p. 7. 2009年9月9日にオリジナル(PDF)からアーカイブ済み。

[21] Zvonkin, A.; L. Levin (1970). "有限オブジェクトの複雑性とアルゴリズム理論による情報とランダム性の概念の発展" (PDF) . Russian Mathematical Surveys . 25 (6): 83– 124. Bibcode : 1970RuMaS..25...83Z . doi : 10.1070/RM1970v025n06ABEH001269 . S2CID 250850390 .

[23] Gregory J. Chaitin (1974年7月)。「形式システムの情報理論的限界」(PDF)。Journal of the ACM。21 ( 3 ): 403–434。doi : 10.1145 /321832.321839。S2CID 2142553。ここ：Thm.4.1b

[24] カルード、クリスティアン S. (2002年9月12日).情報とランダム性：アルゴリズム的視点. スプリンガー. ISBN 978-3-540-43466-5。

[25] Wallace, CS; Dowe, DL (1999). "最小メッセージ長とコルモゴロフ複雑度". Computer Journal . 42 (4): 270–283 . CiteSeerX 10.1.1.17.321 . doi : 10.1093/comjnl/42.4.270 .

[26] Venkataramanan, Venkat; Gács, Peter (2020). "Kolmogorov Complexity" (PDF) . 15-252 講義ノート (2020 年春) . カーネギーメロン大学. 2026 年1 月 14 日取得.長さnのバイナリ文字列は 2 ⁿ個ありますが、長さが厳密にnより小さいバイナリ文字列は2 ⁿ -1 個しかありません。

[27] Martin-Löf, Per (1966). "ランダムシーケンスの定義" . Information and Control . 9 (6): 602– 619. doi : 10.1016/s0019-9958(66)80018-9 .

[28] Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal (2010). "Effective symbolic dynamics, random points, statistical behavior, complexity and entropy" (PDF) . Information and Computation . 208 : 23– 41. arXiv : 0801.0209 . doi : 10.1016/j.ic.2009.05.001 . S2CID 5555443 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。

[29] Alexei Kaltchenko (2004). "バイオインフォマティクスと言語学への応用を伴う情報距離推定アルゴリズム". arXiv : cs.CC/0404039 .

[:1-30] 1 2カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ワイリー・インターサイエンス. ISBN 0-471-24195-4。

[31] Chaitin, G.; Arslanov, A.; Calude, Cristian S. (1995-09-01). "プログラムサイズの複雑性により停止問題が計算される". Bull. EATCS . S2CID 39718973 .

[32] Li, Ming; Vitányi, Paul (2008). An Introduction to Kolmogorov Complexity and Its Applications . Texts in Computer Science. Exercise 2.7.7. Bibcode : 2008ikca.book.....L . doi : 10.1007/978-0-387-49820-1 . ISBN 978-0-387-33998-6ISSN 1868-0941

[33] Johnston, Iain G.; Dingle, Kamaludin; Greenbury, Sam F.; Camargo, Chico Q.; Doye, Jonathan PK; Ahnert, Sebastian E.; Louis, Ard A. (2022-03-15). "Symmetry and simples spontaneously emerge from the algorithmic nature of evolution" . Proceedings of the National Academy of Sciences . 119 (11) e2113883119. Bibcode : 2022PNAS..11913883J . doi : 10.1073/pnas.2113883119 . PMC 8931234. PMID 35275794 .

[34] Alon, Uri (2007年3月). "生物学における単純性" . Nature . 446 (7135): 497. Bibcode : 2007Natur.446..497A . doi : 10.1038/446497a . ISSN 1476-4687 . PMID 17392770 .

[35] Vilimelis Aceituno, Pau; Dall'Osto, Dominic; Pisokas, Ioannis (2024-05-30). Colgin, Laura L; Vafidis, Pantelis (eds.). "Theoretical principles explain the structure of the insect head direction circuit" . eLife . 13 e91533 . doi : 10.7554/eLife.91533 . ISSN 2050-084X . PMC 11139481. PMID 38814703 .

[Rissanen2007-36] Jorma Rissanen (2007).統計モデリングにおける情報と複雑性. 情報科学と統計. Springer S. p. 53. doi : 10.1007 /978-0-387-68812-1 . ISBN 978-0-387-68812-1。

[37] ミン・リー;ポール MB ヴィタニー (2009)。コルモゴロフ複雑性とその応用の紹介。スプリンガー。105 ～106ページ。土井：10.1007/978-0-387-49820-1。ISBN 978-0-387-49820-1。

[38] ケレメン、アルパード。アブラハム、アジト。リャン、ユラン編。（2008年）。医療情報学における計算知能。ニューヨーク;ロンドン：スプリンガー。 p. 160.ISBN 978-3-540-75766-5OCLC 181069666

[39] ミン・リー;ポール MB ヴィタニー (2009)。コルモゴロフ複雑性とその応用の紹介。スプリンガー。 p. 119 . ISBN 978-0-387-49820-1。

[40] Vitányi, Paul MB (2013). "条件付きコルモゴロフ複雑性と普遍確率" . Theoretical Computer Science . 501 : 93–100 . arXiv : 1206.0983 . doi : 10.1016/j.tcs.2013.07.009 . S2CID 12085503 .

[41] 平原秀一；カバネット、バレンタイン。ルー、ジェンジャン。オリベイラ、イーゴリ C. (2024)。「時間制限のあるコルモゴロフ複雑性に対する正確な検索から決定までの短縮」。第 39 回計算複雑性会議 (CCC 2024)。ライプニッツ国際情報学会議 (LIPIcs)。300。 Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 29:1–29:56。土井：10.4230/LIPIcs.CCC.2024.29。ISBN 978-3-95977-331-7。

[42] Klarreich, Erica (2022-04-06). "研究者らがすべての暗号化の根底にある「マスター問題」を特定" . Quanta Magazine . 2024-11-16に取得.

[43] Liu, Yanyi; Pass, Rafael (2020-09-24), On One-way Functions and Kolmogorov Complexity , arXiv : 2009.11514

[ 1 ]

[注1 ]

2

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[

[注 3 ]

[注4

注5

[注6 ]

[

[ 15 ]

[

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[

21

[ 22 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[

[

[ 31 ]

[

[

[ 34 ]

[ 35 ]

[ 36 ]