简介面向计算机专业本科生与备考哈工程计算理论期末的复习者这份文档把自动机理论、图灵机、语言理论、计算复杂度四大板块的核心结论压缩成可直接背诵的短句适合考前突击与概念自查。压缩包内仅1个docx文件约18KB体积轻巧手机与电脑均可直接打开翻阅。内容以命题形式串起关键判定有穷自动机与正则语言的等价关系、正则语言在并、连结、星号运算下的封闭性、正则语言与上下文无关语言同下推自动机的对应、图灵机格局与图灵可识别/可判定语言的区分、判定器与丘奇-图灵论题、映射可归约与多项式时间归约以及P、NP和SAT、3SAT、CLIQUE、HAMPATH等问题的归属与不可判定问题清单可当作背诵提纲与查漏补缺的对照表。目前已有551人学习下载。1. 计算理论到底在算什么一台理想机器能做什么不能做什么很多人第一次翻开计算理论的讲义看到满页的圆圈、箭头和 δ 转移函数第一反应是这玩意儿跟每天写的代码到底有什么关系。其实计算理论问的问题特别朴素一件事一台理想化的机器到底能不能算出来如果能它得花多少时间和空间。它不研究某台具体电脑快不快而是把所有计算抽象成「机器 输入 规则」三样东西像拆一台机器看齿轮怎么咬合。正因为抽象得足够狠它给出的结论能跨语言、跨硬件、跨几十年依然成立。搞懂它你会拿到一把尺子遇到一个新问题先量一量它落在哪一层再决定值不值得投入。2. 有穷自动机与正则语言一台「记不住数」的机器凭什么够用很多人对「机器」的想象是一台会算数的电脑能加能减能存变量。有穷自动机偏偏反着来它没有任何草稿纸全部家当就是「我现在处于哪个状态」。就这样一台抠门到极致的机器却撑起了正则语言这一整层也撑起了你每天都在用的字符串匹配。这一章要讲清的不是怎么画状态图而是这层能力的天花板在哪、为什么刚好卡在这里。2.1 有穷自动机长什么样状态就是它全部的记性把确定型有穷自动机DFA想成一台地铁闸机。它只有「锁着」和「开着」两种状态你投一枚币它就从锁着跳到开着你推杆过去它又弹回锁着。它不会记账不会统计今天来了多少人它只知道此刻自己是开还是关。形式化地说一台 DFA 由五部分组成一个有限的状态集合、一个输入字母表、一个转移函数、一个起始状态、一个接受状态集合。读完整个输入串后如果停在接受状态里就说它接受这个串否则拒绝。关键在于「有限」两个字。状态数是个固定常数无论输入多长机器内部能记住的信息量不变。这既是它的局限也是它的优点——局限在于它记不住「前面已经读了多少个 a」优点在于它的运行速度是严格线性的输入翻十倍时间也只翻十倍。下面这段代码是一个最小的 DFA 模拟它判断一个二进制串里 1 的个数是不是偶数。请留意注释里那句「唯一的内存」# 识别「1 的个数为偶数」的 DFA全机只有两个状态 # state 0 表示到目前为止读到偶数个 1state 1 表示奇数个 def is_even_ones(s: str) - bool: state 0 # 起始状态 for ch in s: # 读写头从左到右扫一遍只能前进 if ch 1: state 1 - state # 每读到一个 1 就翻转0 - 11 - 0 elif ch ! 0: return False # 字母表以外的字符直接进拒绝 return state 0 # 停在接受状态才算接受这里的state就是整台机器的全部记忆一个整数取值只有 0 和 1。为什么够用因为「偶数个」这个性质只跟奇偶有关跟具体数字无关。如果换成「1 的个数等于 3」两个状态就不够了你得数到三需要更多状态如果换成「1 的个数和 0 的个数一样多」那无论给多少个状态都不够因为这需要一个能无限增长的计数器。这一步跨不过去就是正则语言的边界。2.2 并、连接、星号三个运算为什么值得单独拎出来正则语言对三种运算是封闭的并运算、连接运算和星号运算。封闭的意思是拿两个正则语言做这三种运算里的任何一种结果还是正则语言。这条性质听起来像一句正确的废话实际是整套理论的骨架。并运算像把两台机器并联造一个新的起始状态用空串转移分别指向原来两台机器的起始状态谁接受都算接受。连接像串联第一台机器走到接受状态时用空串转移跳到第二台机器的起始状态接着往下跑。星号像加了一个回环允许从接受状态空串跳回起始状态重复任意多次也允许一次都不循环。为什么偏偏是这三个因为它们正好是正则表达式的三条语法规则。你写(ab|c)*的时候用的就是连接、并、星号。这三条规则能生成的语言类和有穷自动机能识别的语言类是同一个类。这条等式是整章的地基。还有两条容易被忽略、但推导时天天用到的性质空集连接到任何集合上还是空集因为没有任何串能拆成「来自空集的串 来自另一个集合的串」空串连接到任何一个串上不改变这个串因为空串长度为 0粘在前后都不产生新字符。前者相当于乘法里的零后者相当于乘法里的 1。写形式化证明时这两条是收尾的常用手段。2.3 非确定型允许「猜」的机器为什么没有变强非确定型有穷自动机NFA比 DFA 多两项特权同一个状态面对同一个字符可以有好几条出路还可以走不消耗输入的空串转移。听起来它像开了天眼能同时试探所有分支总有一条走通就接受。但结论是每一台非确定型有穷自动机都等价于一台确定型有穷自动机。转换的办法叫子集构造——把 NFA 里「此刻可能处于的那一堆状态」打包当成 DFA 的「一个状态」。原来 n 个状态的 NFA转出来的 DFA 最多有 2 的 n 次方个状态是个天文数字但终究有限。所以四条说法是同一件事一个语言是正则的当且仅当有一台 NFA 识别它也当且仅当有一台 DFA 识别它也当且仅当有一个正则表达式描述它。这个结论值得多想一层。非确定型并没有让机器变强它只是让「描述」变短。你写一个正则表达式本质上是在用一种非确定型的方式描述语言而真正跑起来做匹配的引擎如果要保证线性时间得走 DFA 那条路线。至于很多语言里的正则实现为什么会出现回溯爆炸那是另一回事——它跑的不是 DFA这一点在第 6 章还会再提。2.4 加一个栈就跳出去了下推自动机与上下文无关文法正则语言的软肋可以用一句话概括它数不了数。像「若干个 a 后面跟着同样多个 b」这样的语言不是正则的。原因很直白要判断 a 和 b 数量相等机器必须记住读了多少个 a而这是任意大的数有限个状态装不下。这里没有任何玄学纯粹是「记性不够」。但只要给机器配一个栈问题立刻变得简单读到 a 就压栈读到 b 就弹栈最后看栈是否为空。这就是下推自动机PDA。而一个语言是上下文无关的当且仅当存在一台下推自动机识别它等价地当且仅当有一台上下文无关文法产生它。三条路——文法、自动机、派生树——描述的是同一层能力。再往下一层还有一个规范化结果任何一个上下文无关语言都可以用乔姆斯基范式的文法产生。范式把规则限制得极简每条规则要么是「一个非终结符变成两个非终结符」要么是「一个非终结符变成一个终结符」顶多再允许起始符号产生空串。这个限制不损失表达能力却让很多证明变得可写比如证明「每个上下文无关语言都是可判定的」。层级关系到这里已经很清楚了每一个正则语言都是上下文无关的反过来不成立。前者真包含于后者像俄罗斯套娃一层套一层。3. 图灵机与可判定性为什么「会不会停机」是一道分水岭给有穷自动机加一条无限长的纸带再加一个能左右移动、能读能写还能改的读写头就得到了图灵机。它的每一步仍然简单到乏味看一眼当前格子按规则改一下挪一格换个状态。但「能回头改」这件事带来了质变——机器第一次拥有了可以反复擦写的草稿纸于是「计算」这件事被推到了它的极限。这一章要分清的是识别和判定差在哪为什么差这一点点整个学科的面貌就变了。3.1 格局给运行中的机器拍一张快照一台图灵机在跑的时候每一瞬间的状态可以完整地写成三样东西的组合当前处于哪个状态、纸带上的内容是什么、读写头停在哪一格。这三样合起来叫一个格局。运行过程于是变成了一串格局起始格局、第二步的格局、第三步的格局一直排下去。这个抽象的价值在于它把「动态的运行」翻译成了「静态的序列」。于是「机器接受输入 w」这句话可以被改写成「存在一个有限的格局序列第一项是起始格局最后一项是接受格局且每一项都是前一项按规则走一步的结果」。这一改写极其关键后面几乎所有不可判定性证明都是绕着一个格局序列做文章。这里有个细节要抠清楚计算历史一定是有限序列。机器如果在输入上永不停机那就既不存在接受计算历史也不存在拒绝计算历史一条都没有。对确定型机器来说任何给定输入上最多只有一条计算历史非确定型机器可以有多条每一条对应它的一个分支。3.2 识别与判定差别只在「会不会永远转下去」一台图灵机在某个输入上跑最终只有三种结局接受、拒绝、循环。前两种叫停机第三种叫不停机。「循环」这个词容易误导人它不是指原地重复同样的动作而是指机器永远不给出结论。于是有了两个层次的区分。如果一个语言可能被某一台图灵机识别——输入属于该语言时机器接受不属于时机器拒绝或不停机——这个语言就叫图灵可识别的也叫递归可枚举语言。如果存在一台图灵机对任何输入都停机属于就接受、不属于就拒绝这个语言就叫图灵可判定的也叫递归语言。那台「所有输入都停机」的机器叫判定器。为什么学界更喜欢讨论判定器因为判定器好说话。给你一台普通图灵机和一串输入它跑了三天三夜没动静你根本分不清它是卡在死循环里还是只差最后一步就算完了。这种「分不清」在实际工程里就是最典型的麻烦很多人第一次接触不可判定性时都会在这里感到困惑。可判定语言一定是可识别的反过来不成立。补集的概念在这里派上用场。一个语言的补就是所有不属于它的串构成的集合。如果某个语言的补集是图灵可识别的就说它是补图灵可识别的。有一条干净的等价关系一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可识别的。直观理解是你同时开两条线跑一条找「属于」的证据一条找「不属于」的证据因为答案必然落在其中一边所以总有一条会先给出结果整个过程必然停机。3.3 丘奇-图灵论题把「算法」这两个字固定下来「算法」这个词在日常语境里是模糊的你说它是一段步骤那什么才算步骤图灵机给了一个可以写在纸上的答案。丘奇-图灵论题说的就是任何直觉上可计算的算法都能被一台图灵机计算。这不是一条可以证明的定理而是一个被广泛接受的界定——它把「算法」这个模糊概念固定下来了。有意思的是描述一台图灵机有三档详细程度。最底层是形式化描述状态集、转移函数一条条写清楚往上一层是实现描述用日常语言说清数据怎么存、步骤怎么走但不提状态编号再往上是高水平描述连纸带和读写头都省了只说算法在做什么。做不可判定性证明时用最高水平那种就够了因为论题保证了「你说的这套步骤」一定能被图灵机实现。支撑这套论题的还有一串等价性结论每一台多带图灵机都等价于一台单带图灵机每一台非确定型图灵机都等价于一台确定型图灵机一个语言是图灵可识别的当且仅当存在一台非确定型图灵机识别它一个语言是图灵可判定的当且仅当存在一台非确定型图灵机判定它。这里的「等价」只保证能算出来不保证一样快——非确定型转确定型时间上通常要付指数级的代价这一点在讨论复杂度时会被反复提起。3.4 一份名单哪些问题有答案哪些注定没有把这层的结论列成一张表比背十遍定义都管用。下面这些记号在教材里反复出现记住「问的是什么」比记住字母更重要记号它问的问题结论A_DFA这台确定型有穷自动机接受这个串吗可判定A_NFA这台非确定型有穷自动机接受这个串吗可判定A_REX这个正则表达式能生成这个串吗可判定E_DFA这台自动机是不是什么都不接受可判定EQ_DFA两台自动机接受的语言是不是同一个可判定A_CFG这台文法能产生这个串吗可判定E_CFG这台文法是不是什么都产生不了可判定A_LBA这台线性有穷自动机接受这个串吗可判定A_TM这台图灵机接受这个串吗不可判定HALT_TM这台图灵机在这个输入上会不会停机不可判定E_TM这台图灵机是不是什么都不接受不可判定REGULAR_TM这台图灵机接受的语言是不是正则的不可判定EQ_TM两台图灵机接受的语言是不是同一个不可判定且不可识别、补也不可识别E_LBA这台线性有穷自动机是不是什么都不接受不可判定ALL_CFG这台文法是不是能产生所有串不可判定PCP这组对应串是否存在一个匹配解不可判定表里最值得盯住的是 A_TM 和 E_LBA 这两行。前者不可判定是整栋楼的第一块多米诺骨牌几乎所有后续的不可判定结论都从它推出来后者更有意思——A_LBA 明明可判定只把问题从「接受某个串吗」换成「什么都不接受吗」结论就翻了个面。可见「不可判定」不是某个问题的怪癖而是一片有规律的区域。还有一个容易被忽略的层次正则语言是上下文无关的上下文无关语言是可判定的可判定语言是图灵可识别的。每一层都是前一层加上一点新能力换来的反过来每一步都严格地失去一些东西。4. 映射可归约把不会做的题翻译成会做的题如果每遇到一个不可判定问题都得从头构造一遍对角线论证那这门课就没法上了。所幸有一个通用工具归约。它的思路特别像日常办事——我不会修这台机器但我知道怎么把它改装成另一台我确定修不好的机器于是「修不好」这个结论就转移过来了。这一章讲清这个「转移」的机制、方向和代价。4.1 一个只做翻译的函数映射可归约的定义是存在一个可计算函数 f把问题 A 的每个实例翻译成问题 B 的一个实例并且满足「w 属于 A当且仅当 f(w) 属于 B」。这时记作 A ≤m B那个 f 就叫从 A 到 B 的归约。什么叫可计算函数形式化地说如果有一台图灵机 M在任何输入 w 上都会停机并且停机时纸上恰好只有 f(w)那 f 就是可计算的。注意两个要求「一定停机」和「输出唯一」。这两条保证了这个翻译过程本身不是一个新麻烦。举个具体的构造。想把「图灵机 M 是否接受 w」翻译成「某台图灵机是否停机」可以这样造拿 (M, w) 这对输入构造一台新机器 M它无论收到什么输入 x都先在内部模拟 M 在 w 上的运行一旦 M 接受就立刻停机。于是 M 接受 w 当且仅当 M 会在某个输入上停机。整个构造只是照着规则拼装没有搜索、没有试探显然可计算。这条路径就是 A_TM ≤m HALT_TM 的标准做法。写成伪代码会更容易看清楚构造的味道# 这是一个「构造器」输入一台机器和一个串输出一台新机器的描述 # 注意它不运行 M只生成描述所以它一定能在有限步内结束 def build_machine(M, w): def M_prime(x): # 新机器忽略自己的输入 x run(M, w) # 内部模拟 M 在 w 上的运行 if M_accepts(M, w): return halt # M 一旦接受M 就停机 else: loop_forever() # 否则永远转下去 return M_prime # 返回的是描述不是运行结果这段代码的重点不在语法而在两个性质。第一build_machine本身必定停机它只是把M和w打包进去没有执行模拟。第二M_prime的行为和被翻译的问题严格对应只要 M 接受 wM 就在所有输入上停机否则 M 就在所有输入上永不停机。翻译的保真度就体现在这里。4.2 归约的箭头只往一个方向传结论归约最容易被用反的地方就是方向。A ≤m B 的含义是「A 不比 B 难」B 至少和 A 一样难。所以结论只有两条合法的流向第一如果 A ≤m B 且 A 是不可判定的那么 B 也是不可判定的。道理是反证假如 B 可判定那拿到一个 w先算出 f(w)再用 B 的判定器一问就知道 w 属不属于 A于是 A 也可判定了矛盾。第二如果 A ≤m B 且 B 是图灵可识别的那么 A 也是图灵可识别的。这条是顺着用的B 有识别器A 就借它的光。反过来的推论一条都不成立。知道 B 不可判定推不出 A 不可判定知道 B 可识别也推不出什么有用的东西。方向搞反是初学阶段的高频失分点第 5 章会专门再说。归约还具有传递性A ≤m B 且 B ≤m C就有 A ≤m C这让证明可以一段一段接力。4.3 计算历史不可判定性证明的常用手法要证明「某个语言不可判定」最常用的套路是先假设它可判定然后拿这个假设去判定 A_TM矛盾。中间那一步靠的往往就是计算历史。接受计算历史是一个格局序列第一项是机器在输入上的起始格局最后一项是接受格局中间每一步都符合转移规则。拒绝计算历史同理只是最后一项换成拒绝格局。前面说过这个序列一定是有限的机器要是永不停机两种历史都不存在。确定型机器最多一条非确定型机器可以有多条对应它的各个分支。这个工具在证明 E_LBA 不可判定时威力最大。线性有穷自动机是一种被严格限制的图灵机读写头不许离开输入所占的那一段区域想越界就原地不动。于是它的可用内存被输入长度锁死了。正因为如此它的格局总数是有限的A_LBA 才可判定——暴力枚举所有可能格局看能不能走到接受格局就行。但 E_LBA 问的是另一件事这台机器是不是对任何输入都不接受。为了回答它你得把「某台机器在某个输入上的接受计算历史」编码成一个串让 LBA 去检查这段编码是不是合法的历史。整个证明就是围绕这个编码展开的。这类构造第一次读会觉得绕但它有一个很朴素的内核把「过程」压扁成「数据」再让另一台机器去读这份数据。4.4 归约也分贵贱多项式时间版本到了复杂度这一层归约还是那个归约但开始算路费了。如果那个翻译函数 f 可以在多项式时间内算出来就说 A 多项式时间映射可归约到 B记作 A ≤p B。这里多出来的限制不是形式主义。因为如果一个翻译要算指数年那即使 B 有快速算法整体也没意义了。所以复杂度层面的归约必须便宜才能把「B 快」这个性质传递给 A。最经典的两个结果是SAT 是 NP 完全的于是 SAT 落在 P 里当且仅当 P 等于 NP以及 3SAT 可以多项式时间归约到 CLIQUE也就是图里有没有一个大小给定的完全子图。后者的构造很有画面感公式的每个子句出三个点排成一列同一列内的点之间不连边不同列之间只要两个文字不互相矛盾就连一条边于是一个满足赋值对应一个团一个团也对应一个满足赋值。3SAT、HAMPATH、CLIQUE、SUBSET-SUM 这些名字都属于 NP 这一层。5. 易混概念辨析这几个词新手十有八九会张冠李戴理论课的名词密度高很多词长得像、读起来也像混用的代价却很大——一道证明题思路全对就因为把「可识别」写成「可判定」整个论证垮掉。下面五组是翻车率最高的每组按「混在哪、为什么会混、怎么区分」三步说清楚。5.1 误区一把「可识别」当成「能算出来」易混点在于可识别和可判定听起来都像「有办法」。为什么容易混因为教材里的例子大多是先给识别器、再升级成判定器读着读着就以为两者差不多。区分办法抓住一句话识别器允许在「不属于」的输入上永远转下去判定器不允许。所以可判定是可识别的真子集。判断一个语言属于哪一层先问自己如果答案是否定的机器能不能给出一个干脆的「否」能才是可判定。A_TM 就是标准的反例——属于的情况机器总能找到不属于的情况它可能永远找不到于是它可识别但不可判定。5.2 误区二把「非确定型」理解成「随机」或「并行」易混点在于NFA 和 NTM 的描述里满是「可以选择」「多个分支」很容易被脑补成掷骰子或者开多线程。为什么容易混因为日常写代码时非确定性的确常和随机、并发挂钩。区分办法是看结论非确定型图灵机等价于确定型图灵机非确定型有穷自动机等价于确定型有穷自动机。如果它是随机或者并行那等价性就说不通了——随机算法有失败概率并行算法要真的多核。这里的「非确定」是一个纯粹的数学设定只要存在一条分支接受整个机器就接受不谈概率不谈调度。它存在的意义是让描述更简洁让复杂性类的定义更自然。5.3 误区三把归约的箭头方向搞反易混点在于A ≤m B 读起来像「A 小于 B」于是有人理解成「A 更简单所以 A 能被 B 判定」。这个方向刚好说反了A ≤m B 里B 才是更难的那个。为什么容易混因为「≤」这个符号在数学里天然带着大小直觉而这里的大小是反的——它衡量的是「难度」越难越大。区分办法是记住一条硬规则箭头指向难的一边结论从难的一边往回推。具体用的两条是A 不可判定推出 B 不可判定B 可识别推出 A 可识别。凡是想从 B 的坏消息推 A 的坏消息或者从 B 的好消息推 A 的好消息都是方向错了。5.4 误区四把正则语言和「简单字符串」划等号易混点在于很多人觉得凡是能用一两行正则表达式搞定的都是正则语言反过来凡是看起来复杂的都不是。为什么容易混因为日常写的正则表达式早就超出了理论上的正则语言——回溯、反向引用、捕获组、递归匹配这些能力根本不是有穷自动机能提供的。区分办法是拿两个判据。第一问它需不需要数数凡是要求「前后数量严格相等」的基本都跳出了正则。第二问它有没有嵌套结构括号匹配、嵌套的标签、表达式的语法树这些是上下文无关语言的领地。这也顺带说明了一件事正则表达式是一个描述工具正则语言是一个语言类两者名字像内涵并不重合。5.5 误区五把 P、NP 当成难度评分表易混点在于看到 NP 就以为「比 P 难」看到 NP 完全就以为「最难」。为什么容易混因为这套缩写被大量科普文章简化成了排行榜。区分办法是回到定义。P 是能在多项式时间内判定的语言类NP 是能被非确定型多项式时间图灵机判定的语言类换成更顺手的说法P 是「成员资格可以快速判定」的那类NP 是「成员资格可以快速验证」的那类。注意关键词是「判定」和「验证」不是「难」和「易」。而且 P 是否等于 NP 至今没有结论你不能拿一个未解问题当常识用。另外PSPACE 和 NPSPACE 是空间版本两者相等是已经证明了的结论和 P 对 NP 的悬而未决完全不是一回事。6. P、NP 与 PSPACE这套分层什么时候该拿出来用什么时候别用把前面几层的名字连起来会看到一个整齐的阶梯对数空间类 L 包含于 NLNL 包含于 PP 包含于 NPNP 包含于 PSPACE而 PSPACE 等于 NPSPACE。最后这一步相等来自萨维奇定理对于任何 f(n) ≥ n非确定型图灵机用 f(n) 空间能判定的语言确定型图灵机用 f(n) 的平方那么多空间也能判定。空间不像时间那样一非确定就爆炸成指数这是空间与时间最不对称的地方。至于「完全」问题PATH 是 NL 完全的TQBF 一类是 PSPACE 完全的它们各自的用处是给整个类画一条「在这个类里已经到顶」的线。类一句话直觉典型成员L / NL只花对数级空间PATHP成员资格能快速判定PATH 的判定、RELPRIME、上下文无关文法NP成员资格能快速验证SAT、3SAT、CLIQUE、HAMPATH、SUBSET-SUMPSPACE空间够用可以来回试TQBF、FORMULA-GAME这套框架什么时候该拿出来用三类场合最值。一是你要判断某个问题值不值得投入如果它落在一个已知的难类里与其硬啃不如换建模方式或者接受近似解。二是你要写解析器、写匹配引擎知道正则语言的边界在哪就不会试图用正则表达式去解析嵌套结构那是个经典误区。三是做技术选型时的沟通说「这个问题是 NP 完全的」比说「这个问题很难」要精确得多。什么时候别用日常业务代码里没人需要证明一段循环会不会停机你只要它跑完就行也不该拿 NP 完全去吓唬自己或别人输入规模小的时候指数算法一样跑得飞快。另外要当心把理论标签贴到工程实现上很多语言里的正则引擎带回溯最坏情况下会退化它不是 DFA所以「用了正则表达式」并不等于「保证线性时间」。我自己的习惯是每次动笔设计一个匹配或解析模块之前先在纸上写清楚输入的语言到底需要数数还是需要嵌套再决定用什么。有一次做日志字段抽取我图省事把整段嵌套内容塞进一条正则跑测试时数据量一大就直接卡死改成分层解析才消停。从那以后我每次碰到「看起来能用一行正则搞定」的需求都强制先问一遍它需不需要计数或者嵌套。希望这套分层也能帮你在下次遇到一个陌生问题时先量一量它到底站在哪一级台阶上。本文还有配套的精品资源点击获取