4.1 图灵机、可识别与可判定：给算法能力画一条边界

前三章从有限自动机走到下推自动机，存储能力不断增强。若再给机器一条可读写、可无限扩展的纸带，它能表达怎样的通用计算？更重要的是，即使采用图灵机这样的通用模型，为什么仍不存在一个算法可以判定所有程序与输入的行为？

本课目标

• 描述单带确定性图灵机的组成和一步计算；
• 区分接受、拒绝与不停机；
• 区分图灵可识别语言和可判定语言；
• 理解通用机与 Church–Turing 论题的地位。

1. 一个常见的七元组定义

确定性单带图灵机可写成：

$$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{accept},q_{reject}).$$

• $Q$：有限状态集合；
• $\mathrm{\Sigma }$：输入字母表，不含空白符；
• $\mathrm{\Gamma }$：磁带字母表，包含 $\mathrm{\Sigma }$ 和空白符；
• $\delta$：转移函数；
• $q_0$：起始状态；
• $q_{accept}$、$q_{reject}$：互不相同的停机状态。

对非停机状态，一种定义是：

$$\delta :(Q\setminus \{q_{accept},q_{reject}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}.$$

每一步读取当前格，写入一个符号，向左或右移动一格，再改变控制状态。有些教材允许读写头保持不动，或使用单向无限磁带；这些变体经过适当编码后不会改变可计算能力。

2. 配置描述一次完整快照

只知道控制状态不够，还要知道磁带内容和读写头位置。三者合起来称为配置。一次转移把一个配置变成下一个配置：

当前状态 + 读写头所在格 + 当前有限的非空白磁带内容
                         ↓ δ
下一状态 + 写入后的磁带 + 移动后的读写头

对有限输入，磁带其余位置初始为空白。每个有限时刻只访问有限格；若计算永不停止，访问范围可以持续增长，不存在事先统一的有限上界。理论上的无界磁带不等于瞬间拿到无限内存。

3. 一个回文判定过程

要判定二进制串是否为回文，可以设计高层步骤：

1. 若已没有未标记字符，接受；否则找到最左侧字符，记住它并做标记；
2. 若此时没有别的未标记字符，接受（刚处理的是奇数长度的中心）；否则向右移到最右侧未标记字符；
3. 比较二者，不同则拒绝，相同则标记右侧字符；
4. 返回左侧，重复；
5. 若没有未匹配字符，接受。

空串和单字符串都接受；例如 010 先消去两端的 0，再接受剩下的中心 1，011 则在第一次比较时拒绝。有限控制只需记住“本轮左端是 0 还是 1”，磁带保存已处理位置。这个算法可能反复扫描，时间并不高效，但它会对每个有限输入停机并给出正确答案，所以是判定器。

图灵机理论主要研究可计算性时，不要求模型直接成为生产实现。多带图灵机、标准随机访问机，以及不预设有限资源上限的图灵完备语言，在合理编码下计算同一类可计算函数，但复杂度换算仍需单独分析。

4. 接受、拒绝和不停机是三种结果

对输入 $w$，图灵机可能：

• 进入 $q_{accept}$；
• 进入 $q_{reject}$；
• 永远继续运行。

若机器在且仅在 $w\in L$ 时最终接受，就说它识别 $L$。对 $w\notin L$，识别器可以拒绝，也可以不停机。

若机器对每个输入都停机，并且成员输入接受、非成员输入拒绝，就说它判定 $L$。

因此：

$$\text{可判定语言}⊊\text{图灵可识别语言}.$$

可判定语言也叫递归语言；图灵可识别语言也常叫递归可枚举语言。不同术语体系容易混淆，阅读资料时要先对齐定义。

5. 枚举器与识别器

枚举器可随计算逐个输出字符串。它只能输出 $L$ 的成员，且每个成员都必须在某个有限时刻出现，才算枚举 $L$；顺序和重复通常不重要。若 $L$ 无限，并不存在“最后全部列完”的时刻。

一个语言可被图灵机识别，当且仅当它可被某个枚举器枚举。直觉上：

• 从识别器到枚举器：按交错调度模拟所有输入，输出已接受者；
• 从枚举器到识别器：不断运行枚举器，看到目标输入时接受。

例如第 $t$ 轮，让前 $t$ 个输入的模拟各前进一步。这样每个已启动的模拟都会不断得到机会，而任何一轮的工作仍有限。交错调度很重要。若逐个输入串行运行，可能卡在第一个不停机的模拟上，后续成员永远得不到机会。

6. 通用图灵机

程序和输入都可以编码成字符串。通用图灵机 $U$ 接收 $⟨M,w⟩$，模拟机器 $M$ 在 $w$ 上的执行。这把“机器”也变成数据，是解释器、虚拟机和存储程序计算机背后的理论原型。

通用性不表示所有问题都可解决。它表示一台固定机器能模拟任意有效编码的图灵机；下一课会证明，关于这些机器自身行为的某些问题无法被任何判定器解决。

7. Church–Turing 论题不是普通定理

Church–Turing 论题主张：任何直观意义上“有效可计算”的函数，都可由图灵机计算。它连接一个非形式化概念与数学模型，因此不能像同一形式系统内的命题那样直接证明。

支持它的证据来自许多独立提出的计算模型，λ 演算、递归函数、寄存器机等，最终得到相同的可计算函数类。它不声称图灵机是最高效的模型，也不限制物理机器的具体架构。

常见误区

• 识别器总会输出 yes/no：非成员输入上可能永不停止。
• 无限磁带意味着一次计算使用无限空间：每个停机计算只访问有限格。
• 通用机能解决所有输入问题：它能模拟程序，不代表能判定程序的一切性质。
• Church–Turing 论题证明了现实世界没有别的物理计算：它是关于有效可计算性的论题，不是具体物理定律的完整证明。

练习

1. 说明 DFA 为什么总是判定器，而一般图灵机识别器未必是。
2. 为语言 $\{0^n{1}^n\mid n\ge 0\}$ 写图灵机级别的高层判定步骤。
3. 解释枚举器构造中为什么需要交错模拟。
4. 比较 PDA 栈和图灵机磁带在可访问位置上的差别。

小结

图灵机把有限控制与可改写工作带结合起来，刻画通常意义上的算法能力。关键要看它对非成员输入会拒绝还是可能永不停止。一个识别器久久不回答，可能仍在按它的定义认真工作；调用方可不能因此把沉默当成 false。

下一课利用“程序也能作为输入”这一事实构造自指，证明停机问题不可判定，并学习归约方向怎样决定一项证明是否成立。