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

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

Post的模型采用了由"双向无限序列的空间或盒子"组成的"符号空间"，每个盒子能处于在两种可能状态中之一，也就是"有标记的"（一个竖线）和"无标记的"（空）。最初，有限多的盒子是有标记的，余下的是无标记的。接着一个"工人"在盒子间移动，一次只操作一个盒子，依据固定有限的"指令的集合"，它们编号为（1,2,3,...,n）。开始于"被挑选为起点的盒子"，工人每次一条的服从于指令集合，开始于指令1。

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

（a）标记当前操作的盒子（假定为空的），

（b）去除盒子的标记（假定为有标记的），

（c）移动到右边的盒子，

（d）移动到左边的盒子，

（e）确定当前的盒子是否是有标记的。

特别是，给工人的第i条"指令"是下列形式之一：

（A）进行操作Oi[Oi=（a），（b），（c）或（d）]并接着服从指令ji，

（B）进行操作（e）并依据答案的与否来相应的服从指令ji'或ji' '，

（C）停止。

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

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

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

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

图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用{\displaystyle \langle M\rangle }表示图灵机{\displaystyle M}的编码。

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机{\displaystyle M}的编码{\displaystyle \langle M\rangle }，然后模拟{\displaystyle M}的运作，这样的图灵机称为通用图灵机（Universal Turing Machine）。现代电子计算机的计算模型其实就是这样一种通用图灵机，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。1

本词条内容贡献者为: