Post模型

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

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

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

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

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。