芝诺机

在数学和计算机科学中，芝诺机（缩写为ZM ，也称为加速图灵机、 ATM ）是一种与图灵机相关的假设计算模型，它能够执行涉及可数无限个算法步骤的计算。 大多数计算模型都不考虑这些机器。

芝诺机的想法最早由赫尔曼·外尔于 1927 年提出；该名称指的是芝诺悖论，源于古希腊哲学家埃利亚的芝诺。芝诺机在某些理论中发挥着至关重要的作用。例如，物理学家弗兰克·J·蒂普勒(Frank J. Tipler) 提出的欧米茄点理论只有在芝诺机可行的情况下才有效。

 定义 
芝诺机是一种图灵机，可以采取无限多的步骤，然后继续采取更多步骤。这可以被认为是一个超级任务，其中执行步骤；因此，第一步花费 0.5 个时间单位，第二步花费 0.25 个时间单位，第三步花费 0.125 个时间单位，以此类推，经过一个时间单位后，将执行无数个步骤。

 无限时间图灵机 
芝诺机的一个更正式的模型是无限时间图灵机。它最早由杰弗里·基德在其未发表的著作中定义，后经乔尔·哈姆金斯和安迪·刘易斯在《无限时间图灵机》无限时间图灵机是经典图灵机模型的扩展，包含了超限时间；即超越所有有限时间的时间。 一台经典的图灵机在第 0 步有一个状态（处于起始状态，纸带为空，读写头在0号单元格），并有一套从一个状态转移到其后继状态的规则。这样，图灵机的状态就为所有对应于自然数的计算步骤定义了。一台无限时间图灵机（ITTM）保留了这些属性，但它也定义了机器在极限序数处的状态——也就是说，这些序数既不是 0，也不是任何其他序数的后继。图灵机的状态由3个部分组成：

 状态
 读写头的位置
 磁带内容

正如经典图灵机具有带标记的起始状态（即程序启动时的状态）一样， 无限时间图灵机（ITTM）也具有带标记的极限状态，即机器在任何极限序数下的状态。 即使机器没有其他方式访问此状态情况也是如此，例如没有节点转换到该状态，。在任何极限步骤中，读写头的位置都设置为零。  最后，磁带的状态由先前磁带状态的极限上确界决定。对于某些机器 ，一个单元格并且，极限序数然后

这就是第个单元格当机器接近时，同一单元的极限是 . 如果它收敛，则可以认为是极限，或者否则。 

 可计算性 
芝诺机被提出作为一种比经典图灵机更强大的计算模型，其基于其能够解决经典图灵机的停机问题。  Cristian Calude 和 Ludwig Staiger 提出了以下伪代码算法，作为在芝诺机上运行时解决停机问题的方法。 

 程序开始 

     在输出纸带的第一个位置上写入0；    

     循环开始        

         模拟给定图灵机在给定输入上的一个后继步骤；

         如果图灵机已停机，则

             在输出纸带的第一个位置上写入1，并跳出循环；

      循环结束

 程序结束

通过检查输出磁带的第一个位置单位时间过去后，我们就能判断给定的图灵机是否停止。 相反，Oron Shagrir 认为，芝诺机的状态仅在区间 ，因此不可能同时检查磁带此外，由于经典图灵机没有任何时间信息，因此添加时间信息（无论是否加速）本身都不会增加任何计算能力。 

然而，无限时间图灵机能够实现给定的算法，并在时间停止得到正确的解 ，因为它们确实定义了超限步骤的状态。 全部  集合 可用无限时间图灵机判定, and  集合为半可判定.

芝诺机无法解决自身的停机问题。 

 参见 

 极限计算
 Specker序列
 罗斯-利特尔伍德悖论

 参考 

Category:带有伪代码示例的条目
Category:图灵机
Category:计算模型