图灵机

概述

图灵机是由阿兰·图灵于 1936 年定义的抽象计算模型，通过模拟人类计算员的最简行为（读符号、写符号、移动、改变状态）来精确刻画"计算"的数学本质，是计算机科学的理论基石。

图灵机由四个部件组成：

部件	描述
纸带（Tape）	无限长的格子纸，每格写一个符号或为空白
读写头（Head）	指向当前格，可读/写符号
状态控制器	处于有限种状态之一（起始态 + 可能的停机态）
转移函数	δ: Q × Γ → Q × Γ × {L, R}，决定"给定状态和符号，写什么、往哪走、转哪个状态"

极简性的意义：这是迄今为止对"机械计算"最简单的形式化。正是因为极简，才能用来证明"不可能"——如果连这么简单的机器都无法完成某件事，任何更复杂的机器也无法完成。

Turing 的核心论证路径： 1. 分析人类计算员的实际行为（任意时刻只看有限符号、记忆有限、每步只做有限操作、完全确定性） 2. 将这些限制抽象为最小模型（纸带 + 读写头 + 有限状态 + 转移表） 3. 论证：任何"按固定规则进行的机械计算"都能被这台机器模拟

说服力来源：定义不是凭空构造，而是来自对计算行为的忠实分析——接受这个定义的代价等于接受"按规则做计算"就是这么一回事。

论文最具预见性的构造：存在一台特殊图灵机 U，能模拟任意图灵机：

纸带格式: [图灵机M的描述编码] [M的输入数据]
行为: U 读取M的描述，逐步"解释执行"M

历史意义：通用图灵机在1936年就在纸面上描述了"可编程计算机"——固定硬件 + 可变程序。比 ENIAC（1946年）早10年，比 von Neumann 存储程序架构（1945年）早9年。今天你手机里安装 App 的行为，就是在给一台通用图灵机加载"纸带描述"。

Turing 证明了： - 可计算数（存在图灵机能逐位输出其小数展开）是可数的（图灵机描述可枚举） - 实数是不可数的（Cantor 对角线） - ∴ 绝大多数实数是不可计算的——日常遇到的 π、e、√2 全是可计算的，但在"数学意义上"它们只占实数的极微小比例

图灵机使得精确讨论"某问题能否被算法解决"成为可能。停机问题证明了图灵机有根本性的能力边界（见该页面）。