艾伦·图灵提出的理论计算模型，定义了“可计算”的概念，是现代计算机科学的理论基础。 它只有一条纸带、一个读写头和一个有限状态寄存器，却能刻画一切“算法可解”的过程。
🧮 形式定义：七元组
标准单带确定型图灵机通常定义为一个七元组，其中每一项都对应机器运行时不可缺少的一部分：
它的核心是转移函数。给定当前状态和读写头看到的纸带符号，机器必须唯一地决定写入什么符号、 读写头如何移动、以及进入哪个新状态：
这里的 $\rightharpoonup$ 表示“部分函数”：如果某个 $(q,a)$ 没有定义转移，机器就在该配置上停机。 $L$ 表示左移，$R$ 表示右移，$N$ 表示不移动（有些教材写作 $S$ 或 $-$）。
🔁 运行语义：配置与单步转移
在任意一瞬间，机器的完整“快照”称为配置（也称瞬时描述）， 它把纸带内容、读写头位置和当前状态三者打包在一起。通常写成下面的形式， 其中 $u,v\in\Gamma^{*}$，$a\in\Gamma$：
一步计算就是把一个配置改写成下一个配置，记作 $\vdash$。按移动方向分两种情况：
若 $u$ 为空（读写头已在最左端），左移时会在左侧自动补出一个空白符 $B$，这正是“纸带无限长”的含义。 反复应用 $\vdash$ 直到机器停机，就得到一次完整计算：$q_0 w \vdash^{*} u\,q_f\,a\,v$，其中 $q_f\in F$。
🌐 计算能力：通用性与边界
图灵机最深刻的一点是：机器本身可以被编码成纸带上的字符串 $\langle M\rangle$， 于是可以造出一台通用图灵机 $U$，它读取任意机器描述和输入，然后忠实地模拟那台机器：
这正是“硬件与软件分离”与“存储程序”的思想源头。而与之相对的，是计算能力的硬边界—— 停机问题：
图灵用对角线法证明了 $H$ 是不可判定的：不存在一台图灵机能在有限步内对所有输入正确回答“会不会停”。 这条边界至今没有被突破，也是“丘奇—图灵论题”的重要佐证。
📖 标准介绍
图灵机是英国数学家艾伦·图灵（Alan Turing）于 1936 年提出的抽象计算模型， 旨在精确定义“计算”的边界。它由一条无限长的纸带、一个读写头和一个状态寄存器组成。
核心组件：
- 纸带：一条无限长的纸带，被划分为连续的小方格。每个方格可以记录一个来自有限字母表的符号（例如 0、1，以及一个特殊的“空白”符号 B）。纸带的无限长提供了理论上无上限的存储空间。
- 读写头：一次对准一个方格，能执行三种基本操作：读取当前方格中的符号、写入一个新符号（覆盖原有符号，包括擦除为空白）、左移或右移一格到相邻方格。
- 状态寄存器：记录机器当前的“状态”，来自一个有限的状态集合。其中包含一个特殊的起始状态（机器开始运行时的状态）和一个或多个停机状态（进入后机器立即停止运行）。
- 转移规则（程序）：一个有限的规则表，每条规则的格式为：(当前状态, 当前读到的符号) → (要写入的符号, 移动方向, 下一个状态)。
机器运行时，每一步都根据当前状态和读写头所指的符号查找规则，然后执行“写入 → 移动 → 更新状态”。 如果某一步进入停机状态，或找不到匹配的规则，机器便停止，此时纸带上的内容即为计算结果。
更严格地说，单带确定型图灵机可写成七元组： $M=\langle Q,\Sigma,\Gamma,\delta,q_0,B,F\rangle$。 下面的模拟器按这个数学定义执行，而不是只播放固定动画。
需要注意的三个细节： ① 图灵机的“程序”是有限的，而纸带是无限的，因此它能表示的数据量没有上界； ② 转移函数必须是确定型的——同一 $(q,a)$ 不允许出现两条不同的规则； ③ 因为字母表和状态集都是有限集，所有图灵机可以被系统地枚举出来（可数无限多）， 这一点是停机问题不可判定性证明的技术基础。
💬 通俗介绍
想象一个人拿着笔和橡皮，在一条无限长的纸带上工作。他按照一本规则手册，根据当前看到的符号和自己的“心情”（状态）， 决定写什么、往哪走、下一个“心情”是什么。这就是图灵机！
图灵机本质上是一个抽象的计算模型，你可以把它想象成一个人拿着笔和橡皮，在一条被划分为无数小格子、向两端无限延伸的纸带上工作。 这个人的“当前心情”代表机器的有限内部状态，而他手中的笔则充当读写头，一次只能聚焦于纸带上的一个格子。 他必须严格遵守一本固定的“规则手册”（即转移函数），根据当前所处的“心情”和眼前格子里的符号，机械地执行三个动作： 擦除旧符号并写下新符号、将注意力向左或向右移动一格，以及切换到下一个“心情”。 他就这样不断重复“看、写、移、换心情”的简单循环，直到触发手册中的停止条件。 正是这种将复杂计算拆解为最基本机械动作的机制，用最简单的组件刻画了所有可计算过程的边界，从而奠定了现代计算机的理论基础。
一个类比：如果把图灵机想成一名只会照章办事的记账员，那么“纸带”就是账本， “规则手册”就是程序，“心情”就是程序计数器。记账员虽然不会独立思考， 但只要规则手册写得足够详细，他就能完成任何可以用明确步骤描述的工作——哪怕这工作是计算一颗行星的轨道。
🕰️ 历史沿革
图灵机不是凭空出现的玩具，它诞生于 20 世纪数学基础大讨论的漩涡中心—— 希尔伯特提出的“判定问题”（Entscheidungsproblem）：是否存在一种机械方法，能判定任意数学命题的真假？
图灵发表《论可计算数及其在判定问题上的应用》，提出“a-machine”（自动机，后被称为图灵机）与通用图灵机，并用对角线法证明停机问题不可判定，从而给出判定问题的否定答案。
丘奇（Alonzo Church）提出 λ 演算，证明 λ 可定义性与一般递归函数等价，独立地给出了判定问题的否定答案。两种模型殊途同归，成为“丘奇—图灵论题”的雏形。
图灵在普林斯顿发表续文，证明图灵机与 λ 演算、递归函数彼此等价，说明“可计算”这一概念不依赖于具体模型的选择，具有稳健性。
波斯特（Emil Post）独立提出 Post 机，与图灵机等价；他后来研究的“波斯特对应问题”成为另一个经典的不可判定问题。
冯·诺依曼在 EDVAC 报告中提出存储程序式计算机架构。通用图灵机“把程序当作数据”的思想，成为现代计算机体系结构的理论先声。
图灵发表《计算机器与智能》，提出著名的“图灵测试”，把“机器能否思考”这一问题转化为可操作的行为判别问题。
赖斯（Henry Rice）证明赖斯定理：图灵机的一切非平凡语义性质都是不可判定的，把停机问题推广成一大类不可判定问题。
Hartmanis 与 Stearns 提出时间/空间复杂度层级定理，图灵机从“能不能算”的标尺变成“算得多快”的度量工具，复杂性理论由此起步。
Cook 与 Karp 建立 NP 完全性理论，P 与 NP 是否相等成为计算机科学最核心的未解问题，而问题的标准表述正是建立在（非确定型）图灵机之上。
“图灵完备”成为衡量一门编程语言或一个计算系统表达能力的常用说法；从 λ 演算到元胞自动机，人们不断发现与图灵机等价的计算模型。
💬 图灵机解决了什么问题？
1. 给出了“计算”的精确数学定义。它将模糊的“算法”概念彻底机械化，证明任何有明确步骤的问题都可被图灵机计算，奠定了计算机科学的基础。
2. 提出了“通用图灵机”。一台机器通过读取不同的“规则手册”（即软件），就能模拟任何其他图灵机。这是“硬件与软件分离”的思想源头，也是冯·诺依曼架构的先声。
3. 划定了“可计算”的理论边界。图灵机证明了“停机问题”不可判定——不存在通用算法能预判任意程序是否会死循环。这打破了用机械方法解决所有数学问题的幻想，也引出了“丘奇—图灵论题”：任何直觉上可计算的东西，图灵机都能算（迄今未被推翻）。
4. 提供了度量复杂性的统一标尺。时间复杂度 $O(t(n))$、空间复杂度 $O(s(n))$ 都以图灵机的步数与纸带格数为定义基准，P、NP、PSPACE 等复杂性类由此有了严格含义。
🧱 可计算性的三层边界
图灵机让我们第一次能够对“问题”本身进行分类。按照是否存在能解决它的机器， 所有语言（问题的编码集合）被划分为三个层次：
| 类别 | 含义 | 典型例子 |
|---|---|---|
| 可判定（递归语言） | 存在图灵机，对任意输入都在有限步内停机并给出正确的“是/否” | $\{a^n b^n \mid n\ge 0\}$、素数判定、任何正则语言 |
| 可识别（递归可枚举） | 存在图灵机，输入属于该集合时会停机接受；不属于时可能永不停机 | 停机问题 $H$、所有定理的集合 |
| 不可识别 | 不存在任何图灵机能够枚举它 | $H$ 的补集 $\overline{H}$ |
注意三者的包含关系是严格的：可判定 $\subsetneq$ 可识别 $\subsetneq$ 全部语言。 而在可判定的世界里，还有另一层“实用边界”——复杂度：一个问题可能可判定，但需要天文数字般的资源， 以至于在现实中无法求解。
💬 图灵机的缺陷（理论局限）？
1. 无法解决“停机问题”。不存在一个通用的图灵机，能判断任意给定的程序和输入是否会在有限步内停止。赖斯定理进一步说明：任何非平凡的语义性质都不可判定。
2. 效率不现实。图灵机的“纸带”是顺序读写的，实际解决问题极慢（比如排序可能需要 $O(n^2)$ 步移动），不能直接代表现实计算机的“可行”计算（即时间/空间复杂度）。用单带图灵机模拟多带图灵机，时间开销会平方级放大。
3. 无限纸带只存在于理论。现实计算机内存有限，本质上是有限自动机，但通常用图灵机近似——只要实际使用不超过内存上限，这个近似就是准确的。
4. 不刻画并发、交互与实时性。图灵机描述的是一个“封闭系统”：输入一次性给出，计算过程不与外界交互。对于在线算法、并发系统、分布式协议等场景，需要交互式图灵机、π 演算等更强的模型来描述。
5. 无法刻画“超越计算”的假设。带有神谕（Oracle）的图灵机、无限精度实数计算、超计算模型等，都说明图灵机只是“可计算”的一种合理形式化，而不是物理学上的终极答案。
🧩 变体与等价模型
图灵机有很多“增强版”和“简化版”，令人惊讶的是，只要不做本质性的越界（例如允许无限步的判定）， 它们的计算能力完全相同——这被称为计算模型的“稳健性”。
图灵机自身的常见变体
与图灵机等价的其他模型
这些模型的等价性，正是“丘奇—图灵论题”最有力的经验支持： 无论用什么方式形式化“机械可计算”，得到的都是同一个集合。
🎮 标准单带确定型图灵机模拟器
这里不再是固定脚本动画，而是按转移函数逐步执行： 读当前格、写符号、移动读写头、进入下一状态。纸带使用整数坐标按需展开，向左和向右都视为无限。
机器定义
运行控制台
尚未执行
七元组视图
转移规则表
| 当前状态 | 读取 | 写入 | 移动 | 下一状态 |
|---|
执行日志
🧠 理论意义
定义了“可计算”的概念，证明了某些问题是不可计算的（停机问题）。
停机问题标准介绍：
停机问题旨在判断任意程序在特定输入下是否能在有限步内终止。图灵于 1936 年利用对角线法证明，不存在能对所有程序给出正确判定的通用算法。因为一旦假设存在，便会推导出逻辑上的自相矛盾。它作为不可判定问题的典型，划定了计算的绝对理论边界。
停机问题通俗解释：
假设有个“万能死循环检测器”。你可以写个“叛逆程序”专门对付它：若检测器预言它会停机，它就故意死循环；若预言它死循环，它就立刻停机。把叛逆程序输入检测器，它无论怎么回答都会被打脸。这证明了能预判一切程序的完美检测器在逻辑上根本不存在。
💻 实践影响
现代计算机的理论基础，所有编程语言的计算能力都等价于图灵机。
存储程序式架构、解释器与虚拟机（如 JVM）、编译器自举、乃至“用代码生成代码”的元编程技术，都是通用图灵机思想的工程化体现。
同时，停机问题的不可判定性也给工程实践划出了红线：不存在能完美检测所有死循环、内存泄漏或程序正确性的通用工具。现实中的静态分析器之所以有效，是因为它们主动放弃了“对所有程序都准确”这一目标。
🎯 Church-Turing 论题
任何可以被算法解决的问题，都可以被图灵机解决。
它把“直觉上的可计算”与“图灵可计算”这两个概念等同起来。严格来说，这是一个关于“算法”这一非形式概念的论题，而不是可证明的定理；但它得到了迄今为止所有计算模型的强力支持。
它的加强版——物理丘奇—图灵论题——更进一步断言：任何物理上可实现的计算机，都无法超越图灵机的计算能力。这一断言目前仍然是量子计算、光学计算等领域研究的开放问题。