波斯特-图灵机
维基百科,自由的 encyclopedia
波斯特-图灵机(Post-图灵机)是一种特别简单类型的图灵机的“程序公式化”由下面描述的埃米尔·莱昂·波斯特(英语:Emil Post)的图灵等价的计算模型构成。波斯特的模型和图灵的模型,尽管相互之间非常类似,但却是独立开发的。图灵的论文在1936年五月出版,波斯特的论文在十月出版。波斯特-图灵机使用二元字母表,无限序列的二元存储位置,和带有在存储位置上双向移动和一次一个更改其内容的指令的原始编程语言。
“波斯特-图灵程序”和“波斯特-图灵机”的名字由马丁·戴维斯在1973年-1974年使用(Davis 1973, p.69ff)。后来戴维斯在1980年使用名字“图灵-波斯特程序”(Turing-Post)(Davis, in Steen p. 241)。