图灵机：计算理论的奠基模型
1936 年，英国数学家艾伦·图灵用一个"纸带+规则表"的抽象模型，第一次精确回答了"什么是计算"
1.1 图灵机的基本概念
图灵机是艾伦·图灵（Alan Turing）在 1936 年提出的抽象计算模型。它不是一台真实的机器，而是一个"思想实验"，由四个核心组件构成：
- 无限长的磁带（Tape）：被划分为均匀的格子，每格可写一个符号（来自有限字母表，如 {0, 1, 空格}），理论上无限延伸；
- 读写头（Head）：可在磁带上左右移动，读取/写入当前格子的符号；
- 状态寄存器（State Register）：记录机器当前状态，状态来自有限状态集合，其中包含一个特殊的停机状态；
- 控制规则（转移函数 δ）：根据当前状态和读到的符号，决定"写什么、往哪移、进什么状态"。
形式化表示：δ(当前状态, 读取符号) → (新符号, 移动方向, 新状态)
一句话总结：图灵机用"无限磁带 + 读写头 + 状态寄存器 + 规则表"四个最小部件，把"计算"定义成最朴素的符号改写过程。
- 提出者与时间：艾伦·图灵，1936 年；意义在于第一次给出"计算"的严格数学定义。
- 四大组件：磁带（存储）、读写头（操作）、状态寄存器（记忆）、转移函数（规则）。
- 符号来自有限字母表；状态是有限集合，含一个停机状态。
- 转移函数 δ 决定每一步：写什么符号、向哪个方向移动、进入哪个新状态。
课堂练习 · 1.1
1.2 图灵机的运行原理
图灵机的计算过程是一个循环，分为三个阶段：
① 初始化
- 输入字符串写在磁带上，其余格子为空白符号（用 _ 或 B 表示）；
- 读写头指向最左边的输入符号；
- 状态寄存器设为初始状态 q₀。
② 计算步骤（每一步）
- 读取当前格子符号 → 2. 查规则表 → 3. 写入新符号 → 4. 移动读写头（L 左移 / R 右移 / N 不动）→ 5. 转移新状态 → 6. 重复
③ 终止条件
- 达到停机状态 → 接受输入；
- 进入无限循环 → 拒绝输入；
- 无适用转移规则 → 拒绝输入。
一句话总结：图灵机的运行就是"读符号 → 查规则 → 写符号 → 移头 → 换状态"的循环，最终停机接受、循环或卡住即拒绝。
- 初始化：输入写入磁带，读写头指向最左输入符号，状态置为 q₀。
- 每步五件事：读、查、写、移、换；移动方向只有 L / R / N 三种。
- 三种结局：停机=接受；无限循环=拒绝；无规则可查=拒绝。
课堂练习 · 1.2
1.3 任务：判断二进制串是否为"回文"
回文：正读反读都一样，如 101。为它设计一台图灵机，只需一条朴素策略：
- 检查两端：比较最左端与最右端的符号是否相同；
- 标记/擦除：相同则把两端字符擦除（写入 _）；
- 递归收缩：重复上述过程向中间收缩；
- 决策：所有配对成功且中间只剩 _ → 接受；任何一步不匹配 → 拒绝。
状态集分工：q_start 起始q_next_0/1 首字符为0/1向右q_pre_0/1 向左回退q_check_0/1 核对右端q_back_to_start 回到左端q_accept / q_reject
图灵机运行步骤演示 · 输入 "101"（点击步进按钮逐步观察）
完整转移函数（δ）速查表
| 当前状态 | 读到 | 写入 | 移动 | 下一状态 | 说明 |
|---|---|---|---|---|---|
| q_start | 0 | 0 | R | q_next_0 | 标记左端为0，向右寻找右端 |
| q_start | 1 | 1 | R | q_next_1 | 标记左端为1，向右寻找右端 |
| q_start | _ | _ | - | q_accept | 所有符号已处理完，接受！ |
| q_next_0 | 0 / 1 | 不变 | R | q_next_0 | 首字符为0，继续向右扫过中间符号 |
| q_next_0 | _ | _ | L | q_check_0 | 遇到右端空白，左移一格去核对 |
| q_next_1 | 0 / 1 | 不变 | R | q_next_1 | 首字符为1，继续向右扫过中间符号 |
| q_next_1 | _ | _ | L | q_check_1 | 遇到右端空白，左移一格去核对 |
| q_check_0 | 0 | _ | L | q_pre_0 | 右端是0，匹配成功，擦除 |
| q_check_0 | 1 | 1 | - | q_reject | 右端是1，与左端0不匹配，拒绝！ |
| q_check_1 | 1 | _ | L | q_pre_1 | 右端是1，匹配成功，擦除 |
| q_check_1 | 0 | 0 | - | q_reject | 右端是0，与左端1不匹配，拒绝！ |
| q_pre_0 / q_pre_1 | 0 / 1 | 不变 | L | q_pre_0 / q_pre_1 | 向左退回磁带头，跳过中间符号 |
| q_pre_0 / q_pre_1 | _ | _ | R | q_back_to_start | 已到磁带最左端，右移进入下一轮 |
| q_back_to_start | 0 / 1 | _ | R | q_start | 擦除已配对的左端符号，开启下一轮 |
| q_back_to_start | _ | _ | - | q_start | 回到最左端标记处，开始下一轮 |
一句话总结：通过"两端比较、逐对擦除、向中间收缩"的状态设计，图灵机用最朴素的规则精确完成了回文判定——计算即"基于规则的符号操作"。
- 回文判定策略：检查两端 → 擦除配对 → 递归收缩 → 接受/拒绝。
- 状态设计本质上是"记住了左端第一个字符"，再回头核对右端。
- 输入 101 经 15 步进入 q_accept；非回文（如 10）会进入 q_reject。
- 任何现代程序本质上都能分解为这样一系列最基本的符号操作。
课堂练习 · 1.3
1.4 图灵机的理论意义
1.4.1 计算通用性：界定"可计算"的探索之旅
20 世纪 30 年代，几位数学家从完全不同的角度独立提出了计算的形式模型，后来被证明能力相同：
一个系统若能模拟通用图灵机，就能理论上解决任何可计算问题。现代通用编程语言（C++、Python、Java…）都是图灵完备的。
条件分支（if）、无限存储（理论上）、数据读写修改能力。
它同时揭示了不可计算的存在——例如停机问题。
一句话总结：多种计算模型殊途同归，证明"可计算性"是客观的、不依赖具体模型的，丘奇-图灵论题则断言了计算的终极边界。
- λ演算、图灵机、递归函数形式不同，计算能力完全等价。
- 丘奇-图灵论题：任何算法可计算的函数都能被图灵机计算（论题，非定理）。
- 图灵完备 = 能模拟通用图灵机 = 可解决一切可计算问题。
- 注意：量子计算机在可计算性上也与图灵机等价，只是速度可能指数级更快。
1.4.2 计算复杂性基础：问题的"命运之问"
对一个问题，计算机科学会依次问三个问题：
核心概念
- 可计算问题：存在一台图灵机能解决它的所有实例；不可计算问题则反之。
- 可判定 vs 不可判定：是否存在图灵机对每个实例都能在有限步内给出"是/否"答案。经典不可判定问题：停机问题（判断任意程序在给定输入下是否停止）——图灵用自指技巧证明无解。
- P 类：能在多项式时间内解决的问题（O(n)、O(n²)…），视为"易解"。
- NP 类：解能在多项式时间内被验证的问题。注意 NP 不是"非P"，而是 Non-deterministic Polynomial（非确定性多项式）。
- P vs NP：是否所有易验证的问题也易求解？学界主流认为 P ≠ NP。
一句话总结：可计算性理论划出"能否解决"的边界，复杂性理论度量"解决的代价"，P vs NP 则追问"验证易、求解难"是否本质。
- 图灵机是衡量可计算性的"黄金尺子"，并区分可判定与不可判定。
- 停机问题是最著名的不可判定问题。
- P：多项式时间可解；NP：多项式时间可验证；P ⊆ NP。
- P vs NP 未解；若 P=NP，密码学、优化等领域将天翻地覆。
1.4.3 现代计算机的理论原型
现代计算机普遍遵循冯·诺依曼架构，其核心思想与图灵机惊人地一致——组件一一对应：
| 图灵机（抽象模型） | 现代计算机（物理实现） | 说明 |
|---|---|---|
| 无限长的纸带 | 内存（RAM + 硬盘） | 纸带格子 = 内存地址；理论上内存可不断扩展。 |
| 读写头 | 中央处理器 CPU | 从内存读指令和数据、处理、写回。 |
| 状态寄存器 | CPU 寄存器 / 状态标志（PSW） | 记录中间结果与运算状态。 |
| 规则表（转移函数） | 存储在内存中的程序 | "程序即数据"：CPU 从内存取指令来执行。 |
一句话总结：冯·诺依曼架构的"存储程序"思想，正是图灵机把"指令（规则表）与数据（纸带内容）同等对待"这一抽象思想的具体实现。
- 纸带 ↔ 内存；读写头 ↔ CPU；状态寄存器 ↔ 寄存器/PSW；规则表 ↔ 内存中的程序。
- 最深刻的一点：程序本身也是一种可被处理的数据。
- 这一映射说明所有通用计算机在理论上都是一台"物理化的图灵机"。
1.4 综合练习
1.5 图灵机的变体与扩展
对图灵机的各种修改，主要研究两个问题：① 计算能力（能否解决更多问题？）与 ② 计算效率（能否更快/更省？）。结论：所有变体计算能力等价，只影响效率。
多带图灵机
拥有多条独立纸带、各带读写头，但只有一个状态控制器。更贴近现代计算机的建模（输入带、输出带、工作带分离）。关键结论：任何多带图灵机都能被单带图灵机模拟——能力不变；但模拟有代价：k 带机 T(n) 步完成的任务，单带机可能需 O(T²(n)) 步（多项式级加速，无指数级加速）。
非确定性图灵机（NTM）
同一（状态, 符号）允许多个可选操作，机器可同时探索所有计算路径（"猜中"正确路径 / 并行宇宙）。它是定义 NP 问题类的理论基础。关键结论：NTM 可被确定型图灵机模拟——能力不变；但模拟代价可能是指数级的 O(2^T(n))，这正是 P vs NP 的核心。
通用图灵机（UTM）
输入由"另一台机器 M 的规则表编码 + 交给 M 的数据"两部分组成，UTM 模拟 M 的运行。它实现"程序即数据"，是所有存储程序计算机（冯·诺依曼架构）的科学定义——你的手机和电脑，理论上都是一台物理实现的通用图灵机。
一句话总结：多带、非确定性、通用等变体都在"不改变可计算边界"的前提下揭示了效率与通用性的奥秘，其中通用图灵机直接预言了现代软件的本质。
- 多带图灵机：加硬件换效率（多项式加速），能力不变。
- 非确定性图灵机：加"猜"的能力，模拟代价指数级，是理解 P vs NP 的钥匙。
- 通用图灵机：程序即数据，一台机器万能用途，通用计算机的理论基石。
- 三者的计算能力全部与原始图灵机等价，强化了丘奇-图灵论题。
