波斯特-图灵机
维基百科，自由的百科全书
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) 进行操作 Oi [Oi = (a), (b), (c) 或 (d)] 并接着服从指令 ji，
- (B) 进行操作 (e) 并依据答案的与否来相应的服从指令 ji' 或 ji' ' ，
- (C) 停止。
(上述交错的文本和斜体同最初一样)。Post 备注说这种公式处于开发的"初始阶段"，并提及了在最终的"终极形式"中的一些可能的"更大的灵活性"，包括：
- (1) 把无限的盒子替代为有限可扩展的符号空间，"扩展原始操作来允许随着处理的进行对给定的有限符号空间作必要的延伸"，
- (2) 使用多于两个符号的字母表，"有多于一种的方式标记盒子"，
- (3) 介入有限多的 "物理对象充当指针，工人识别它们并从一个盒子移动到另一个"。
