用户:LynChern/Sandbox

模板:Distinguish/Confusion 一个图灵机是由艾伦·图灵设计的一种假想机器，用于执行计算。它由一个有限状态自动机（通常称为其“控制机制”或程序）连接到一个无界磁带组成，磁带可以左右移动，从中可以读取符号，并可以在其上写入符号。

一个通用图灵机是一种图灵机，它可以被给予以某种形式编码的任何任意图灵机的描述，在其磁带上初始化，并且有限状态机以这样的方式操作描述，从而模拟被描述的机器。通用机得名于它们能够计算任何可计算序列的事实。

图灵机在计算上具有重要意义，因为尽管许多计算模型已被证明只能解决给定图灵机可以解决的计算问题的一个子集，但尚未有任何可定义为算法集合的计算系统被证明能够解决图灵机不能解决的计算问题。

此外，尚未设计出任何通用图灵机明显无法执行的明确定义算法。这导致了丘奇-图灵论题，它（粗略地）指出图灵机是（我们直观上认为的）有效可计算算法的机械体现。也就是说，图灵机可以进行任何可能精确定义算法的计算。

自从艾伦·图灵的论文中发明图灵机以来，许多其他系统已被证明与它们等价。（事实上，其中一些系统，如λ演算、组合子逻辑和波斯特规范系统，早于图灵机。）通过这种方式，图灵机定义了一个等价系统的计算类别；这些系统被称为图灵完备。

由于所有这些原因，证明一个深奥编程语言是否等价于图灵机通常是一个有趣和/或有价值的任务。

形式上，图灵机通常以元组格式描述，$(\Sigma ,{\sigma }_0,Q,q_1,q_h,f)$，包括：

• 符号集合 $\Sigma$
• 空白符号 ${\sigma }_0$
• 状态集合 $Q$
• 起始状态 $q_1$
• 停机状态 $q_h$
• 转移函数 $f:Q\times \Sigma \to \Sigma \times D\times Q$
  • 其中 $D$ 通常是 $\{left,center,right\}$ 或 $\{left,right\}$
  • 对于 $q_h$ 未定义
  • 接受当前状态和当前观察到的符号，然后产生一个新符号来覆盖观察到的符号、一个移动方向以及要转换到的下一个状态

以这种方式描述的图灵机可以被视为一个部分函数 $\Phi :{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$，它接受一个预设的有限长度符号磁带，并（通过机器的变异操作）在磁带上产生一个新的有限符号串。由于集合 ${\Sigma }^{\ast }$ 是可数无限的，图灵机的部分函数也可以写为 $f:\mathbb{N}\rightharpoonup \mathbb{N}$，其中使用自然数和符号串之间的某种编码方案。该函数是部分的，因为机器可能无限循环而不是产生答案。对于在输入磁带 $x$ 上停机的图灵机 $M$，记号为 $M(x)\downarrow$，而对于在该输入上不停机的图灵机，记号为 $M(x)\uparrow$。

停机问题

关于图灵机的一些最著名的事实涉及停机状态。机器是否会从给定的起始配置进入停机状态？我们有两个重要结果。

定理。 如果一个图灵机停机，那么在ETCS和ZF中存在证明它停机的证明。

定理（图灵机停机的不可判定性）。 没有有效程序能在ETCS或ZF中产生证明，证明给定图灵机在给定输入磁带上停机。

通俗地说，图灵机是否停机（在选定的输入上）是一个具体的、客观的、野蛮的事实；相应的证明仅仅是机器执行的历史。然而，标准集合论并不总是能够证明这样的事实。根本问题在于强集合论的哥德尔不完备性；当集合论能够编码数论时，它也能够引入哥德尔关于数论不完备性的所有推理。

另一个非正式的教训是，可计算是图灵机做什么，而不是图灵机是什么。关于图灵机的事实可能不是可计算的！

变体

• 顺时针图灵机
• 预言机
• 近图灵机
• 交换图灵机

外部资源

• 参见维基百科上的图灵机
• 图灵机语言 - 一个用Python编写的图灵机解释器
• 可视化图灵机 - 动画图灵机模拟器
• 论可计算数及其在判定问题上的应用 - 图灵介绍其机器的论文
• Boolos, G. 和 Jeffrey, R., 可计算性与逻辑, 第二版, 剑桥: 剑桥大学出版社, 1980.
• 在线图灵机模拟器
• 另一个模拟器
• 又一个模拟器
• 图灵机模拟语言