コロモゴロフ複雑性の「計算不能性」

【 コロモゴロフ複雑性の「計算不能性」】

https://youtu.be/Iir7Y9WNcZk?list=PLQIrJ0f9gMcOWKDmKxI3aJ6UYf6gaPa2K

コロモゴロフ複雑性には、重要な性質があります。

それは、コロモゴロフ複雑性は、xを出力するプログラムの最小の長さとして定義されるのですが、計算理論的には、それは「計算不能」です。

ここでは、そのことを見ていきましょう。

つぎのような関数Lを考えます。

  𝐿(𝑛)=𝐾(𝑘)≥2𝑛 となるような最小の𝑘

関数 L : ℕ → 𝒪 は、nに対して、そのコロモゴロフ複雑性𝐾(𝑘)が2n 以上となるような最小の kを返します。もし、Kがすべてのnについて計算可能だとすると、Lもすべてのnについて計算可能です。

  ここで、すべての𝑛に対して、𝐾(𝐿(𝑛))≥2𝑛 です。

なぜならば、すべての𝑛について、𝐿(𝑛)は、𝐾(𝐿(𝑛)) ≥ 2𝑛を満たす最小のものであるからです。

ここで、ある V : 𝒪  → ℕ  が、「最適」であるとしましょう。この時、𝐾=𝐾_𝑉 と書くことができます。前回見た「不変性定理」から、𝐾 ≤ 𝐾_𝐿 + 𝑐 である定数cが存在することがわかります。
 
  𝐾_𝐿 の定義から、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 が成り立ちます。

なぜならば、𝐾_𝜑 (𝑦)=min⁡{ |𝑝|  :𝜑(𝑝)=𝑦 } で、𝜑=𝐿として、
𝐾_𝐿 (𝐿(𝑛))=min⁡{ |𝑝|  :𝐿(𝑝)=𝐿(𝑛) }となります。
𝑝=𝑛 の場合、L(𝑝)=𝐿(𝑛)  が成り立つので、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 がいえます。

そうすると、次の不等式が成り立ちます。

  2𝑛 ≤ 𝐾(𝐿(𝑛)) ≤ 𝐾_𝐿 (𝐿(𝑛)) + 𝑐 ≤ 𝑛 + 𝑐 

  2𝑛 ≤ 𝑛 + 𝑐 から 𝑛 ≤ 𝑐 ということになります。

ただし、この不等式は、全ての n については成り立ちません。𝑛 > 𝑐 なるnについては矛盾します。

Kがすべてのnについて計算可能だと仮定すると、矛盾が導かれるので、Kは計算可能ではありません。

------------
このショートムービーのpdfファイルは、次から利用できます。

セミナー「計算科学とエントロピー」のまとめページは、こちらです。

セミナーへのお申し込みは、次のサイトからお願いします。

コメント

このブログの人気の投稿

マルレク・ネット「エントロピーと情報理論」公開しました。

初めにことばありき

宇宙の終わりと黒色矮星