波斯特-圖靈機

波斯特-圖靈機（Post-圖靈機）是一種特別簡單類型的圖靈機的「程序公式化」由下面描述的埃米爾·萊昂·波斯特（英語：Emil Post）的圖靈等價的計算模型構成。波斯特的模型和圖靈的模型，儘管相互之間非常類似，但卻是獨立開發的。圖靈的論文在1936年五月出版，波斯特的論文在十月出版。波斯特-圖靈機使用二元字母表，無限序列的二元存儲位置，和帶有在存儲位置上雙向移動和一次一個更改其內容的指令的原始程式語言。

「波斯特-圖靈程序」和「波斯特-圖靈機」的名字由馬丁·戴維斯在1973年-1974年使用（Davis 1973, p.69ff）。後來戴維斯在1980年使用名字「圖靈-波斯特程序」（Turing-Post）（Davis, in Steen p. 241）。

波斯特模型

在他1936年的論文"Finite combinatory processes—formulation 1"（可以在The Undecidable的289頁找到它），埃米爾·萊昂·波斯特（英語：Emil Post）描述了非常簡單的一個模型，它被猜測為"邏輯上等價於遞歸函數"，並且後來被證明確實如此。

埃米爾·波斯特的模型採用了由"雙向無限序列的空間或盒子"組成的"符號空間"，每個盒子能處於在兩種可能狀態中之一，也就是"有標記的"（一個豎線）和"無標記的"（空）。最初，有限多的盒子是有標記的，餘下的是無標記的。接著一個"工人"在盒子間移動，一次只操作一個盒子，依據固定有限的"指令的集合"，它們編號為（1,2,3,...,n）。開始於"被挑選為起點的盒子"，工人每次一條的服從於指令集合，開始於指令1。

指令可以要求工人進行下列"基本活動"或"操作":

（a） 標記當前操作的盒子（假定為空的），

（b） 去除盒子的標記（假定為有標記的），

（c） 移動到右邊的盒子，

（d） 移動到左邊的盒子，

（e） 確定當前的盒子是否是有標記的。

特別是，給工人的第i條"指令"是下列形式之一：

（A）進行操作O_i [O_i =（a），（b），（c）或（d）]並接著服從指令j_i，

（B）進行操作（e）並依據答案的與否來相應的服從指令j_i'或j_i' ' ，

（C）停止。

（上述交錯的文本和斜體同最初一樣）。埃米爾·波斯特備註說這種公式處於開發的"初始階段"，並提及了在最終的"終極形式"中的一些可能的"更大的靈活性"，包括：

（1）把無限的盒子替代為有限可擴展的符號空間，"擴展原始操作來允許隨著處理的進行對給定的有限符號空間作必要的延伸"，

（2）使用多於兩個符號的字母表，"有多於一種的方式標記盒子"，

（3）介入有限多的"物理對象充當指針，工人識別它們並從一個盒子移動到另一個"。

定理