チューリング・マシンとは、アラン・チューリングが1936年に導入した抽象的な計算モデルである。無限に伸びるテープ、その上の記号を読み書きするヘッド、有限個の内部状態からなり、「現在の状態と読み取った記号の組に応じて、記号を書き換え、ヘッドを左右に動かし、状態を遷移する」という規則表だけで動作する。この極端に単純な仕組みが、原理的にあらゆる計算可能な手続きを実行できることから、計算可能性の定義そのものとして用いられてきた。任意のチューリング・マシンを模倣できるものを万能チューリング・マシンと呼ぶ。

チューリング・マシンは、単純な規則から複雑な振る舞いが生じる系の典型例でもある。Cellular Automata (CA)やtag system、register machine、mobile automataと並ぶ計算系の一種として、抽象的な数学の道具ではなく物理的な動的システムとして捉え直す視点からは、「万能性を持つ最小構成はどこまで小さくできるか」が焦点となる。1956年にクロード・シャノンが最小の万能チューリング・マシンを問題として提起して以来、万能性には複雑な状態遷移が必要だと考えられてきたが、2状態3記号（規則6本）の (2,3) チューリング・マシンが万能であることが2007年にアレックス・スミスによって示された。

この (2,3) マシンの万能性は「弱い万能性」に基づく。標準的な万能チューリング・マシンが空白テープから計算を始めるのに対し、この場合はテープの両端に特定の繰り返しパターンが置かれていることを許す。初期条件の側に複雑性を押し込んでいるという批判もあるが、系そのものの計算能力を問うならば本質は変わらないという立場もある。いずれにせよ、計算能力が精緻な設計の産物ではなく、ごく単純な規則の連鎖に遍在しうるという見方を支える議論であり、Principle of Computational Equivalence (PCE)の主要な根拠のひとつとなっている。