在数学和计算机科学中，芝诺机（缩写为ZM ，也称为加速图灵机、 ATM ）是一种与图灵机相关的假设计算模型，它能够执行涉及可数无限个算法步骤的计算。 大多数计算模型都不考虑这些机器。
芝诺机的想法最早由赫尔曼·外尔于 1927 年提出；该名称指的是芝诺悖论，源于古希腊哲学家埃利亚的芝诺。芝诺机在某些理论中发挥着至关重要的作用。例如，物理学家弗兰克·J·蒂普勒(Frank J. Tipler) 提出的欧米茄点理论只有在芝诺机可行的情况下才有效。
定义
芝诺机是一种图灵机，可以采取无限多的步骤，然后继续采取更多步骤。这可以被认为是一个超级任务，其中\frac{1}{2^n}执行n步骤；因此，第一步花费 0.5 个时间单位，第二步花费 0.25 个时间单位，第三步花费 0.125 个时间单位，以此类推，经过一个时间单位后，将执行无数个步骤。
无限时间图灵机
思想实验的无限时间图灵机动画。一个细胞交替进行0和1对于之前的步骤\omega .细胞变成1在\omega因为序列不收敛。]]
芝诺机的一个更正式的模型是无限时间图灵机。它最早由杰弗里·基德在其未发表的著作中定义，后经乔尔·哈姆金斯和安迪·刘易斯在《无限时间图灵机》无限时间图灵机是经典图灵机模型的扩展，包含了超限时间；即超越所有有限时间的时间。 即使机器没有其他方式访问此状态情况也是如此，例如没有节点转换到该状态，。在任何极限步骤中，读写头的位置都设置为零。 最后，磁带的状态由先前磁带状态的极限上确界决定。对于某些机器T ，一个单元格k并且，极限序数\lambda然后
T(\lambda)_k = \limsup_{n\rightarrow \lambda}T(n)_k
这就是k第个单元格\lambda当机器接近时，同一单元的极限是\lambda . 如果它收敛，则可以认为是极限，或者1否则。 Cristian Calude 和 Ludwig Staiger 提出了以下伪代码算法，作为在芝诺机上运行时解决停机问题的方法。
**程序开始
**在输出纸带的第一个位置上写入0；
**循环开始
**模拟给定图灵机在给定输入上的一个后继步骤；
**如果图灵机已停机，则
**在输出纸带的第一个位置上写入1，并跳出循环；
**循环结束
**程序结束
通过检查输出磁带的第一个位置1单位时间过去后，我们就能判断给定的图灵机是否停止。 ，因为它们确实定义了超限步骤的状态。 全部\Pi_1^1 集合 可用无限时间图灵机判定, and \Delta_2^1 集合为半可判定.
芝诺机无法解决自身的停机问题。
参见
- 极限计算
- Specker序列
- 罗斯-利特尔伍德悖论
参考
评论 (0)