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