コルモゴロフ複雑性

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

コルモゴロフ複雑性の概念は、カントールの対角線論証、ゲーデルの不完全性定理、チューリングの停止問題に類似した不可能性結果を述べ、証明するために使用できる。特に、各テキストのコルモゴロフ複雑性の下限を計算するプログラムPは、 P自身の長さよりも本質的に大きい値を返すことはできない(セクション § チャイティンの不完全性定理を参照)。したがって、単一のプログラムでは、無限の数のテキストの正確なコルモゴロフ複雑性を計算できない。コルモゴロフ複雑性は、ファイル (つまり、コンピュータに配置できるもの) の最終的な圧縮バージョンの長さである。正式には、ファイルを再構築できる最短のプログラムの長さである。コルモゴロフ複雑性は計算不可能であるが、さまざまなアプローチが提案され、検討されてきた。^[3]

32 個の小文字と数字から なる次の 2 つの文字列を考えてみましょう。

abababababababababababababababab、 そして

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

最初の文字列には、 17文字からなる「ab を 16 回書く」という短い英語の説明があります。2 番目の文字列には、文字列自体を書き留める以外に、明白な簡単な説明 (同じ文字セットを使用) はありません。つまり、「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 番目の文字列は、疑似コードによって出力されます。

関数GenerateString2() は
    "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"
を返します。

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

関数GenerateString1() は
    "ab" × 16
を返します

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

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

最短の説明の長さは、記述言語の選択によって異なりますが、言語を変更した場合の影響は制限されます (不変性定理と呼ばれる結果)。

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

デフォルトでは、すべての方程式は加法定数までしか成り立ちません。たとえば、 は実際には、つまり を意味します。 ${\displaystyle f(x)=g(x)}$${\displaystyle f(x)=g(x)+O(1)}$${\displaystyle \exists c,\forall x,|f(x)-g(x)|\leq c}$

を有限バイナリ文字列をバイナリ文字列にマッピングする計算可能な関数とします。任意の計算可能なに対して、関数を「プログラム」 でエンコードして とすることができる場合にのみ、これはユニバーサル関数です。 は、プログラムを記述する最初のセグメントと、それに続くプログラムが処理するデータを受け取るプログラム インタープリタと考えることができます。 ${\displaystyle U:2^{*}\to 2^{*}}$${\displaystyle f:2^{*}\to 2^{*}}$${\displaystyle s_{f}}$${\displaystyle \forall x\in 2^{*},U(s_{f}x)=f(x)}$${\displaystyle U}$

単純な計算量に関する問題の1つは、直感的に言えば、連結された文字列を見ただけでは出力文字列をどこで分割するかを判断する一般的な方法がないことです。またはの長さを指定して分割することはできますが、それには余分な記号が必要になります。実際、任意の に対して となる が存在します。^[4]${\displaystyle C(xy)\not <C(x)+C(y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle O(\min(\ln x,\ln y))}$${\displaystyle c>0}$${\displaystyle x,y}$${\displaystyle C(xy)\geq C(x)+C(y)+c}$

通常、単純な複雑度を持つ不等式の片側にはのような項がありますが、接頭辞のない複雑度を持つ同じ不等式には のみがあります。 ${\displaystyle O(\min(\ln x,\ln y))}$${\displaystyle O(1)}$

単純な計算量に関する主な問題は、プログラムに何か余分なものが紛れ込んでいるということです。プログラムは、コードで何かを表すだけでなく、自分自身の長さも表します。特に、プログラムは、までの2進数を、単に自分自身の長さで表すことができます。別の言い方をすると、単語の終わりを示すために終了記号を使用しているようなもので、2つの記号ではなく3つの記号を使用しています。この欠陥を修正するために、プレフィックスフリーのコルモゴロフ計算量を導入します。^[5]${\displaystyle x}$${\displaystyle \log_{2}|x|}$

プレフィックスフリー コードとは、セット内の2 つの異なる単語が与えられた場合、どちらも他方のプレフィックスではないサブセットです。プレフィックスフリー コードの利点は、コードから単語を一方向に読み取るマシンを構築できることです。マシンは単語の最後の記号を読み取った時点で単語が終了したことを認識し、バックトラックや終了記号を必要としません。 ${\displaystyle 2^{*}}$${\displaystyle x,y}$

プレフィックスフリーのチューリング マシンを、プレフィックスフリーのコードを備えたチューリング マシンとして定義します。このチューリング マシンは、コードから任意の文字列を一方向に読み取り、最後のシンボルを読み取ったらすぐに読み取りを停止します。その後、作業テープ上で計算を行い、書き込みテープに書き込むことはできますが、読み取りヘッドをそれ以上移動することはできません。

これにより、 Kを記述する形式的な方法が次のように得られる。^[6]

• 3 つのテープ (一方向に無限の読み取りテープ、2 方向に無限の作業テープ、一方向に無限の書き込みテープ) を使用して、プレフィックスのない汎用チューリング マシンを修正します。
• マシンは、読み取りテープから一方向のみで読み取り (バックトラックなし)、書き込みテープに一方向のみで書き込みます。作業テープは両方向で読み取りと書き込みが可能です。
• 作業テープと書き込みテープはすべてゼロで始まります。読み取りテープは入力プレフィックス コードで始まり、その後にすべてゼロが続きます。
• を、汎用チューリングマシンで使用される上のプレフィックスフリーコードとします。${\displaystyle S}$${\displaystyle 2^{*}}$

一部の汎用チューリング マシンはプレフィックス コードでプログラムできない場合があることに注意してください。プレフィックスのない汎用チューリング マシンのみを選択する必要があります。

文字列のプレフィックスフリー複雑度は、マシンが次のように出力できる最短のプレフィックスコードです。${\displaystyle x}$${\displaystyle x}$$${\displaystyle K(x):=\min\{|c|:c\in S,U(c)=x\}}$$

いくつかの記述言語は、次の意味で最適です。記述言語でオブジェクトを記述すると、その記述は、一定のオーバーヘッドで最適な記述言語で使用できます。この定数は、関係する言語のみに依存し、オブジェクトの記述や記述されるオブジェクトには依存しません。

最適な記述言語の例を次に示します。記述は 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が存在し、

∀ s . − c ≤ K ₁ ( s ) − K ₂ ( s ) ≤ c .

証明：対称性により、すべての弦sに対して定数cが存在することを証明すれば十分である。

K ₁ ( s ) ≤ K ₂ ( s ) + cです。

ここで、言語L _{1で記述され、言語}L ₂のインタープリタとして機能するプログラムがあるとします。

関数InterpretLanguage(文字列 p )

ここで、p はL ₂内のプログラムです。インタープリタは次の特性を備えています。

InterpretLanguage入力pを実行すると、pの実行結果が返されます。

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

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

これは望ましい上限を証明します。

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

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

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

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

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

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

ブルーム公理（Blum 1967）に基づくコルモゴロフ複雑性への公理的アプローチは、アンドレイ・コルモゴロフの出版のために提出された論文の中でマーク・バーギンによって導入された。^[14]

を と書きます。ここで は文字列 x と y のタプルをコード化する固定された方法を意味します。 ${\displaystyle K(x,y)}$${\displaystyle K((x,y))}$${\displaystyle (x,y)}$

の加法因子は省略する。このセクションは に基づく。^[6]${\displaystyle O(1)}$

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

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

定理:となるような が存在する。より簡潔に言えば、である。同様に、および である。^{[説明が必要]}${\displaystyle c}$${\displaystyle \forall x,C(x)\leq |x|+c}$${\displaystyle C(x)\leq |x|}$${\displaystyle K(x)\leq |x|+2\log _{2}|x|}$${\displaystyle K(x||x|)\leq |x|}$

証明。単純な複雑さの場合は、入力を出力にコピーするだけのプログラムを書くだけです。プレフィックスなしの複雑さの場合は、文字列自体を書き出す前に、まず文字列の長さを記述する必要があります。

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

• ${\displaystyle 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)}$
• ${\displaystyle K(xy)\leq K(x,y)}$

andまたはまたはを比較する方法がないことに注意してください。文字列全体を記述するのは簡単だが、その部分文字列を記述するのは非常に難しい 文字列があります。${\displaystyle K(xy)}$${\displaystyle K(x|y)}$${\displaystyle K(x)}$${\displaystyle K(y|x)}$${\displaystyle K(y)}$${\displaystyle xy}$

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

証明。一方は単純である。他方については、計数的議論（38ページ^[15]）を使用する必要がある。 ${\displaystyle K(x,y)\geq K(x|y,K(y))+K(y)}$

定理。(情報非増加)任意の計算可能関数に対して、 が成り立ちます。 ${\displaystyle f}$${\displaystyle K(f(x))\leq K(x)+K(f)}$

証明。チューリング マシンをプログラムして、関数を記述するプログラムと文字列を記述するプログラムの 2 つの連続するプログラムを読み込みます。次に、両方のプログラムを作業テープ上で実行して を生成し、書き出します。 ${\displaystyle f(x)}$

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

関数KolmogorovComplexity(文字列s)、
     i = 1から無限大:
        長さがちょうど i
            の各文字列 pについて、 isValidProgram(p)かつevaluate(p) == s
                の場合、 i を
返します。

このプログラムは、最も短いものから始めて、すべての可能なプログラムを反復処理します (すべての可能な文字列を反復処理し、有効なプログラムのみを考慮します)。各プログラムが実行され、そのプログラムによって生成された結果が入力sと比較されます。結果が一致すると、プログラムの長さが返されます。

しかし、これは機能しません。なぜなら、p でテストされたプログラムの一部は、たとえば無限ループが含まれている場合など、終了しないからです。停止問題の非計算可能性のため、実行前に何らかの方法でテストすることによって、これらすべてのプログラムを回避する方法はありません。

さらに、どんなに高度なプログラムであっても、関数Kを計算することはできません。これは次のように証明されます。

定理: 任意の大きさのコルモゴロフ複雑度を持つ弦が存在する。形式的には、各自然数nに対して、 K ( s ) ≥ nとなる弦sが存在する。^{[注 1]}

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

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

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

関数KolmogorovComplexity(文字列s)

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

関数GenerateComplexString()
    はi = 1から無限大まで:
        長さ i
            の各文字列 sに対して、 KolmogorovComplexity(s) ≥ 8000000000
                であればs
を返します。

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

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

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

コルモゴロフ複雑性の連鎖律^{[17]は、すべての}XとYに対して定数cが存在することを述べています。

K ( X , Y ) = K ( X ) + K ( Y | X ) + c*max(1,log( K ( X , Y )))。

これは、 XとY を再現する最短のプログラムは、X を再現するプログラムと、 Xが与えられた場合にY を再現するプログラムよりも大きい対数項にすぎないことを示しています。このステートメントを使用して、コルモゴロフ複雑性に対する相互情報量の類似物を定義できます。

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

文字列sは、その長さが | s | − cビットを超えない記述を持つ場合、数値cで圧縮可能です。これは、 K ( s ) ≤ | s | − cと言っているのと同じです。それ以外の場合、s はcで圧縮できません。1 で圧縮できない文字列は、単純に圧縮できないと言われます 。圧縮された文字列はすべて 1 つの非圧縮文字列にマップされるため適用される鳩の巣原理によ​​り、長さnのビット文字列は 2 ^{n 個}ありますが、それより短い文字列、つまりn未満の長さの文字列(つまり、長さ 0、1、...、 n − 1) は2 ⁿ − 1 個しかないため、圧縮できない文字列が存在するはずです。^{[注 6]}

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

定理: 長さ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内の式F _Aを関連付けることができるほど強力である必要があります。この関連付けには、次のプロパティが必要です。

F _{A が}Sの公理から証明可能であれば、対応する主張A は真でなければなりません。この「形式化」はゲーデル数に基づいて達成できます。

定理：定数L （ Sと記述言語の選択にのみ依存）が存在し、次の文が成り立つ 文字列sは存在しない。

K ( s ) ≥ L ( S       で形式化されているように)

Sの範囲内で証明できる。^{[18] [19]}

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

証拠：

Sにおけるすべての形式的証明の効果的な列挙は、ある手順によって 見つけることができる。

関数NthProof( int  n )

これはn を入力として受け取り、何らかの証明を出力する。この関数はすべての証明を列挙する。これらのうちいくつかは、ここでは気にしない式の証明である。なぜなら、Sの言語におけるあらゆる可能な証明は、何らかのnに対して生成されるからである。これらのうちいくつかは、 K ( s ) ≥  nの形式の計算量式である。ここで、sとn はSの言語における定数である。次の手続きがある。

関数NthProofProvesComplexityFormula( int  n )

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

関数StringNthProof( int  n )

関数ComplexityLowerBoundNthProof( int  n )

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

関数GenerateProvablyComplexString( int  n )、
     i = 1 から無限大:
         NthProofProvesComplexityFormula (i)かつComplexityLowerBoundNthProof(i) ≥ nの場合、 StringNthProof( i )
を返します。
            

nが与えられると、この手順は、何らかのL  ≥  nに対して式K ( s ) ≥  Lの文字列と形式体系Sの証明が見つかるまで、あらゆる証明を試みます。そのような証明が存在しない場合は、永久にループします。

最後に、これらすべてのプロシージャ定義とメイン呼び出しで構成されるプログラムを検討します。

証明可能な複雑な文字列を生成する( n 0 )

ここで、定数n _{0 は}後で決定されます。プログラム全体の長さは、U +log ₂ ( n ₀ ) と表すことができます。ここで、Uは定数で、 log ₂ ( n ₀ ) は、2進数でエンコードされているという合理的な仮定の下で、整数値n _{0の長さを表します。} n _{0 は}プログラムの長さよりも大きくなるように選択します。つまり、n ₀ > U +log ₂ ( n _{0 ) となります。これは、} n _{0 が}十分に大きい場合に当てはまります。なぜなら、左側はn ₀に対して線形に増加するのに対し、右側はn ₀に対して固定定数Uまで対数的に増加するからです。

すると、間接的な議論からわかるように、L ≥ n ₀の形式「K ( s )≥ L」の証明はSでは得られません。 がn ₀以上の値を返すことができれば、内部のループは最終的に終了し、その手順は次のような 文字列sを返します。ComplexityLowerBoundNthProof(i)GenerateProvablyComplexString

これは矛盾だ、QED

その結果、上記のプログラムは、選択された値n ₀を使用して永久にループする必要があります。

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

統計的・帰納的推論と機械学習の最小メッセージ長原理は、1968 年にCS Wallaceと DM Boulton によって開発されました。MML はベイジアン(事前の信念を組み込む) かつ情報理論的です。統計的不変性 (極座標から直交座標への再パラメータ化による推論の変換など)、統計的一貫性 (非常に難しい問題でも、MML はあらゆる基礎モデルに収束する)、効率性 (MML モデルは可能な限り迅速にあらゆる真の基礎モデルに収束する) という望ましい特性を備えています。CS Wallace と DL Dowe (1999) は、MML とアルゴリズム情報理論 (またはコルモゴロフ複雑性) との正式な関係を示しました。^[20]

コルモゴロフのランダム性は、文字列（通常はビット）がランダムであるとは、その文字列を生成できるすべてのコンピュータ プログラムが文字列自体と同じかそれ以上の長さである場合に限ると定義します。これを正確にするには、汎用コンピュータ（または汎用チューリング マシン）を指定する必要があります。この場合、「プログラム」はこの汎用マシンのプログラムを意味します。この意味でのランダム文字列は、文字列を文字列自体よりも短いプログラムに「圧縮」することが不可能であるという点で「圧縮不可能」です。すべての汎用コンピュータには、それぞれの長さのアルゴリズム的にランダムな文字列が少なくとも 1 つあります。^[21] ただし、特定の文字列がランダムであるかどうかは、選択された特定の汎用コンピュータによって異なります。これは、汎用コンピュータに特定の文字列がハードコードされている場合があり、この汎用コンピュータで実行されるプログラムは、短いビット シーケンス（つまり、文字列自体よりもはるかに短い）を使用して、このハードコードされた文字列を参照するだけで済むためです。

この定義は、有限のアルファベットからの無限シーケンスのランダム性の概念を定義するために拡張できます。これらのアルゴリズム的にランダムなシーケンスは、 3つの同等の方法で定義できます。1つの方法は、測度論の効果的な類似物を使用し、もう1つは効果的なマルチンゲールを使用します。3番目の方法は、初期セグメントのプレフィックスフリーコルモゴロフ複雑性が十分に速く増加する場合、無限シーケンスがランダムであると定義します。つまり、長さnの初期セグメントの複雑性が常に少なくともn − cになるように定数cが存在する必要があります。この定義は、有限文字列のランダム性の定義とは異なり、プレフィックスフリーコルモゴロフ複雑性を定義するためにどのユニバーサルマシンが使用されるかによって影響を受けません。^[22]

動的システムの場合、エントロピー率と軌道のアルゴリズムの複雑さは、ほぼすべての場合に等式が成立するというブルドノの定理によって関連しています。^[23]${\displaystyle K(x;T)=h(T)}$${\displaystyle x}$

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

定理（定理14.2.5 ^[25]）バイナリ文字列の条件付きコルモゴロフ複雑度は、バイナリエントロピー関数（エントロピー率と混同しないでください） を満たす。${\displaystyle x_{1:n}}$$${\displaystyle {\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)}$$${\displaystyle H_{b}}$

コルモゴロフ複雑度関数は停止問題を決定することと同等です。

停止オラクルがあれば、文字列のコルモゴロフ複雑度は、いずれかの停止プログラムが文字列を出力するまで、辞書式順序ですべての停止プログラムを試すだけで計算できます。

他の方向ははるかに複雑です。^{[26] [27]}これは、コルモゴロフ複雑性関数が与えられた場合、任意の大きな に対してとなる関数 を構築できることを示しています。ここで はビジービーバーシフト関数（ とも表記）です。 のより低い値で関数を修正するとの上限が得られ、停止問題が解決します。 ${\displaystyle p}$${\displaystyle p(n)\geq BB(n)}$${\displaystyle n}$${\displaystyle BB}$${\displaystyle S(n)}$${\displaystyle n}$${\displaystyle BB}$

入力を として受け取り、 を使用するこのプログラムについて考えます。 ${\textstyle p_{K}}$${\textstyle n}$${\textstyle K}$

• 長さ のすべての文字列を一覧表示します。${\textstyle \leq 2n+1}$
• このような文字列ごとに、長さ のすべての（プレフィックスなしの）プログラムを列挙し、そのうちの 1 つが を出力するまで続けます。その実行時間を記録します。${\textstyle x}$${\displaystyle K(x)}$${\textstyle x}$${\textstyle n_{x}}$
• 最大のものを出力します。${\textstyle n_{x}}$

背理法によって、すべての大きい に対して であることが証明されます。 ${\textstyle p_{K}(n)\geq BB(n)}$${\textstyle n}$

を長さ の Busy Beaver とします。入力を受け取らない次の (プレフィックスなしの) プログラムを考えます。 ${\textstyle p_{n}}$${\displaystyle n}$

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

プログラムによって出力される文字列を とします。 ${\textstyle x}$

プログラムの長さはで、 はBusy Beaver の長さに由来し、は数 に対する(プレフィックスなしの) Elias デルタ コードの使用に由来し、 はプログラムの残りの部分に由来します。したがって、すべての大きな に対して となります。さらに、長さ のプログラムは限られているため、ピジョンホール原理により となります。仮定により となるため、長さ のすべての文字列には実行時間 の最小プログラムがあります。したがって、文字列には実行時間 の最小プログラムがあります。さらに、そのプログラムの長さは です。これは の構築方法と矛盾しています。 ${\textstyle \leq n+2\log _{2}n+O(1)}$${\displaystyle n}$${\textstyle p_{n}}$${\displaystyle 2\log _{2}n}$${\displaystyle n}$${\displaystyle O(1)}$$${\displaystyle 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)}$${\textstyle \leq 2n+1}$${\textstyle <BB(n)}$${\textstyle x}$${\textstyle <BB(n)}$${\textstyle K(x)\leq 2n}$${\textstyle x}$

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

注意。 は、入力ストリームが であることを意味するのではなく、汎用チューリングマシンが最初のセグメント を読み取った後、それ以上の入力を読み取らずにある時点で停止し、停止したときに が出力テープに 書き込まれることを意味します。${\displaystyle U(p)=x}$${\displaystyle p000\cdots }$${\displaystyle p}$${\displaystyle x}$

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

2つの文字列の条件付きコルモゴロフ複雑度は、大まかに言えば、手順への補助入力としてyが与えられたときのxのコルモゴロフ複雑度として定義されます。 ^{[28] [29]}${\displaystyle K(x|y)}$

長さ条件付き複雑性もあり、これはxの長さが既知/入力として与えられたときのxの複雑性である。 ^{[30] [31]}${\displaystyle K(x|L(x))}$

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

• ベリーパラドックス
• コードゴルフ
• データ圧縮
• 記述的複雑性理論
• 文法誘導
• 帰納的推論
• コルモゴロフ構造関数
• レーベンシュタイン距離
• ソロモノフの帰納的推論理論
• サンプルエントロピー

• Blum, M. (1967). 「機械のサイズについて」.情報と制御. 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
• Brudno, 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-0387339986。
• ユウ、マニン（1977）。『数理論理学講座』。シュプリンガー出版。ISBN 978-0-7204-2844-5。
• シプサー、マイケル (1997)。計算理論入門。PWS。ISBN 0-534-95097-3。
• Downey, Rodney G.; Hirschfeldt, Denis R. (2010). 「アルゴリズムのランダム性と複雑性」。計算可能性の理論と応用。doi : 10.1007 / 978-0-387-68441-3。ISBN 978-0-387-95567-4. ISSN  2190-619X。

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