从有穷自动机到图灵机：记忆结构决定计算能力边界

简介：这份《计算理论知识点.docx》面向哈尔滨工程大学计算理论期末备考的计算机专业学生，也适合需要快速回顾形式语言与可计算性基础的读者，用条目化方式梳理自动机、图灵机、语言理论与计算复杂度等核心考点，帮助在考前集中背诵结论并查漏补缺。压缩包仅含1个docx文档，大小约18KB，篇幅轻便，适合打印或导入平板反复翻阅。文档围绕DFA与NFA等价、正则语言封闭性、上下文无关语言与下推自动机、图灵可识别与可判定、判定器、可计算函数、映射归约，以及P、NP、SAT、3SAT等高频知识点展开，强调定义与判定条件的对应关系，便于快速定位易混概念。已有551人学习，适合期末冲刺时配合教材和习题使用，也可作为章节复习前的提纲，对易混的判定条件与归约关系可反复对照记忆。

1. 加资源不变强、砍资源才变强：计算理论里那条反直觉的分界线

计算理论里最反直觉的一件事是：给机器加资源，能力几乎不涨；砍资源，能力反而涨。给图灵机多加几条带子、多装几个读写头、放开非确定性让它同时走多条分支，这三样全加上去，它能判定的语言集合一个都没变大——多带等价于单带，非确定等价于确定。反过来，把读写头拴死在输入区不许越界，这台被削弱的线性有界自动机，接受问题反倒成了可判定的：格局总数有限，搜得完。

这条分界线值不值得搞懂，取决于你想“背下来”还是想“推出来”。这份文档把结论按有穷自动机、上下文无关文法、图灵机、可判定性、复杂性一条条列全了，它们压缩的是同一件事：机器的记忆结构决定它的能力边界。只背结论，换个设问就会错；知道记忆结构怎么限制机器，结论遇到没见过的题也能现推。下面按这条线索，从最弱的有穷自动机往上走。

2. 正则语言的三张脸：为什么 DFA、NFA、正则表达式总是同时出现

2.1 五元组里那个 δ，决定了 DFA 只能记住有限个事实

确定型有穷自动机写成五元组 (Q, Σ, δ, q0, F)，其中 δ: Q×Σ→Q 是一个全函数：给定当前状态和一个输入符号，下一个状态唯一确定。关键不在“确定”，而在 Q 是有限集。整台机器的记忆就是“我现在处在哪个状态”，状态数一旦固定，它能记住的事实就固定了。

这个限制很硬。判断“串是否以 1 结尾”只要 2 个状态；判断“串里 1 的个数是不是 3 的倍数”要 3 个状态，取模就够了；但判断 {0ⁿ1ⁿ | n≥0} 就不行——n 可以任意大，机器必须记住“已经读了多少个 0”，而这是无穷多种可能，塞不进有限个状态。教材里的泵引理就是把这句话形式化：p 个状态的机器读长度 ≥p 的串，走 p+1 步必然重复某个状态，中间那段读过的内容可以任意重复或删掉而判断结果不变，于是“必须精确计数”的语言全被排除。

提示：很多教材把 δ 定义成部分函数，允许某些 (状态, 符号) 没有转移。这在单独描述 DFA 时没问题，但一旦要构造补运算就会出问题，后面 2.3 节会踩到这个坑。

2.2 子集构造：NFA 的“猜测”怎么变成 DFA 的“确定”

非确定型有穷自动机的转移函数是 δ: Q×Σε→P(Q)，输出的是一个状态集合，还允许 ε 转移（不读输入就跳）。它的接受条件是“存在某条路径走到接受状态”，也就是它天生带“猜”的能力。直觉上它比 DFA 强，但结论是两者等价，桥就是子集构造——把“所有可能处于的状态”打包成一个 DFA 状态。

def subset_construct(nfa): start = eps_closure({nfa.q0}) # 起始状态先做 ε 闭包 dfa_id = {frozenset(start): 0} # DFA 的一个状态 = NFA 状态集合 queue, trans = [frozenset(start)], {} while queue: cur = queue.pop(0) for a in nfa.sigma: # 只遍历真实字母，ε 不进这个循环 nxt = eps_closure(move(cur, a)) # move：cur 中状态经 a 能到达的所有状态 if nxt not in dfa_id: # 只保留可达子集，不做全幂集展开 dfa_id[nxt] = len(dfa_id) queue.append(nxt) trans[(dfa_id[cur], a)] = dfa_id[nxt] accept = {i for s, i in dfa_id.items() if s & nfa.accept} return dfa_id, trans, accept # accept 按“集合里含 NFA 接受态”判定

参数和逻辑说明：eps_closure求的是不读输入就能到达的状态闭包，move只走一个真实符号，两者必须分开，否则会把 ε 路径重复计入。nfa.sigma不含 ε 是关键细节——ε 不是输入字母表里的字符，把它放进外层循环会导致构造出的 DFA 转移表多出一列永远用不到的边。状态数上界是 2^|Q|，实际只建从起始集合可达的那些，通常远小于上界，但最坏情况下的指数膨胀是真实存在的，这也是为什么工程里的正则引擎宁可保留 NFA 模拟（ Thompson 构造 + 并行状态集合）也不真去做确定化。

注意：这个构造同时证明了“语言是正则的当且仅当存在 NFA 识别它”。方向是：DFA 是 NFA 的特例（一个状态集合退化成单元素集），NFA 又能确定化成 DFA，两头一夹就闭合了。

2.3 封闭性为什么用乘积构造证明，星号为什么要靠 ε 边

正则语言在并、连接、星号下封闭，是文档里反复出现的结论。并和交的证明靠乘积构造：两台 DFA 同时跑，状态是序对 (q1, q2)，转移逐分量进行 δ((q1,q2), a) = (δ1(q1,a), δ2(q2,a))，接受条件按要证的运算挑。

注意表格最后一行括号里的“先补全死状态”：如果原机器的 δ 是部分的，某些串根本走不到任何状态，取反 F 之后这些串依然不被接受，补集就算错了。解决办法是加一个吸收状态，把所有缺失的转移都指向它，让它非接受，再取反。

连接和星号没法用乘积构造做，因为“前一段在哪结束、后一段在哪开始”这个切分点不确定。所以引入带 ε 边的 NFA：连接是把 M₁ 的每个接受状态用 ε 连到 M₂ 的起始状态；星号是在外面套一个新起始状态，ε 连到旧起始，旧接受状态 ε 连回旧起始。三种封闭运算对应三种 ε 连线方式，正则表达式的三个基本运算（并、连接、星号）刚好就是这三条构造。换句话说，正则表达式的语法不是随便定的，它的三种组合子之所以够用，是因为它们各自对应一个可构造的自动机拼接动作，多一个少一个都会破坏这套对应关系。

3. 下推自动机与乔姆斯基范式：一个栈为什么刚好够用

3.1 从 A → aB 到 A → BC：乔姆斯基范式在拆一棵树

上下文无关文法写成四元组 (V, Σ, R, S)，产生式形如 A → α，左边必须是单个变量，右边是变量和终结符组成的任意串。语言里的每个串对应一棵推导树，树根是起始符号 S，叶子从左到右拼成这个串。上下文无关的意思是：不管 A 出现在推导的什么位置，把它重写成 α 的规则都成立，不需要看 A 的左右邻居。

乔姆斯基范式把产生式压缩成两种形状：A → BC（两个变量）和 A → a（单个终结符），外加一种特例——如果 ε 在语言里，允许 S → ε，且 S 不出现在任何右部。任何上下文无关文法都能机械地转成这个形状，三步走：先把 A → BCD 这种长右部拆成 A → BX、X → CD；再把终结符混在长右部里的地方换成一个专门产生它的变量 T_a → a；最后消掉 ε 产生式和 A → B 这种单位产生式。

这套规范化的价值不在“好看”，而在它把推导树掰成了严格的二叉树。一棵有 n 个叶子的满二叉树恰好有 n−1 个内部节点，对应 n−1 次 A → BC 类型的推导，加上 n 次 A → a 把叶子生成出来，长度为 n 的串在任何乔姆斯基范式文法里的推导步数正好是 2n−1。这个数字是很多证明的支点：它意味着“枚举所有推导”是一棵有限的、深度有界的树，可以暴力搜，也可以从长度为 1 的子串往上填表——CYK 算法就是借这个结构在 O(n³) 里判成员资格。这也是文档里“每一个上下文无关语言都是 P 类”的来源。

3.2 栈的读写策略：记忆结构从“有限个格子”变成“一条后进先出的带”

下推自动机写得比有穷自动机多一个栈：(Q, Σ, Γ, δ, q0, Z₀, F)，转移函数 δ: Q×Σε×Γε → P(Q×Γε)，第三个输入参数是当前栈顶符号，输出可以往栈上压一串符号。栈的规则是后进先出，只有栈顶可见、可弹、可压。

这个记忆结构刚好对上“嵌套配对”这类语言。判断 {0ⁿ1ⁿ} 时，读 0 就压栈，读 1 就弹栈，最后栈里只剩初始符号 Z₀ 就接受——栈的深度天然记录着“已经读了多少个 0”。有穷自动机做不到这一点，因为它的“计数器”只能是有限个状态；图灵机不需要专门设计就能做，因为带子可以来回移动。栈卡在中间：容量无界，但只能从一头进出。

这个限制也能解释为什么栈不够用。{0ⁿ1ⁿ2ⁿ} 不是上下文无关的，理由是栈只有一个顶，压 0 的计数会被后面 1 的计数覆盖掉，两种计数在同一个栈上互相打架。用一个栈记两件事，必然有一件记不住。

3.3 非确定性在这里不再是免费的：NPDA 与 DPDA 不等价

文档里说，一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。这里有个容易被忽略的差异：这个结论里的下推自动机是非确定的。有穷自动机那边，非确定型和确定型等价，子集构造就能抹掉“猜”的能力；下推自动机这边，等价的结论不成立，确定型下推自动机识别的语言（有时叫 DCFL）是上下文无关语言的真子集。

机制上的原因很清楚。子集构造之所以可行，是因为“NFA 当前可能处于的状态集合”虽然是个集合，但它是有限集 Q 的子集，天生塞得进有限个 DFA 状态里。放到下推自动机上，非确定型机器在某一时刻“可能处于的格局”里包含的是栈内容，而栈内容有无穷多种，这个集合塞不进任何有限结构，构造就断了。非确定性在这里没法用枚举抹平，只能真留着。

提示：非确定性是否“免费”，取决于你把它当作状态集合还是当作搜索分支。在可判定性层面它免费（后面 4.3 节会说非确定图灵机等价于确定图灵机），在时间层面它不免费（指数代价），在栈结构这就连语言类都改变了。

还有一条层级要记住：每一个正则语言都是上下文无关的。构造很直接——把 DFA 的每个状态 q 变成一个变量 A_q，对每条 δ(q,a)=r 加一条 A_q → aA_r，接受状态再加 A_q → ε。反过来不成立，{0ⁿ1ⁿ} 就是分界线上那个反例。

4. 格局与判定器：图灵机“循环”这件事到底黑在哪

4.1 格局：把“状态 + 带内容 + 读写头位置”打包成一个瞬间快照

图灵机的形式定义是 (Q, Σ, Γ, δ, q0, q_accept, q_reject)，δ: Q×Γ → Q×Γ×{L,R}，即当前状态加读写头下的符号，决定新状态、写回的符号和左移还是右移。注意 δ 在 q_accept 和 q_reject 上没有定义，这两个状态是“停机”的语义落点。

计算过程里任一时刻的完整快照，就是把当前状态、带内容、读写头位置三者合起来，这叫格局。形式化地写成 u q v 或者 u q a v：u 是读写头左边的串，q 是当前状态，v 是从读写头位置开始往右到最右非空白符号的串。这个写法很省，因为它默认读写头左边和右边远处全是空白，而空白符号是无限供应的。

格局的总数直接决定了一台机器的“可搜索性”。如果带子只用了有限个格子、读写头被限制在输入区内（线性有界自动机就是这种情况），格局数是 |Q| × n × |Γ|ⁿ，n 是输入长度，这是一个有限的数。既然有限，从起始格局能不能走到接受格局就是一张有限图上的路径问题，暴力搜一定能出结果。反过来，普通图灵机的带子可以越写越长，格局数没有上界，这张图是无限的，“能不能走到接受格局”就不再是有限搜索能回答的问题——这就是后面 5.3 节里可判定与不可判定的真正分水岭。

4.2 判定器与识别器：停机承诺值多少钱

在输入上跑一台图灵机，结果只有三种：接受、拒绝、循环。这里的循环不是“原地重复同样的步骤”，而是“永不停机”，可能一直在往右走、一直在写新的符号，你看着它一直在动，就是不知道它到底会不会停。

图灵可识别的语言（递归可枚举语言）只要求“存在一台图灵机，对语言里的串最终接受”，对语言外的串没有任何承诺，它可能拒绝，也可能一直跑下去。图灵可判定的语言（递归语言）要求更强：存在一台机器，对所有输入都停机，接受或拒绝都有明确答案。这种“所有输入都停机的图灵机”就是判定器。

判定器之所以被单独拎出来，是因为“区分循环和跑得久”这件事没有通用算法。你盯着机器跑到第 10¹² 步，它可能下一步就接受，也可能永远不。工程里可以用超时来兜底，理论上没有一个上界能保证“过了这个界还没停就是循环”。所以我们宁可讨论“保证停机”的机器，也不讨论“有可能循环”的机器。这也解释了为什么文档里要强调那一对结论：每一个可判定语言都是图灵可识别的，反过来不成立。

还有一个非常实用的等价刻画：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。做法是让两台识别器并行跑，输入串 w 交替喂给两边各走一步，哪边先接受就立刻给出答案。因为 w 要么在语言里、要么在补集里，两边至少有一台会在有限步内接受，所以这个并行过程一定停机，而且它同时给出了“是”和“否”的判决。

4.3 多带、非确定与三种描述层次：加资源为什么不改变能力

多带图灵机每条带子有自己的读写头，看起来比单带强一大截。等价性证明的做法是把 k 条带子编码到一条带上：带子划分成 k 条“道”，每条道对应一个虚拟带，道与道之间用分隔符隔开，每个虚拟读写头的位置用带标记表示。模拟一步需要扫过整段被用到的区域，单次代价 O(t)，跑到 t 步总代价 O(t²)。这就是文档里那条“t(n) 时间的多带图灵机与 O(t²(n)) 时间的单带图灵机等价”的来源。

非确定型图灵机等价于确定型图灵机，做法是广度优先遍历格局树：用三条带子，一条存输入，一条当队列存待搜的格局，一条当工作区。一条分支的地址就是一串选择编号，模拟时按编号在输入上重走一遍。代价是时间从 t 涨到 b^{O(t)}，b 是最大分支数。能力没变，代价变了——这条差别在第 6 章会成为 P 与 NP 之间那道墙。

支撑这一整套等价性证明的，是丘奇-图灵论题：算法这个直观概念，就是图灵机可计算。它不是定理，没有证明，它是“形式化定义选对了”的经验判断——迄今为止所有被提出的计算模型（λ 演算、递归函数、寄存器机）算出来的都是同一批函数。至于描述一台图灵机，可以分三个层次：形式化描述要写全状态和转移函数，最啰嗦也最严格；实现描述用日常语言讲清楚数据怎么组织，但不逐条写转移；高水平描述连带子和读写头怎么管理都不提，只讲算法步骤。写证明时按需要挑层次，写“判定某语言”的证明通常用实现描述就够了，写涉及步数或空间的分析就得下沉到形式化描述。

5. 归约链排查：从 A_TM 到 EQ_TM，五条最容易翻车的地方

5.1 映射归约：一个可计算函数，加上一个双向蕴含

归约的直觉是“把难问题翻译成另一个问题，如果另一个问题能解，难问题就能解”。文档里选的是最简单也最好用的一种，叫映射可归约性：语言 A 映射可归约到语言 B，记作 A ≤m B，意思是存在一个可计算函数 f: Σ→Σ，使得对每个串 w，w ∈ A 当且仅当 f(w) ∈ B。这个 f 叫归约函数。

可计算函数的定义要卡死：存在一台图灵机 M，对每个输入 w 都停机，停机时带上恰好是 f(w)。两个条件缺一不可——必须处处停机（f 是个全函数，不能对某些输入卡住），必须只留 f(w) 在带上（输出唯一，不能带一堆计算过程中的垃圾）。很多错误证明就坏在没检查第一点：如果 f 的计算本身可能不停，那这个归约根本没法用来做判定。

双向蕴含也是硬要求。如果只能证“w ∈ A 则 f(w) ∈ B”，得不到任何结论，因为 B 里还可能有 f 送不过去但照样在 B 里的串，A 和 B 的成员资格就脱钩了。所以每写一条归约，最该检查的是那个反方向：w ∉ A 时要能保证 f(w) ∉ B。

5.2 传染方向：为什么结论总是“B 也不可判定”

映射归约的两条定理，方向感是理解它的核心：

第一条的证明是一行逆否：如果 B 可判定，设 M_B 判定 B，那么“先算 f(w) 再交给 M_B”就是一台判定 A 的机器（f 处处停机，所以这一步一定结束），与 A 不可判定矛盾。第二条同理，用识别 B 的机器拼出识别 A 的机器。

方向感的关键在于：箭头永远从“已知难”指向“待证难”。画图时把箭头画成 w ∈ A ⟺ f(w) ∈ B，箭头尾部坐的必须是那个已经知道不可判定的 A。这条规矩在考场上尤其要命，写反了之后整道题的论证依然读起来通顺，但逻辑上是空的——它只证明了“B 的难度不高于 A”，而这通常是我们已经知道的事实。

经典链条都建立在这个方向上：A_TM = {⟨M,w⟩ | M 接受 w} 是图灵可识别但不可判定的（对角线论证），把它的实例改造成“M 在 w 上停机”的实例，就得到停机问题 HALT_TM 不可判定；同样的手法还能推到 E_TM（不接受任何串的图灵机）、REGULAR_TM（接受的语言是正则的那台图灵机）、EQ_TM（两台接受相同语言的图灵机）。

5.3 计算历史：把“机器跑起来”编码成一个串

证明不可判定性时最有用的工具，是把动态的过程压成静态的字符串。设 M 是图灵机、w 是串，M 在 w 上的一个接受计算历史是一个格局序列 C₁, C₂, …, C_l：C₁ 是起始格局，C_l 是接受格局，每个 C_i 都是 C_i−1 走一步的结果。拒绝计算历史同理，只是最后一个格局是拒绝格局。

这个定义有几个直接后果。计算历史一定是有限序列；如果 M 在 w 上永不停机，那就既不存在接受历史也不存在拒绝历史。确定性机器在给定输入上最多只有一条计算历史，非确定型机器可以有多条，每条分支各对应一条。正因为有这个编码，“M 是否接受 w”就变成了“存不存在一个合法的格局序列”，也就是一个关于字符串的匹配问题，可以交给别的语言去判。

线性有界自动机是这套工具的最佳展台。它是一台被限制的图灵机，读写头不许离开输入区，想往左越过左端点时原地不动，和普通图灵机对待左端点的方式一样。限制带来一个致命后果：格局数变成有限的（状态 × 位置 × 带内容的所有组合）。既然有限，A_LBA（给定 LBA 是否接受给定串）就是可判定的——把所有格局铺开成图，跑一遍可达性就行。但 E_LBA（这台 LBA 是否不接受任何串）就是不可判定的，因为被问的不再是某一个固定长度的输入，而是“所有可能的输入串”，串长无界，格局图跟着无界，有限搜索这招就废了。

注意：A_LBA 可判定、E_LBA 不可判定

本文还有配套的精品资源，点击获取