ポスト・チューリングマシン
1936年にエミール・ポストが示した計算モデル。無限に並んだ箱の列の上を動く作業者が、番号付きの命令リストに従う。チューリングと同じ発想を、同じ年に独立して発表したものだ。
ポストは、無限に続く箱の列がある部屋にいる「作業者」を考えた。箱はそれぞれ印が付いているか、いないかのどちらかである。命令は五つ。箱に印を付ける、印を消す、一つ右へ動く、一つ左へ動く、箱に印があるかで分岐する。各命令は次に実行する命令の番号を指定する。これは現代的な意味でのプログラム、つまりジャンプ付きの番号付きリストであり、チューリングの機械が同じ内容を状態遷移表で表すのと対照的だ。
論文「Finite Combinatory Processes — Formulation 1」がJournal of Symbolic Logicに載ったのはチューリングの論文のわずか数か月後で、ポストは独立した研究であると校正時の注記で断らねばならなかった。評価に差がついたのは、ポストがモデルを示すところで止まったのに対し、チューリングはそれにできないことの証明まで進んだからだ。ポストは1921年の時点で不完全性定理の間近まで迫っていたが、発表していない。「ポスト・チューリングマシン」という呼び名は、ずっと後にマーティン・デイヴィスが作った。