波斯特-图灵机

Post-图灵机是一种特别简单类型的图灵机的"程序公式化"，由下面描述的Emil Post的图灵等价的计算模型构成。（Post的模型和图灵的模型，尽管相互之间非常类似，但却是独立开发的。图灵的论文在1936年五月出版，Post的论文在十月出版。）Post-图灵机使用二元字母表，无限序列的二元存储位置，和带有在存储位置上双向移动和一次一个更改其内容的指令的原始编程语言。"Post-图灵程序"和"Post-图灵机"的名字由Martin Davis在1973年-1974年使用（Davis 1973, p.69ff）。后来Davis在1980年使用名字"Turing-Post程序"（Davis, in Steen p. 241）。

Post模型

在他1936年的论文"Finite combinatory processes—formulation 1"（可以在The Undecidable的289页找到它），Emil Post描述了非常简单的一个模型，它被猜测为"逻辑上等价于递归函数"，并且后来被证明确实如此。

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）停止。

（上述交错的文本和斜体同最初一样）。Post备注说这种公式处于开发的"初始阶段"，并提及了在最终的"终极形式"中的一些可能的"更大的灵活性"，包括：

（1）把无限的盒子替代为有限可扩展的符号空间，"扩展原始操作来允许随着处理的进行对给定的有限符号空间作必要的延伸"，

（2）使用多于两个符号的字母表，"有多于一种的方式标记盒子"，

（3）介入有限多的"物理对象充当指针，工人识别它们并从一个盒子移动到另一个"。

定理