セル・オートマトン
コンピュータの先駆者コンラート・ツーゼは、素粒子の持つ情報についての問題を解くため、不規則な格子を考案した。またエドワード・フレドキンは "finite nature hypothesis" と名付けた仮説を提唱。「最終的に時間や空間を含む全ての物理量は離散的で有限だと判明するだろう」とした。フレドキンとウルフラムはデジタル物理学の信奉者である。
21世紀に入ると、非標準計算についての著作からこの考え方に沿った示唆が生まれている。ウルフラムの A New Kind of Science では、CAが物理学を含めた様々な主題を理解する鍵だとしている。(Francesco Berto が創始し、Gabriele Rossi と Jacopo Tagliabue が発展させた)iLabsが2010年に出版した Mathematics Of the Models of Reference では「菱形十二面体」をベースとする格子と独特の規則で2次元および3次元の宇宙を説明するモデルを提案している。このモデルはチューリングマシンと等価であり、完全な可逆性を有し(様々な量を保存し、情報を決して失わない)、宇宙の発展についての質的な論述を計算できる論理が組み込まれている。
離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンはチューリングマシンとよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタルコンピュータ」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。
セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の平面充填構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素(すなわちセル)は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日のノイマン型コンピュータのプロセッサとはかなり違う。
例えばシストリックアレイ(英語版)はCAプロセッサアレイの一例である。
例えば「ルール30」と呼ばれるのは、上の表のように時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この2進数の数を10進数に直すと30であるためであり、これをウルフラム・コードと呼ぶ。
ルール30は「クラス3」の挙動を示し、単純な初期状態からもカオス的な経過を示し、無作為な履歴になっている。
ルール110はライフゲームのように「クラス4」の挙動を示し、完全な無作為でもなく、完全な反復でもない。局所的構造が現れ、様々な複雑な形で相互作用する。1994年ウルフラムの研究助手だったマシュー・クックは、それら構造の一部がチューリング完全性をサポートするのに十分であることを証明した。ルール110は非常に単純な1次元のシステムであり、具体的なことを実行するよう設計するのは困難であるため、この成果は興味深い。この結果からウルフラムはクラス4のセル・オートマトンが本質的にチューリング完全である可能性を示唆した。1998年、セル・オートマトンの学会がサンタフェ研究所で開催され、クックはその成果を発表したが、ウルフラムは A New Kind of Science の出版前にその証明の詳細を公表したくなかったため、証明の詳細は発表されなかった。2004年、Cookの証明がウルフラムの発行する雑誌 Complex Systems (Vol. 15, No. 1) で発表された。実に証明してから10年が経過している。ルール110をベースとして極小の万能チューリングマシンが構築されている。