コルモゴロフ複雑性 - AITwiki アルゴリズム情報理論ウィキ - atwiki（アットウィキ）

AITwiki アルゴリズム情報理論ウィキ

AITwiki アルゴリズム情報理論ウィキ

ページ一覧

コルモゴロフ複雑性

普遍計算機 $\cal U$ に対して，記号列 $x$ のコルモゴロフ複雑性 $K_{\cal U}(x)$ は以下の様に定義される:

$K_{\cal U} (x)=\min_{p:{\cal U}(p)=x} {l(p)},$

即ち $\cal U$ の全てのプログラムの内， $x$ を出力し停止する最も短かいプログラム $\hat p$ の長さ $l(\hat p)$ である．

リンク

http://ja.wikipedia.org/wiki/コルモゴロフ複雑性

「コルモゴロフ複雑性」をウィキ内検索

最終更新：2009年10月26日 16:55