如果你让我用一句话总结《计算理论导论决策计算与语言》这门课带给我的改变那就是从今往后每当有人跟我说“这个需求写个算法就能搞定”我脑子里会先蹦出一个问题——这个问题可判定吗这门课的核心主线就是“决策计算”也就是判定问题给定一个实例程序能不能在有限的步数内回答“是”或者“否”。标题里的 Decision Computation 翻译成“决策计算”说的就是这个意思。这篇文章是系列的第二篇上一篇我们沿着正则语言的版图走了一圈梳理了有限自动机、正则表达式以及它们之间的联系。这一篇我们继续往上爬从正则语言的边界出发进入上下文无关语言和下推自动机再一路走到图灵机和可判定性理论。整条路线有一个很清晰的逻辑语言越来越复杂你需要的计算模型就必须拥有越来越强的记忆能力。正则语言只靠有限状态上下文无关语言需要一个栈到了图灵机则变成一条无限纸带。理解这条升级路线比记住任何一条定理都更有价值。1. 正则语言的边界为什么“有限状态”撑不住嵌套结构1.1 泵引理先把“正则”扳倒再谈升级在上一篇里DFA、NFA、正则表达式这三兄弟被证明是等价的能表达的语言范围完全一致。这套模型有一个天然短板状态数量是有限的而输入串可以无限长。你可以把 DFA 想象成一条只有几个房间的走廊走再长的路你也只能在这些房间之间来回穿梭不可能凭空“记住”无穷多的历史信息。泵引理Pumping Lemma就是把这种直觉变成一把精确的尺子。它的核心论断是如果一个语言 L 是正则的那么一定存在一个正整数 p使得任意长度超过 p 的字符串 s ∈ L都能被切成三段 s xyz满足三个条件|xy| ≤ p且 |y| ≥ 1并且对任意 i ≥ 0字符串 x y^i z 仍然属于 L。翻译成人话就是因为 DFA 只有有限个状态处理长度超过状态数的输入时必然会有一个状态被“重复访问”。这一段重复的路径就是 y你可以把这段路径循环任意多次DFA 根本察觉不到。这套工具最常见的用途是证明某个语言不是正则的比如语言 L { aⁿbⁿ | n ≥ 0 }。假设它是正则的取泵长度 p再取 s aᵖbᵖ。因为 |xy| ≤ p而 s 的前 p 个字符全是 a所以 y 必然完全落在 aᵖ 这一段里不妨设 y aᵏk ≥ 1。现在把 y 复制一遍得到 x y² z里面的 a 变成了 pk 个b 还是 p 个显然 a 的数量不等于 b 的数量这个字符串就不在 L 里矛盾。我第一次看完这个证明的感受是原来“证明一个语言不能用正则表达”不是靠直觉而是有一套机械化的操作流程。后来实际做开发看到不少人试图用正则表达式去解析嵌套的括号、HTML 标签、JSON然后写出一个三四屏的“正则怪物”我就知道他们一定没被泵引理教育过。遇到需要数数、需要配对的场景正则这一步就该停下了。1.2 上下文无关语言当嵌套结构出现的时候正则语言描述不了“嵌套”“配对”这类结构但现实世界里到处是嵌套。算术表达式里括号套括号前端代码里 div 套 span文本里引号里面还有转义引号。这些结构的共同点是什么需要一个“记忆”来记录当前嵌套到第几层、以及每一层分别是什么类型。形式语言理论把这些语言按表达能力分成了四级。最底层就是我们刚刚讨论的 3 型语言也就是正则语言往上是 2 型语言叫作上下文无关语言再往上是 1 型和 0 型。这个谱系不是人为划分的而是由每种语言对应的计算模型决定的正则语言对应有限自动机上下文无关语言对应下推自动机。举几个典型例子回文串的集合 { wwᴿ | w ∈ Σ* }它不是正则的但它是上下文无关的平衡括号串它也不是正则的但它也是上下文无关的。你在编译器课上背过的那些文法规则比如E - E T | T本质上就是在用“上下文无关文法CFG”来描述一种结构化的嵌套语言。所以到了这一步两个问题摆在面前第一上下文无关语言长什么样第二什么样的机器能识别它答案分别是“文法”和“下推自动机”。下面我们一个一个看。2. 下推自动机给自动机配一根无限长的草稿纸2.1 文法推导比背定义重要CFG 的读写直觉上下文无关文法的定义并不复杂它由四部分组成非终结符集合 V、终结符集合 Σ、产生式规则 R、以及一个开始符号 S。我们通常写 G (V, Σ, R, S)。每条产生式的左边是单个非终结符右边是一串由终结符和非终结符组成的符号。比如下面的文法S - a S b S - ε它描述的语言是什么从 S 出发可以一直套 a S b最后用 ε 收尾得到的串是 aⁿbⁿ。这个文法只有两条规则表达能力却超过了前面提到的所有正则模型。道理很简单非终结符可以被“递归地展开”而递归恰恰是嵌套结构的数学表达。光看定义没意思关键是要会“推”。推导的过程就是从开始符号出发不断把非终结符替换成产生式右边。还是上面的文法推一个 aabbS a S b a a S b b a a ε b b aabb每一步替换一个非终结符这就是最左推导。如果把推导过程画成一棵树每片叶子是终结符、每个内部节点是产生式的应用这样一棵语法树能把“结构”直观地呈现出来。这也是语法分析器的雏形。再举一个稍微现实的例子。描述算术表达式的文法如果写成E - E E | E * E | ( E ) | id会有一个老问题比如 id id * id既可以先算加法再算乘法也可以先算乘法再算加法一棵语法分析树就有两种这就是文法的二义性。解决二义性的常用手段是引入优先级分层E - E T | T T - T * F | F F - ( E ) | id这样一来乘法的优先级高于加法语法树就只有一棵了。理解这个例子比背诵“什么是二义性”有价值得多因为你在写表达式解析器的时候实际要解决的就是这种问题。2.2 手工设计一个 PDAaⁿbⁿ 的完整状态机下推自动机Pushdown Automaton, PDA说白了就是在 NFA 的基础上加一个栈。栈可以无限增长但每次只能访问栈顶。这个“无限”很关键它让自动机拥有了某种程度的记忆能力。形式化地看PDA 是一个六元组状态集合 Q、输入字母表 Σ、栈字母表 Γ、转移函数 δ、开始状态 q0、以及栈底符号 Z0。转移函数的输入是当前状态、读到的输入字符或 ε、栈顶符号输出是新状态、要压入的字符串。这里允许 ε 转移意味着机器可以在不消耗输入的情况下操作栈。直接用经典的例子设计一个 PDA 识别 L { aⁿbⁿ | n ≥ 0 }。思路是读到一个 a 就往栈里压一个 A读到一个 b 就从栈里弹出一个 A如果结束时栈恰好恢复到只剩栈底符号就说明 a 和 b 的数量相等。可以设计成这几个核心状态q0: 读 a压入 A连续读 a 就连续压 q0: 第一个 b 到来时弹出 A进入 q1 q1: 继续读 b每读一个 b 弹出 A q1: 输入结束且栈顶只剩 Z0进入接受态 q2当我们把状态写细致一点(q0, a, Z0) → (q0, A Z0) (q0, a, A) → (q0, A A) (q0, b, A) → (q1, ε) (q1, b, A) → (q1, ε) (q1, ε, Z0) → (q2, Z0)这里我把栈顶写在左边A Z0表示压入 A 后栈内从顶到底为 A、Z0。逐条解释一下第一条规则在 q0读入 a栈底是 Z0压入一个 A。第二条规则在 q0读入 a栈顶已经有一个 A再压入一个 A。第三条规则在 q0第一次读入 b弹出一个 A进入 q1。第四条规则在 q1继续读 b每读一个弹一个 A。第五条规则在 q1输入全部读完栈顶露出 Z0转移到接受状态 q2。拿输入 aabb 手工走一遍读 a压 A读 a再压 A此时栈里是 A A Z0读 b弹 A剩 A Z0读 b弹 A剩 Z0输入读完q1 看到栈顶 Z0进入 q2接受。如果输入是 aab走到最后剩 A Z0第五条规则不匹配机器卡住不接受。如果输入是 abb读第二个 b 时栈顶已经是 Z0没有可用的转移规则同样不接受。这里有一个细节值得单独说PDA 有两种接受方式一种是“进入接受状态就接受”叫终态接受另一种是“栈弹空就接受”叫空栈接受。教材里一般会证明这两种接受方式等价。工程上我们更熟悉的是“终态接受”因为写代码时你不会把“栈空”当作一个神奇的时刻而会显式地设一个返回 true 的分支。很多人觉得 PDA 太抽象其实你早就用过它了。手写的递归下降解析器、括号配对算法、HTML 标签匹配这些本质上都是一个带栈的自动机。遇到/div就弹出最近的开始标签遇到 start tag 就压栈配合一个有限状态判断当前上下文——这就是 PDA 在现实世界的分身。2.3 为什么 CFG 和 PDA 总能互相转换这一节的结论是一个语言是上下文无关的当且仅当存在某个 PDA 识别它。但比记住结论更重要的是理解两个转换方向的直觉。从 CFG 构造 PDA 的方向相对直观做法叫“自顶向下分析”。PDA 的栈里放的是“还没处理完的符号”读到一个非终结符就把它展开成产生式右边的串读到终结符就和输入匹配。这个过程模拟的正是刚才说的“推导”。这就是为什么现代语法分析器全是这一思路的工程化——解析器本质上是一个用代码实现的 PDA。从 PDA 构造 CFG 的方向复杂很多我当年啃这部分的证明啃了很久。它的核心想法是为每一对“栈符号状态”设计一个非终结符用它来表示“某个栈符号从状态 p 变到状态 q 的净效果”。这个构造过程很机械真要手推一遍工作量不小但对理解“机器行为等价于文法推导”非常有帮助。理解了这两个方向的转换你会得到一个很重要的工程直觉描述一类结构你可以用“文法”这种声明式的方式也可以用“栈机器”这种命令式的方式。两者可以互相翻译所以你写语法解析器的时候可以先设计文法再转成代码也可以直接手写状态和栈逻辑结果是等价的。3. 图灵机从一个“足够强”的模型到可计算性论题3.1 图灵机的形式化组成接受、拒绝与循环PDA 尽管有了无限栈仍然有不擅长的问题。比如语言 { aⁿbⁿcⁿ | n ≥ 0 }它需要同时记住 a、b、c 三者的数量关系一个栈只够记录一组配对不够同时记两组。这时候需要一种更通用的机器。图灵机的形式化定义是一个七元组(Q, Σ, Γ, δ, q0, q_accept, q_reject)。它比 PDA 多出来的核心部件是一条无限长的纸带、一个可以左右移动的读写头、以及一个“拒绝状态”。转移函数 δ 不再是“读一个字符、弹出栈顶、压入栈”而是“读一个格子、写一个字符、向左或向右移动一格”。三个状态的区分值得多说几句。之前讨论的 DFA 和 PDA要么串被读完后停在终态要么卡死在某个状态要么栈变了却没进终态。图灵机多了一个真正的第三态循环。它可能一直跑下去永不停止。这个“循环”不是理论上的边角料它是整个可判定性理论的题眼。来看一个简单的图灵机如何识别 aⁿbⁿcⁿ机器可以反复从左到右扫描把当前的第一个 a 标记为 X再向右找到第一个 b 标记为 Y再向右找到第一个 c 标记为 Z然后回到纸带左端重新开始。如果某次扫描找不到配对的 b 或 c就进入拒绝如果所有 a、b、c 都配完且没有多余字符就进入接受。这个过程用到了“多个来回扫描”的能力这远超 PDA 那种“从左到右一遍 栈”的模式。图灵机真正厉害的地方不是某一个具体机器设计得有多巧妙而是它提供了通用的计算模型。只要输入足够编码一个问题你就能设计一台图灵机来计算它而机器本身的行为完全由有限的状态和规则表控制。3.2 为什么编程语言和它等价以及“算法”的边界学到这里一个绕不开的问题就是为什么我们相信图灵机就是“算法”的边界而不是某个更强大、但是还没被发现的机器这就是可计算性论题通常也叫 Church-Turing thesis的内容任何在直觉上“可计算”的函数都可以被某台图灵机计算。这个论题没法被严格证明因为“直觉上可计算”不是一个形式化概念。但几十年来各种被提出来的计算模型——lambda 演算、递归函数、while 程序、寄存器机、随机访问机——全都被证明和图灵机等价没有任何反例。等价的意思不是这些模型长得像而是一个语言能被图灵机识别当且仅当它能被 lambda 演算表达当且仅当它能被现代编程语言写出的算法解决。换句话说你用 Python、Java、C 能写出的算法边界和图灵机能解决的边界完全一致。区别只在时间、空间这些资源指标上。我自己从工程角度理解的图灵机其实很简单内存就是纸带CPU 的寄存器就是有限状态控制程序就是状态转移表。你写的 while 循环、递归调用、闭包最终都会落到“读写内存、改变状态、移动执行位置”这个模式上。所以讨论“某个问题是否被算法解决”本质上就是问“某个语言是否被图灵机判定”。3.3 决策计算的语言学转身从“解问题”到“认语言”有了图灵机我们就可以更精确地定义“问题”了。一个判定问题通常只需要回答“是”或“否”比如“给定一个图是否有长度不超过 k 的路径”。把问题的所有实例编码成字符串再把答案为“是”的那些实例对应的编码收集成一个集合这个问题就转化成了一个语言。于是“解决一个问题”就等价于“用图灵机识别一个语言”。你不需要让图灵机输出一串复杂的结果只需要让它接受或者拒绝。这就是标题里 Decision 的含义决策计算研究的是哪些语言可以被人用算法判定“是/否”。这个翻译非常关键因为一旦把问题变成语言所有形式语言理论里的工具就都能用了。你可以问这个语言是可判定的吗如果可判定它属于哪一层语言谱系如果不可判定能不能用归约证明它的不可判定下一节我们就要面对这个理论最核心的结论之一有一些语言算法永远无法判定。4. 可判定性停机问题的不可判定证明4.1 把“问题”翻译成“语言”Decision 的本质先明确一个重要的性质可判定性要求图灵机对所有输入都停机接受属于该语言的串拒绝不属于该语言的串。注意“所有输入”这四个字它排除了“只对某些输入给答案”的偷懒做法。举个例子问题“给定一个 DFA 和一个字符串DFA 是否接受该字符串”是可判定的。你只要模拟这个 DFA 跑一遍输入最后看停在终态没有即可模拟过程一定在有限步内结束。问题“给定一个图和两个顶点是否 s 和 t 连通”也是可判定的BFS 或 DFS 就能回答遍历过程不会无限循环。真正麻烦的是涉及图灵机自身的问题。比如语言 A_TM { M, w | 图灵机 M 接受输入 w }。这里 M, w 是编码把图灵机的状态转移表和输入串按某种规则编码成一个字符串。看上去给定 M 和 w我只要模拟 M 在 w 上的运行它接受了我就接受拒绝了我就拒绝这不是很简单吗问题出在 M 可能在 w 上循环。你模拟它它一直不停止你要不要继续等下去你无法区分“它还需要跑一万步”和“它永远不会停”。这就是为什么 A_TM 只是一个半可判定的语言而不是可判定的。4.2 停机问题的完整证明对角线笔法现在来到整个课程最著名的一个结论语言 HALT_TM { M, w | 图灵机 M 在输入 w 上停机 } 是不可判定的。这个结论通常叫停机问题它的证明思路很经典假设存在一个判定器然后构造一台“专门跟自己作对”的机器。完整的推演是这样的假设存在一台图灵机 H它能判定任何 M, w 是否为停机问题的一个“是”实例。即 H(M, w) 接受当且仅当 M 在 w 上停机。基于 H构造一台新机器 D。D 的输入被解码为某个图灵机的编码 然后执行以下逻辑D(M) 运行 H(M, M) 如果 H 接受说明 M 在 M 上停机 D 进入一个无限循环永不停止 如果 H 拒绝说明 M 在 M 上不停机 D 停机并接受现在让 D 自己跑在自己身上D( )。我们分两种情况讨论如果 D( ) 停机那么 H( , ) 会返回接受。可是按照 D 的构造当 H 返回接受时D 会故意进入无限循环矛盾。如果 D( ) 不停机那么 H( , ) 会返回拒绝。可是按照 D 的构造当 H 返回拒绝时D 会停机接受矛盾。两种可能性都导致矛盾所以假设不成立H 不存在。我第一次看这个证明的时候总觉得有哪里不对H 说“M 在 上停机”D 就故意不停机H 说“M 在 上不停机”D 就停机。等到问 D 自己的时候它的话和它的行为完全相反矛盾自然就出现了。这套思路听起来像绕口令但它恰恰是严谨的。这里要澄清一个很容易有的误解并不是说“某台具体的机器”不能被判断是否停机。每台机器单独拿出来可能都能写一个专门的分析程序来判断它。不可判定说的是不存在一个统一的、对任意 (M, w) 都正确的算法。你可以一个个处理单个问题但不存在一劳永逸的通用判定器。学这个证明的时候我的建议是不要光看一定要手写三遍。第一遍照着写第二遍合上书自己推第三遍试着给别人讲。讲到你能在每一步都回答“为什么这里要这样设计”的时候才算真正理解了。4.3 可判定、半可判定与不可判定的边界停机问题不是孤立的反例它开启了一整类“判不了”的问题。我们可以把语言按可判定性分成三个层次性质可判定半可判定不可判定对“是”实例一定在有限时间内接受一定在有限时间内接受不一定能识别对“否”实例一定在有限时间内拒绝可能拒绝可能循环不一定能识别是否存在识别算法存在停机判定器存在“只保证是”的识别器不存在任何判定器A_TM 就是典型的半可判定我确实可以模拟 M(w)它接受我就接受但它拒绝或循环时我无法在有限时间内给出“否”的结论。而停机问题是连“是”都没法在统一算法下保证判定的。这两者的差异放到现实中很有体感。你在调试一个崩溃的程序程序报错退出你能确定地知道“它拒绝了”——这就像可判定问题里的“否”。但如果程序一直卡住你可能完全无法判断它是在计算一个大素数还是陷入了死循环。抽象的定理和真实的调试体验在这里是一致的。还有一个推论值得记住如果一个语言 L 既是半可判定的它的补集也是半可判定的那么 L 就是可判定的。原因是同时跑两个识别器一个识别 L一个识别 L 的补集总能有一个先停下。这个结论从侧面说明很多不可判定问题的补集连半可判定都算不上。5. 归约用已知的“不可算”证明新的“不可算”5.1 归约的方向为什么“用 B 解 A”意味着 A ≤ B当我们手上已经有了一堆不可判定问题怎么证明一个新问题是不可判定的最常用的工具是归约。映射归约的定义是这样的语言 A 可以归约到语言 B记作 A ≤m B当且仅当存在一个可计算函数 f使得对任意字符串 w都有w ∈ A 当且仅当 f(w) ∈ B关键是理解这个方向背后的逻辑如果 B 有一个判定器那么我可以先对任意输入 w 计算 f(w)然后把这个结果交给 B 的判定器最后得到的答案就是在回答“w 是否属于 A”。所以B 可判定 → A 可判定。反过来写就是本文最常用的推理链如果已知 A 不可判定并且 A ≤m B那么 B 必然不可判定。因为如果 B 可判定A 就跟着可判定了这与已知矛盾。这里我见得最多的问题就是方向搞反。很多人以为“A 不可判定A 归约到 B所以 B 不可判定”中的归约方向是 B 到 A这是不对的。用个不算特别精确但很贴切的类比如果你能用验血来判断一个人的心脏病那么“判断心脏病”这个问题就归结到了“验血”这个问题上。这时候如果有人告诉你心脏病这个问题本身是无法用通用算法解决的那验血也不能解决它——因为一旦验血能解决心脏病也能解决了。所以记住这个口诀把已知不可判定的问题归约到新问题新问题才不可判定。也就是说箭头从已知不可判定的 A 指向待证明不可判定的 B。5.2 实战归约从语言接受问题到停机问题我们已经知道 A_TM 是不可判定的现在用它来证明停机问题 HALT_TM 也不可判定。假设 HALT_TM 存在判定器记作 HALT。我们要构造的归约函数 f输入 M, w输出一台新机器 M使得 M 停机当且仅当 M 接受 w。构造 M 的思路是“包装”M 在任意输入 x 上先假装什么都没看见直接去模拟 M 在 w 上的运行。如果 M 接受 wM 就停机如果 M 拒绝 wM 就故意进入无限循环如果 M 在 w 上不停机M 当然也跟着不停机。M(x): 模拟 M 在输入 w 上的运行 如果 M 接受 w: 停机接受 如果 M 拒绝 w: 进入无限循环现在调用 HALT(M)询问“M 是否在所有输入上都停机”。等一下这里有个细节。M 的行为和输入 x 无关所以它要么在任何输入上都停机当 M 接受 w 时要么在任何输入上都不停机当 M 拒绝 w 或循环时。因此我只要问 HALT(M, 0) 即可输入 x 随便选什么都可以。于是有下面的等价关系M 接受 w ⇔ M 停机在输入 0 上右边的判断由 HALT 完成左边的判断就等价于 A_TM 被判定。这与 A_TM 不可判定矛盾所以 HALT_TM 不可判定。这个构造体现了一个很实用的套路把“接受/拒绝”包装成“停机/不停机”。很多归约证明都在做同一件事——改造目标机器让它的某种行为恰好对应原机器的接受行为。类似的归约可以一路做下去。比如问题“给一个图灵机 M它的语言是否为空”也不可判定。思路是构造 M仅当 M 接受 w 时 M 才接受某个固定输入否则 M 什么都不接受。这样“语言是否为空”就编码了“是否接受 w”。这类结论可以推广成一句非常强的话任何关于图灵机“语言的非平凡性质”的判定问题都是不可判定的。这句话几乎一劳永逸地覆盖了大量看似有价值的自动分析需求。5.3 换一种眼光看工程中的“做不到”学完归约之后再回头看看实际开发里遇到的“自动分析”需求你会发现很多东西本质上都是不可判定的。比如静态分析里常见的“这段代码是否永远不会抛异常”。你可以把一段任意程序包装成一个图灵机把“抛异常”对应成“停机”于是这个问题就变成了停机问题的变体不可判定。编译器只能做保守估计它分析不出就默认可能抛异常宁可多插桩也不敢误判安全。再比如“两个程序是否等价”这是一个极具诱惑力的问题。如果我能自动判断任意两个函数是否功能相同代码重构、测试覆盖都可以自动化。但这个问题同样不可判定。所以测试和验证领域会退而求其次做有限状态空间的模型检测、做符号执行、做差分测试而不是追求一个万能的等价判定器。安全领域的“这段二进制代码是否是恶意代码”也是一样。你要检测任意程序是否有恶意行为本质上也要回答一个不可判定的问题。所以杀毒软件永远只能做特征匹配、行为启发、沙箱观察而不是“理论上完全判定恶意性”。我自己的体会是计算理论不是一门“记忆课程”而是一门“改变直觉”的课程。当你完整写过一遍停机问题的证明再遇到那种拍胸脯说“只要给我足够的算力就能证明任意程序会不会终止”的需求你只会平静地问一句你是不是把半可判定当成可判定来用了这门课的第二篇到这里刚好走完了一条完整路线从正则语言的局限到上下文无关语言和 PDA再到图灵机与可判定性最后用归约把不可判定的结论扩展到一大类问题。下一篇我们可以聊一聊这个框架里剩下的那块版图——计算复杂性也就是 P 与 NP 的那片疆域。
