コルモゴロフ複雑性
この値を選ぶに当っては、s が GenerateParadoxicalString() というプログラムによって生成される点に着目すると良い。このプログラムの長さは、たかだか
U + log 2  ( n 0 ) + C {\displaystyle U+\log _{2}(n_{0})+C\quad }
である(C は GenerateParadoxicalString() が GenerateComplexString() を呼び出す前後の固定部分の長さを表す)。n と log2(n) では前者の方が急速に増大することが明らかなので、ある n0 が存在して次の関係を満たす。
U + log 2  ( n 0 ) + C < n 0 . {\displaystyle U+\log _{2}(n_{0})+C<n_{0}.\quad }
ところが、これは「少なくとも n0 以上の複雑性を持つ」ということの定義に反してしまう。何故なら K(s) の定義により、文字列 s を生成したプログラムの長さは少なくとも n0 以上はある筈なのに、s を生成した GenerateParadoxicalString() の長さは n0 よりも短いからである。以上より、"KolmogorovComplexity" というプログラムは、任意の文字列について複雑性を計算することは出来ないことが示された。
この証明は背理法によるが、ここで現れる矛盾はベリーのパラドックスに似ている:「n を30字未満では表現できない最小の正の整数としよう」。他の証明方法として、K が計算不能であることを停止問題 H が計算不能であることに帰着して示すこともできる。K と H はチューリング同値である。