セル・オートマトン
ウルフラムは秩序状態とカオス状態の間にあるクラス4の様な状態こそが、生命現象などの現実世界で見られる複雑な現象を引き起こす源だと考えた。この研究により、複雑系と呼ばれる新しい科学分野の基盤が確立した。
これらの定義は質的なもので、その解釈には若干の幅がある。ウルフラムは「どんな一般分類体系でも、ある定義ではこのクラスになるが、別の定義では別のクラスになるというケースが必然的に存在する。セル・オートマトンでもそれは変わらない。あるクラスの特徴と別のクラスの特徴を備えた規則群は時として存在する」としている。ウルフラムの分類は、セル・オートマトンの出力を圧縮した長さの分類と経験的に合致している。
CulikとYuによって、ウルフラムの4つのクラスの算術的階層における位置が証明されている。クラス1と2は Π 2 0 {\displaystyle \Pi _{2}^{0}} -完全、クラス3は Σ 3 0 {\displaystyle \Sigma _{3}^{0}} -完全に所属する。
ウルフラムの分類に触発され、CAを形式的に厳密に分類しようとする試みもなされてきた。例えば、CulikとYuは3つのwell-definedなクラス(そしてそれらのどれにも分類されない4番目のクラス)を提案した。これを Culik-Yu クラスなどと呼び、ある規則群がどのクラスに属するかの判定は決定不能だと証明された。