複雑性
システムの研究のひとつとしての、複雑 (complex) なシステム、すなわち複雑系 (complex system) の研究の歴史は長い。複雑系は生物的なもの、経済的なもの、テクノロジー的なものなど様々なものが存在する。最近では、実世界の社会認知的システムの研究も複雑系を扱っている。複雑系は高次元で非線形であることが多く、モデル化が難しい。状況によっては低次元の振る舞いをすることもある。
情報理論において、アルゴリズム情報理論はデータとしての文字列の複雑性を扱う。
複雑な文字列は圧縮しにくい。直観的には、文字列の圧縮率は採用したコーデックで変わってくると思われる。コーデックは理論的には任意の言語について作成でき、中には非常に小さいコマンド X が非常に長い記号列(例えば 18995316)を生成するものもありうる。任意の2つのチューリング完全な言語は互いを実装できる。2つの言語による符号化の長さは変換言語の長さを上限として様々となるが、データ文字列が十分大きければその差はほとんど無視できる。
アルゴリズム的な複雑性の尺度は、無作為なノイズに高い値を割り当てる傾向がある。しかし、複雑系を研究する分野では無作為性と複雑性を区別して扱う。
情報量も複雑性の尺度として情報理論で使われることがある。