图灵机

基本介绍

简单来说，图灵机的最大用处就是回答了两个根本性的问题：什么是计算？ 以及 计算的极限在哪里？
图灵机最重要的用途可以归纳为以下三点：

1、现代计算机的理论原型

通用计算： 图灵机证明了只需要一个单一、通用的机器，就能执行所有可计算的任务。
冯·诺依曼结构： 这一概念直接启发了现代计算机的基本架构，即程序（指令）和数据可以像存放在图灵机的纸带上一样，存储在一起并被执行。

2、定义“可计算性”的边界

图灵论题： 确立了算法（机械过程）的极限。所有能用算法解决的问题都能被图灵机解决。
解决了判定问题： 判定问题简单来说就是：是否存在一个明确的、可机械执行的步骤（即算法），能够判断任何一个给定的数学命题是真还是假？ 图灵机给出的答案是 “不存在” 。

3、衡量算法效率的标准

复杂度分析： 图灵机是衡量算法效率（如 O(n) 或 O(n2)）的标准单位。它量化了算法所需的时间（步数）和空间（存储单元）。
复杂性理论： 图灵机是 P 问题 和 NP 问题 理论的基石。

运行过程

零件：

1、存储数据，可以被划分为单元格，每个单元格写入一个符号（数据）。

2、读写头，可以在纸带上左右移动，一次读取或写入一个单元格的符号。

3、状态寄存器，存储机器当前的内部状态（例如，机器正在“寻找 0”或“准备写入 1”）。

4、程序表，这是一套规则或程序，决定机器在每一步如何操作。

过程：

图灵机每一步的转换，都由一个五元组 的指令来定义：

(当前状态,读取符号)⇒(新的状态,写入符号,移动方向)

当图灵机开始运行时，它在一个循环中重复执行以下三个动作：

读取 (Read)

机器的读写头 查看它当前所在单元格的符号（读取符号），同时机器的状态寄存器 记录当前的内部状态 （当前状态）。

查找指令 (Look Up Instruction)

机器的有限控制单元 在它的指令表 中查找匹配的规则。它要找到一个与当前的当前状态和读取符号 完全吻合 的五元组。

执行更新 (Execute Transition)

一旦找到匹配的规则，图灵机就会按照规则进行更新。

演示：

giphy-(1)

giphy-(2)

如何停止： 会在程序表中有一个写特殊状态，例如：接受，拒绝。一旦发现内部状态处于接受或者拒绝，就会停止。

输出： 纸带上从头到尾的符号序列就是机器计算的最终结果。

作为结果的字符串： 如果图灵机被设计为计算一个函数（例如，将输入 X 转换为输出 Y），那么停止时纸带上留下的 Y 就是输出。
作为“是/否”的判定： 如果图灵机被设计为解决一个判定问题（判断一个输入是否具有某种属性），那么最终的输出就是（接受，拒绝）“是”** 或 “否”

为什么图灵机能有如此作用

本质上，图灵机就是图灵完美的定义了“计算”这个概念的具体表现。例如：我们把DNA完全拆解开来，知道了他的结构，他的组成，我们便掌握了遗传的底层规律，从而能够认识、活用，并一层层向外拓展，最终实现对生命性状等复杂概念的完全掌握和定义。

图灵将“计算”分解为读、写、移动、状态转换这四个原子级、机械化 的操作，提供了计算的普适标准： 任何遵循算法的思维过程，都能被这套符号系统所表达。

拓展讨论

1、非确定性图灵机

他与图灵机的区别就是，他的程序表中，一对确定的状态与符号能对应多条操作。非确定性图灵机定义了NP问题。

P vs NP 问题

非确定性图灵机的计算时间与确定性图灵机之间的关系是 P vs NP 问题的核心：
- P 类问题： 可以被确定性图灵机在多项式时间内解决的问题。
- NP 类问题： 可以被非确定性图灵机在多项式时间内解决的问题。
如果 P = NP，则意味着非确定性图灵机（即其隐含并行性）所能带来的时间加速，也可以被确定性图灵机有效地模拟，从而在计算能力上没有本质区别（至少在多项式时间复杂度内）。
如果 P $\neq$ NP，则意味着非确定性图灵机的“隐含并行性”在理论上具有确定性图灵机所无法达到的加速能力。
NP问题的核心：P = NP？

P vs NP 问题 可以被理解为：无限的隐含并行性 (NP) 是否能被有限的序列化计算 § 在多项式时间内高效模拟？

情景	含义	并行性视角
$P \neq NP$ (主流观点)	序列化计算是有限制的。	隐含的无限并行能力 ( $\text{NTM}$ ) 是本质上强大的。你不能用一台 DTM 在多项式时间内模拟 NTM 的所有并行探索。如果你想要解决 NP-Complete 问题，你仍然需要指数级的时间来按顺序检查所有分支。
$P = NP$	序列化计算的能力被低估了。	隐含并行性带来的加速可以被消除。这意味着对于任何 NP 问题，虽然 NTM 似乎需要并行搜索所有指数级的分支，但实际上存在一个 DTM 算法，它聪明地找到了一个捷径，无需并行搜索就能在多项式时间内直接确定解。
结论	P 就像一个单独的，非常快速的核心。NP 就像一个拥有无限并行核心的机器。 $\mathbf{P=NP}$ 意味着那个单独的核心本身就拥有无限并行机器的效率（即，“猜”的过程可以被高效的算法所取代）。

2、量子图灵机

QTM 与经典图灵机的根本区别

特性	经典图灵机 (DTM)	量子图灵机 (QTM)
信息存储	比特 (Bit)：状态只能是确定的 0 或 1。	量子比特 (Qubit)：状态是0，1叠加态
计算路径	单一路径：每一步都是确定的。	叠加态并行：同时探索所有可能的计算路径。
状态转换	确定性规则（写入 0 或 1）。	酉变换 (Unitary Transformation)：由可逆的量子门定义。
输出	确定性：运行结束后就是最终答案。	概率性：测量时，叠加态坍缩到某个确定的答案，结果具有一定概率。

叠加态并行：因为量子处于叠加态，我们对一组量子进行运算操作，实际上就是对这一组量子的所有排列组合都进行了操作。

酉变换：起的是程序表的作用，将旧的概率振幅转换成新的概率振幅。这个概率振幅类似于权重，我们可以把他当作处于一个状态（内部状态 q,纸带所有内容 B,读写头精确位置 i）的可能性，每一个特定的、完整的瞬时描述都有一个概率振幅，假设有10的6次个状态，就有10的6次个概率振幅与之对应，所有的概率振幅的平方和为1。

停止：将接受的概率振幅推到最大，拒绝的概率振幅推到最小，但是实际上这只是一个过程，不会有明确的停止，停止这个概念只发生在观测的一瞬间。量子坍塌后，会通过输出寄存器来得到结果。

输出：由于量子计算的设计目标是让正确答案对应的概率振幅最大，所以机器在测量时会以极高概率输出正确答案。但理论上，总是存在极小的概率输出错误答案。

推荐读物：
图灵机：计算机世界的理论基石 - 知乎

动画通俗解释-为什么图灵停机问题计算机永远无法解答？_哔哩哔哩_bilibili

什么是图灵机_哔哩哔哩_bilibili