计算模型：从有限自动机到图灵机

在造出计算机之前，数学家先要回答：**什么是"计算"？什么问题是可计算的？**答案由一族能力递增的理想机器给出：有限自动机、下推自动机、图灵机，分别对应正则、上下文无关、递归可枚举三类语言。本章给出每一级模型的直觉与例子，为第十卷的严格讨论做铺垫。

计算模型的层级

模型	等价语言	核心装置	能做什么的例子
有限自动机（FA）	正则语言	有限状态 + 无存储	正则表达式匹配、词法分析
下推自动机（PDA）	上下文无关语言	有限状态 + 一个栈	括号配对、语法解析
图灵机（TM）	递归可枚举语言	有限状态 + 无限纸带	一切现代计算机能做的事

层级之间的差别只有一个变量：存储。有限自动机没有存储，于是数不清"左括号是否比右括号多"；下推自动机有一个栈，能配对括号却数不清两个不相邻的计数；图灵机有可随机读写的无限纸带，于是与一切现代计算机等价（忽略资源限制）。

有限自动机：没有记忆的机器

确定性有限自动机（DFA）由状态集、转移函数、初始与接受状态组成，逐字符读入输入，按状态转移，结束时由所在状态决定接受与否。它能识别"所有含偶数个 1 的串"这类问题，却识别不了 $a^n b^n$（$n$ 个 a 后跟 $n$ 个 b）——要记住见过多少个 a，需要的状态数无界，而 FA 只有有限个状态。

这个"数不清"有精确表述：正则表达式不能匹配括号配对，因为有限自动机没有栈。推论是工程上熟悉的——嵌套结构（JSON、XML、代码块）不能只用正则表达式解析（→ 有限自动机与正则语言）。

非确定性自动机（NFA）看起来更强——允许同时处于多个状态——但与 DFA 等价（子集构造），只是状态数可能指数爆炸。

下推自动机：加一个栈

给 FA 加一个栈，就得到下推自动机，能力恰好覆盖上下文无关语言——也就是大多数编程语法的层次。栈的"只进不出上端"恰好匹配嵌套结构：读到 ( 压栈，读到 ) 弹栈，弹不出去或不空即失败。语法分析（→ 语法与语义）就是在这个模型上工程化的。

但 PDA 仍数不清 $a^n b^n c^n$——需要同时记住两个计数，一个栈只能先弹后进的。

图灵机：能力的上界

给自动机换成可随机读写的无限纸带，就得到图灵机：读写头左右移动、改写符号，直到（可能永不）停机。三条关键事实：

1. Church–Turing 论题：一切"有效可计算"的函数都能被图灵机计算。这是论题而非定理——"有效可计算"是直觉概念，无法形式化证明；但八十年间所有候选计算模型（λ 演算、寄存器机器、 Cellular automata、现代编程语言）都被证明与图灵机等价。
2. 通用图灵机：存在一台图灵机 $U$，能模拟任何给定的图灵机——这正是"程序是数据"的数学表述，操作系统与编译器之所以可能，根在这一步。λ 演算与图灵机等价，是函数式语言的根（→ 编程范式）。
3. 不可判定性：有些良定义的问题没有算法，停机问题是原型（→ 图灵机、可计算性与停机问题）。

因此图灵机是所有现代计算机的能力上界：不可能写出比图灵机"更能算"的程序，只能在速度与资源上做文章——后者正是复杂度理论（→ 复杂度类全景）的主题。

为什么是"论题"而非定理

Church–Turing 论题断言"直觉上的可计算 = 图灵机可计算"。由于"直觉上的可计算"不是数学对象，这个断言无法被证明，只能被反复确证：每个被认真提出过的计算模型最终都与图灵机等价。这与物理定律的地位类似——是被证据支持的最佳形式化，而非逻辑必然。

本章要点

• 计算模型的层级由存储决定：无存储 → 正则，一个栈 → 上下文无关，无限纸带 → 图灵机
• 正则表达式不能匹配括号配对，因为有限自动机没有栈
• 图灵机是所有现代计算机的能力上界（忽略资源）；通用图灵机即"程序是数据"
• Church–Turing 论题是论题而非定理，靠反复确证而非证明

相关阅读

严格定义与证明见有限自动机与正则语言与图灵机、可计算性与停机问题。