简介：这份《计算理论知识点.docx》面向备战计算理论期末考试的本科生，尤其适合哈工程等高校需要集中背诵、快速梳理考点的同学。内容围绕自动机理论、图灵机、语言理论、计算复杂度理论及其他核心概念展开，涵盖正则语言与有穷自动机的等价关系、上下文无关语言与下推自动机的对应、图灵可识别与图灵可判定语言的区分、判定器与格局的定义、映射可归约性、P与NP类、SAT与3SAT、列文-库克定理等高频考点，并以条目化方式罗列，便于对照记忆与考前突击。资源包共1个docx文件，约18KB，轻量易携带，可直接打印或导入笔记软件复习。目前已有548人学习下载，适合需要系统整理计算理论框架、查漏补缺的读者参考使用。
1. 计算理论期末救急：一份被哈工程学长称为“背下来你就好了”的知识点清单
如果你正在搜“计算理论期末 哈工程 该死的计算理论的理论 背下来你就好了”，大概率你和我当年一样，正对着一本厚得能防身的教材发愁。计算理论这门课的特点很鲜明：概念密度极高，证明链条极长，但考试和面试里真正反复出现的，其实是一批核心结论和它们之间的等价关系。这份《计算理论知识点.docx》就是把这些结论从教材里抽出来，按自动机、图灵机、语言层级、可判定性、归约、复杂度几个模块重新排了一遍。它不替代教材推导，但能让你在复习和做题时快速定位“这个语言属于哪一层”“这个判定问题到底可不可判定”。适合正在准备期末、考研复试，或者刚接触形式语言与自动机、想先抓住骨架的从业者。下面我按自己拆文档的顺序，把这份资料怎么用、参数怎么记、坑在哪讲清楚。
2. 自动机与正则语言：从 DFA 到正则表达式的等价链条怎么串
2.1 三条核心等价关系先立住
文档开篇前 11 条几乎都在讲正则语言。我一般先把这三句话背死：
- 被有穷自动机识别的语言是正则语言。
- 语言是正则的，当且仅当有一台非确定型有穷自动机（NFA）识别它。
- 语言是正则的，当且仅当有一个正则表达式描述它。
这三句合起来就是“DFA、NFA、正则表达式”三者等价。考试里常见的套路是给你一个 NFA 或正则表达式，让你说明它描述的语言是正则的；或者反过来，给你一个语言让你构造 DFA。文档里还补了一句“每一台非确定有穷自动机都等价于一台确定型有穷自动机”，这是子集构造法的理论依据，也是做构造题时敢下笔的底气。
2.2 封闭性怎么用：并、连结、星号
正则语言在并、连结、星号运算下封闭，这条看起来简单，但它是很多证明题的起点。比如题目问“正则语言经过某个操作后还是不是正则”，你首先想能不能用这三种基本运算表示出来。文档里还提到“空集连接到任何集合上得到空集，空串连接到任何一个串上不改变这个字符串”，这是运算的边界情况，构造自动机时如果遇到空串或空集，别在这里翻车。
2.3 上下文无关语言的位置
文档第 8 到 11 条把层级往上推了一层：任何一个上下文无关语言都可以用乔姆斯基范式的上下文无关文法产生；一个语言是上下文无关的当且仅当存在一台下推自动机（PDA）识别它；每一个正则语言都是上下文无关的。这几句连起来就是“正则 ⊂ 上下文无关”的严格表述。复习时我习惯画一条竖线：DFA/NFA/正则表达式 → PDA/CFG → 图灵机，每往上一层，识别能力变强，但封闭性和判定性质会变差。文档里没有展开乔姆斯基范式的转换步骤，但如果你考试要手写转换，常见做法是先把文法化成 A → BC 或 A → a 的形式，消 ε 产生式和单一产生式，这部分建议配合教材例题练两遍。
3. 图灵机与可判定性：格局、判定器、丘奇图灵论题
3.1 格局和三种运行结果
图灵机的“格局”是当前状态、当前带内容和读写头位置的组合。文档特别强调：在输入上运行一个 TM，可能出现三种结果——接受、拒绝或者循环。这里“循环”仅仅指机器不停机，不一定是永远重复同样的步骤。这个区分很关键，因为后面讲判定器和可判定性时，循环是最大的敌人。图灵机有两种方式不接受：进入拒绝状态，或者进入循环。考试里如果问“TM 不接受输入 w 是什么意思”，你要答出这两种可能，不能只写“拒绝”。
3.2 判定器为什么比识别器更受欢迎
文档第 4 条说得很直白：判定器有时候很难区分进入循环还是需要耗费很长时间的运行，因此我们更喜欢讨论所有输入都停机的图灵机，它们永远不循环，总是能决定接受还是拒绝。这就是“判定器”和“识别器”的分水岭。识别器接受的语言叫图灵可识别（递归可枚举），判定器判定的语言叫图灵可判定（递归）。文档里两条包含关系要记牢：每一个可判定语言都是图灵可识别的；但反过来不成立。另外，每一个多带图灵机等价于一个单带图灵机，非确定型图灵机也等价于确定型图灵机，这两条是后面复杂度类定义的基础。
3.3 丘奇图灵论题和描述层次
文档第 10 条把丘奇图灵论题称为“算法的明确定义”。第 11 条给了图灵机的三种描述层次：形式化描述（写出状态和转移函数）、实现描述（日常用语描述）、高水平描述（忽略带子和读写头管理）。我复习时的心得是：做题时先判断题目要求哪一层。如果题目说“给出形式化描述”，你就老老实实列状态表和转移函数；如果说“描述一台图灵机”，用实现描述就够了。很多同学在这里丢分，是因为把高水平描述当成了形式化描述，或者反过来把状态表写得太啰嗦。
3.4 可判定与不可判定语言清单
文档第 12 条是一张非常实用的清单，我把它整理成表格，方便对照记忆：
| 语言/问题 | 性质 |
|---|---|
| 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 的补 | 不可识别 |
这张表建议直接背。考试里常见题型是给你一个语言，问它属于哪一类。判断顺序我一般是：先看是不是正则，再看是不是上下文无关，再看是不是可判定，最后看是不是图灵可识别。文档里还提到“每一个上下文无关语言是可判定的”，这条把 CFG 和可判定性连起来了。
4. 归约与计算历史：映射可归约性怎么用来证明不可判定
4.1 映射可归约性的定义
文档第 18 到 22 条集中讲归约。核心定义是：用映射可归约性把问题 A 归约为问题 B，指的是存在一个可计算函数，将 A 的实例转换成 B 的实例。如果有了这个转换函数，就能用 B 的解决方案来解决 A。记作 A ≤m B。文档里给了两条重要性质：如果 A ≤m B 且 A 是不可判定的，则 B 也是不可判定的；如果 A ≤m B 且 B 是图灵可识别的，则 A 也是图灵可识别的。这两条是证明不可判定性的主要武器。
4.2 计算历史与线性有穷自动机
文档第 15 到 17 条讲计算历史和线性有穷自动机（LBA）。接受计算历史是一个格局序列 C1, C2, …, Cl，其中 C1 是起始格局，Cl 是接受格局，每个 Ci 都是 Ci-1 的结果。确定型机器在任何输入上最多只有一个计算历史，非确定型机器可能有多个。LBA 是一种受限图灵机，读写头不能离开输入带区域。文档里说 A_LBA 是可判定的，但 E_LBA 是不可判定的，这个对比经常考。
4.3 归约的实操思路
如果你要手写一个归约证明，我一般按这个步骤走：
- 明确已知不可判定的问题，比如 A_TM 或 HALT_TM。
- 构造一个可计算函数 f，把已知问题的实例转换成目标问题的实例。
- 证明 w ∈ A_TM 当且仅当 f(w) ∈ 目标问题。
- 引用“若 A ≤m B 且 A 不可判定，则 B 不可判定”。
文档里没有展开具体归约的构造，但第 23 条给了一个重要结论：EQ_TM 既不是图灵可识别的，也不是补图灵可识别的。这条经常作为选择题或判断题出现，记住结论能省不少推导时间。
5. 复杂度类 P、NP、PSPACE：时间与空间复杂性的边界
5.1 时间复杂性类和 P、NP
文档第 24 到 30 条讲时间复杂性。TIME(t(n)) 是由时间 O(t(n)) 的图灵机可判定的所有语言的集合。P 类是在多项式时间内可判定的语言类。NP 是一个语言在 NP 中，当且仅当它能被某个非确定型多项式时间的图灵机判定。文档里给了一句很精炼的对比：P = 成员可以快速判定的语言类，NP = 成员可以快速验证的语言类。PATH、RELPRIME 属于 P，每一个上下文无关文法都是 P。HAMPATH、CLIQUE、SUBSET-SUM、SAT、3SAT、UHAMPATH 属于 NP。
5.2 多项式时间归约与 NP 完全
文档第 32 到 35 条讲多项式时间归约。语言 A 多项式时间映射可归约到 B，记作 A ≤p B，若存在多项式时间可计算函数 f，对于每一个 w，w ∈ A 当且仅当 f(w) ∈ B。列文-库克定理说 SAT ∈ P 当且仅当 P = NP，这是 NP 完全理论的基石。3SAT 多项式时间可归约到 CLIQUE，这条常用来证明 CLIQUE 是 NP 完全的。
5.3 空间复杂性类和萨维奇定理
文档第 36 到 43 条讲空间复杂性。SPACE(f(n)) 是被 O(f(n)) 空间的确定型图灵机判定的语言集合，NSPACE(f(n)) 是非确定型版本。萨维奇定理说 NSPACE(f(n)) ⊆ SPACE(f²(n))，其中 f(n) ≥ n。文档最后给了一条包含链：L ⊆ NL ⊆ coNL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE。这条链建议直接背，考试里判断语言所属复杂度类时非常有用。TQBF、FORMULA-GAME、GG 是 PSPACE 完全的，PATH 是 NL 完全的。对数空间转换器和对数空间归约的定义也在文档里，如果考到 L 和 NL 的完全性，这部分是必看的。
6. 避坑与排查：背计算理论时最容易翻车的五个地方
6.1 把“图灵可识别”和“图灵可判定”混为一谈
现象：题目问“这个语言是不是可判定的”，你答“是图灵可识别的”。原因：识别器允许循环，判定器要求所有输入都停机。解决：看到“可判定”三个字，先问自己“机器会不会循环”，如果可能循环，那就只是可识别，不是可判定。
6.2 归约方向写反
现象：证明 B 不可判定时，你构造了从 B 到 A 的归约。原因：映射可归约性的方向是 A ≤m B，用 B 的解决方案解决 A。要证明 B 不可判定，应该从已知不可判定的 A 归约到 B。解决：写归约前先默念“已知不可判定 → 目标问题”，方向别反。
6.3 忘记空串和空集的边界
现象：构造自动机或文法时，空串处理错误。原因：文档里明确说空集连接到任何集合上得到空集，空串连接到任何一个串上不改变这个字符串。解决：遇到 ε 和 ∅ 时单独列一行检查，别默认它们和普通符号一样。
6.4 复杂度类包含链记混
现象：把 NP 和 PSPACE 的顺序写反。原因：包含链 L ⊆ NL ⊆ coNL ⊆ P ⊆ NP ⊆ PSPACE ⊆ NPSPACE 需要整体记忆。解决：按“空间从小到大、时间从短到长”的顺序背，P 在 NP 前面，NP 在 PSPACE 前面。
6.5 丘奇图灵论题当成定理用
现象：证明题里写“根据丘奇图灵论题，这个函数是可计算的”。原因：丘奇图灵论题是论题，不是定理，它不能被证明。解决：要证明可计算性，老老实实构造图灵机或给出算法描述，别拿论题当挡箭牌。
7. 进阶用法：把知识点清单变成考前 48 小时冲刺表
这份文档最大的价值不是让你从零学计算理论，而是帮你把已经学过的东西快速串起来。我自己的用法是：考前 48 小时，先花 2 小时把第 2 章到第 5 章的表格和包含链默写一遍，再用 3 小时做三件事。
第一，把文档第 12 条的可判定/不可判定清单抄到一张 A4 纸上，左边写语言，右边写性质，遮住右边自测。第二，把第 24 到 43 条的复杂度类定义和包含链画成一条竖线，每层写两个代表问题，比如 P 层写 PATH 和 RELPRIME，NP 层写 SAT 和 CLIQUE，PSPACE 层写 TQBF。第三，把归约的定义和两条性质（A ≤m B 且 A 不可判定则 B 不可判定；A ≤m B 且 B 图灵可识别则 A 图灵可识别）默写三遍，直到能不看文档写出来。
如果你时间更紧，只剩一个晚上，那就只背三样东西：正则/上下文无关/图灵可识别的层级关系、可判定与不可判定清单、P/NP/PSPACE 包含链。这三样覆盖了计算理论期末 70% 以上的结论题。至于证明题，把文档里“当且仅当”的句子挑出来，每一句试着从两个方向各推一遍，推不动就回去翻教材对应章节。
从那以后我每次带人复习计算理论，都强制先过一遍这份清单再碰真题，因为概念不清的时候做题，错题会反复错在同一类等价关系上。希望这份整理能帮你少熬两个通宵。
本文还有配套的精品资源，点击获取
