企业官网建设流程全解析

简介：面向计算机专业本科生与备考哈工程计算理论期末的复习者，这份文档把自动机理论、图灵机、语言理论、计算复杂度四大板块的核心结论压缩成可直接背诵的短句，适合考前突击与概念自查。压缩包内仅1个docx文件，约18KB，体积轻巧，手机与电脑均可直接打开翻阅。内容以命题形式串起关键判定：有穷自动机与正则语言的等价关系、正则语言在并、连结、星号运算下的封闭性、正则语言与上下文无关语言同下推自动机的对应、图灵机格局与图灵可识别/可判定语言的区分、判定器与丘奇-图灵论题、映射可归约与多项式时间归约，以及P、NP和SAT、3SAT、CLIQUE、HAMPATH等问题的归属与不可判定问题清单，可当作背诵提纲与查漏补缺的对照表。目前已有551人学习下载。

1. 计算理论到底在算什么：一台理想机器能做什么，不能做什么

很多人第一次翻开计算理论的讲义，看到满页的圆圈、箭头和 δ 转移函数，第一反应是这玩意儿跟每天写的代码到底有什么关系。其实计算理论问的问题特别朴素：一件事，一台理想化的机器到底能不能算出来；如果能，它得花多少时间和空间。它不研究某台具体电脑快不快，而是把所有计算抽象成「机器 + 输入 + 规则」三样东西，像拆一台机器看齿轮怎么咬合。正因为抽象得足够狠，它给出的结论能跨语言、跨硬件、跨几十年依然成立。搞懂它，你会拿到一把尺子：遇到一个新问题，先量一量它落在哪一层，再决定值不值得投入。

2. 有穷自动机与正则语言：一台「记不住数」的机器凭什么够用

很多人对「机器」的想象是一台会算数的电脑，能加能减能存变量。有穷自动机偏偏反着来：它没有任何草稿纸，全部家当就是「我现在处于哪个状态」。就这样一台抠门到极致的机器，却撑起了正则语言这一整层，也撑起了你每天都在用的字符串匹配。这一章要讲清的不是怎么画状态图，而是这层能力的天花板在哪、为什么刚好卡在这里。

2.1 有穷自动机长什么样：状态就是它全部的记性

把确定型有穷自动机（DFA）想成一台地铁闸机。它只有「锁着」和「开着」两种状态，你投一枚币，它就从锁着跳到开着；你推杆过去，它又弹回锁着。它不会记账，不会统计今天来了多少人，它只知道此刻自己是开还是关。形式化地说，一台 DFA 由五部分组成：一个有限的状态集合、一个输入字母表、一个转移函数、一个起始状态、一个接受状态集合。读完整个输入串后，如果停在接受状态里，就说它接受这个串；否则拒绝。

关键在于「有限」两个字。状态数是个固定常数，无论输入多长，机器内部能记住的信息量不变。这既是它的局限，也是它的优点——局限在于它记不住「前面已经读了多少个 a」，优点在于它的运行速度是严格线性的，输入翻十倍，时间也只翻十倍。

下面这段代码是一个最小的 DFA 模拟，它判断一个二进制串里 1 的个数是不是偶数。请留意注释里那句「唯一的内存」：

# 识别「1 的个数为偶数」的 DFA，全机只有两个状态 # state = 0 表示到目前为止读到偶数个 1，state = 1 表示奇数个 def is_even_ones(s: str) -> bool: state = 0 # 起始状态 for ch in s: # 读写头从左到右扫一遍，只能前进 if ch == '1': state = 1 - state # 每读到一个 1 就翻转：0 -> 1，1 -> 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_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 接受 w，M' 就在所有输入上停机；否则 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 包含于 NL，NL 包含于 P，P 包含于 NP，NP 包含于 PSPACE，而 PSPACE 等于 NPSPACE。最后这一步相等来自萨维奇定理：对于任何 f(n) ≥ n，非确定型图灵机用 f(n) 空间能判定的语言，确定型图灵机用 f(n) 的平方那么多空间也能判定。空间不像时间那样一非确定就爆炸成指数，这是空间与时间最不对称的地方。至于「完全」问题，PATH 是 NL 完全的，TQBF 一类是 PSPACE 完全的，它们各自的用处是给整个类画一条「在这个类里已经到顶」的线。

这套框架什么时候该拿出来用？三类场合最值。一是你要判断某个问题值不值得投入：如果它落在一个已知的难类里，与其硬啃，不如换建模方式，或者接受近似解。二是你要写解析器、写匹配引擎：知道正则语言的边界在哪，就不会试图用正则表达式去解析嵌套结构，那是个经典误区。三是做技术选型时的沟通：说「这个问题是 NP 完全的」，比说「这个问题很难」要精确得多。

什么时候别用？日常业务代码里，没人需要证明一段循环会不会停机，你只要它跑完就行；也不该拿 NP 完全去吓唬自己或别人，输入规模小的时候，指数算法一样跑得飞快。另外要当心把理论标签贴到工程实现上：很多语言里的正则引擎带回溯，最坏情况下会退化，它不是 DFA，所以「用了正则表达式」并不等于「保证线性时间」。

我自己的习惯是，每次动笔设计一个匹配或解析模块之前，先在纸上写清楚输入的语言到底需要数数还是需要嵌套，再决定用什么。有一次做日志字段抽取，我图省事把整段嵌套内容塞进一条正则，跑测试时数据量一大就直接卡死，改成分层解析才消停。从那以后，我每次碰到「看起来能用一行正则搞定」的需求，都强制先问一遍：它需不需要计数或者嵌套。希望这套分层，也能帮你在下次遇到一个陌生问题时，先量一量它到底站在哪一级台阶上。

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