記述言語による相対性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)
「コルモゴロフ複雑性」の記事における「記述言語による相対性」の解説
定義から明らかなように、コルモゴロフ複雑性は記述言語あるいは万能計算機に依存する。 しかし、ある万能計算機 u1 から別の万能計算機 u2 にプログラムを移植しても、コルモゴロフ複雑性はたかだか（u1 と u2 によって決まる） 定数分しか増えない。なぜなら2つの万能計算機は、必ずもう一方の計算機をエミュレートできるからである。 u2 上で u1を模倣するエミュレーションプログラム ε1,2 を作り、その上で u1 のためのプログラム p を動かせば、結果として u2 の上でプログラム p を動かせたことになる。 そしてこのエミュレーションプログラムはエミュレートするプログラムの大きさにかかわらずつねに一定である。 従って、 u2 上でのコルモゴロフ複雑性はたかだか l(p) + l(ε1,2) である。 逆の場合も同様にエミュレートができるので、すなわち、 定理： 任意の万能計算機 u1, u2 に対し、ある定数 c1,2 が存在して、任意の x に対し、 | K 1 ( x ) − K 2 ( x ) | ≤ c 1 , 2 . {\displaystyle |K_{1}(x)-K_{2}(x)|\leq c_{1,2}.} が成り立つ。 なおコルモゴロフ複雑性の議論では、記述言語の違いによりこのようなある定数分を除いて成立するという関係が頻出する。
※この「記述言語による相対性」の解説は、「コルモゴロフ複雑性」の解説の一部です。
「記述言語による相対性」を含む「コルモゴロフ複雑性」の記事については、「コルモゴロフ複雑性」の概要を参照ください。
- 記述言語による相対性のページへのリンク
