メモ

Kolmogorov complexity

アンドレイ・ニコライェヴィッチ・コルモゴロフが提唱した文字列の複雑性。計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。

コルモゴロフ複雑性の概念は一見すると単純なものであるが、テューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。

ナシーム・ニコラス・タレブの「ブラック・スワン」で私たちが講釈が好きなのは情報の溜め込みや読み込みを行うにコストがかかるためである。いわゆる「コルモゴロフ複雑性」を減らしたい衝動にかられるためである。