チューリング完全
チューリングマシン以外にチューリング完全な計算モデルとしては、ラムダ計算やμ再帰関数やマルコフアルゴリズムなどが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。
チューリング完全性に関する重要なトピックとして、チャーチ=チューリングのテーゼが挙げられる。
スティーブン・ウルフラムは、以前からこういった問題を追求していたことで知られる一人だが、最も単純でありながらチューリング完全であろう計算モデルとして、2状態3記号のチューリングマシン、「2, 3 チューリングマシン」に目を付け、2007年にその万能性(あるいはその否定)の証明に2万5000ドルの懸賞金をかけた。問題提起から47日後、バーミンガム大学コンピューター科学部の学生だったアレックス・スミスが肯定的(万能である、とする)証明を提出し、懸賞は確定した。