永恒的数学
开放获取

抽象的

理解图灵机计算的方法

约翰·尼克松

本文是对描述图灵机 (TM) 行为的方法的从头开始的研究。它展示了如何使用受限于有限磁带长度的 TM 结果来加速任何 TM 计算。这种规则的非冗余集被称为不可约规则（计算）规则（IRR），并且描述了一种算法来为任意长度的磁带的任何TM生成它们。该算法已用 C++ 实现，可以免费获得。研究的例子表明，IRR 的数量可以是有限的，也可以是无限的。对于多个TM，当它们是无限的时，找到它们的递归公式并且期望这总是可能的。这些公式是通过分别检查每个示例中的 IRR 并正确猜测它并通过归纳证明它而找到的。在研究的示例中找到了一个表，显示哪个 IRR 跟随其他 IRR 取决于下一个符号读取，并提供了有关 TM 行为的大量信息。预计以这种方式分析通用TM以发现解释周期是如何工作的是可能的。