数学を初めとした理系の学問と哲学について　１６

数学を初めとした理系 ..

80:考える名無しさん
21/07/24 00:20:02.30 0.net
コルモゴロフ複雑性（ Kolmogorov complexity）とは、計算機科学において有限長のデータ列の
複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値と
して定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。
この画像はフラクタル図形であるマンデルブロ集合の一部である。このJPEGファイルのサイズは
17KB以上（約140,000ビット）ある。ところが、これと同じファイルは140,000ビットよりも
遥かに小さいコンピュータ・プログラムによって作成することが出来る。従って、
このJPEGファイルのコルモゴロフ複雑性は140,000よりも遥かに小さい。
コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題や
ゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性や
その他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム
情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、
グレゴリー・チャイティンによって創始された。

次ページ

続きを表示

1を表示