チューリングマシン
果てしなく続く紙テープと読み書きヘッドを持つ数学上の玩具。コンピューターに「できないこと」を証明するために、1936年に考案された。
構成要素は4つ。マス目に区切られたテープ、一度に1記号を読み書きするヘッド、有限個の状態、そして現在の状態とヘッド下の記号に応じて何をするかを定めた表である。装置はこれで全部だ。算術も、レジスタも、アドレス指定もない。それでも、他のどんな計算モデルが計算できるものも、これは計算できる。
実機を作ることが目的だったわけではない。Alan Turingに必要だったのは、「機械的手続き」を、どんな手続きにもできないことを論じられるほど切り詰めて定義することだった。そしてヒルベルトの決定問題への答えは否定的に出た。アルゴリズムでは決着しない問いがあり、任意のプログラムが停止するかどうかはその一つである。Alonzo Churchも同じ年にラムダ計算で同じ結論に達しており、両モデルの等価性がチャーチ=チューリングのテーゼの中身である。
万能チューリングマシンは、別の機械の記述をテープ上に受け取って、その動作を模倣する。これは、それを実現できるハードウェアが作られる10年も前に述べられた、プログラム内蔵方式の考え方そのものだ。ある言語が「チューリング完全」だというのは、この機械を模倣できるという意味で、いくつか拡張したCSSや、おそらく意図していない何かもその仲間に入る。