Post–Turing machine とは

記事チューリングマシンはチューリングマシンの一般的な紹介ですが、この記事ではチューリングマシンの特定のクラスについて説明します。
ポストチューリングマシンは、以下に説明するEmil PostのTuring等価計算モデルの変形を含む、特に単純なタイプのチューリングマシンの「プログラム定式化」である。 (PostのモデルとTuringのモデルは、互いに非常に類似していましたが、独立して開発されました.Turingの論文は1936年5月に出版され、その後10月にPostに掲載されました。)Turing後の機械は、2進アルファベット、記憶場所と、記憶場所間の双方向移動とその内容の変更とを一度に1つずつ指示するプリミティブプログラミング言語とを含む。 「Post-Turing program」と「Post-Turing machine」という名前は、Martin Davisによって1973-1974年に使われた(Davis 1973、p。69ff)。 1980年後半、Davisは「Turing-Postプログラム」という名前を使用しました(Davis、Steen p.241)。