简介：一份面向哈工程“计算理论”期末复习的计算理论知识点整理文档，内容覆盖自动机理论、图灵机、语言理论与计算复杂度四大模块，系统梳理正则语言与有穷自动机的等价关系、正则语言封闭性、非确定型与确定型自动机等价、上下文无关语言与下推自动机、图灵可判定与可识别、补图灵可识别、映射可归约等核心结论，并补充丘奇-图灵论题、多带与非确定型图灵机等价性、线性有穷自动机、多项式时间类与非确定型多项式时间类、可满足性问题等高频考点，便于考前快速背诵和查漏补缺。资源为单个Word文档，压缩包大小18KB，目前已获550人学习。文档以结论式条目和典型例子组织，集中列出可判定与不可判定语言的典型代表，适合期末突击、反复记忆，也可作为考研复习提纲。

1. 一学期没听懂的自动机理论，期末靠这份知识点清单能补回多少

计算理论这门课，考前一周开始复习的人十有八九都会经历同一个状态：书上的每条定理都认识，合上书做题全忘。这份《计算理论知识点.docx》解决的就是这个问题——它把自动机、图灵机、归约和复杂度类里最常考的结论整理成一条条可以直接背的陈述句，从"正则语言在并运算、连结、星号运算下封闭"到"SAT属于P当且仅当P=NP"，覆盖了计算理论期末的绝大部分考点。它适合两类人：一类是平时听课但没跟上、考前想快速建立知识框架的；另一类是已经复习过一轮、但分不清"哪个语言可判定、哪个归约到哪个"的备考者。它不是教材，是考前那几天最值得反复翻的一页纸。

2. 自动机与正则语言：DFA/NFA等价为什么是记忆锚点

2.1 五条封闭性定理怎么串成一条线

知识点清单里的第一句话是"如果一个语言被有穷自动机识别，则这个语言是正则语言"，这句话给出的是正则语言的定义方向。紧接着的第二到第五条则在讨论这类语言的封闭性：并运算、连结、星号运算下封闭，以及空集和空串这两个特殊元素的行为。很多人背这五条时是分开记的，结果考试考到一个集合表达式，比如"空集连接某个正则语言"，就卡住了。

更好的记忆方式是把它串成一句话：正则语言做并、连结、星号这三种操作，得到的仍然是正则语言；空集是连结运算的零元素，空串是连结运算的单位元。换句话说，空集连接到任何集合上的结果是空集，空串连接到任何串上不改变这个串。有了这个整体认知，考试时遇到"两个正则语言做差集是否正则"这类超纲问题，也能用"差集可以先取补再做交集，而补和交在封闭性推导上需要额外证明"来判断，至少不会把零元素和单位元的关系记反。

这一类题的实战判断顺序我一般是这样：先看题目给出的语言类是否为正则，再看做的运算是否落在并、连结、星号这三类里面，是就直接套结论；不是则回到自动机的构造去证明。期末复习时可以在草稿纸上把这些封闭性写成带方向箭头的图，比如"正则语言 —并/连结/星号→ 正则语言"，再把空集和空串的例子各写一个，两分钟就能过一遍。

2.2 非确定型与确定型等价：NFA/DFA/正则表达式三角

知识点里有两条看起来重复的结论："每一台非确定有穷自动机都等价于一台确定型有穷自动机"和"一个语言是正则的当且仅当有一台非确定型有穷自动机识别"。前者是讲两种机器的计算能力等价，后者是讲这种等价能力恰好刻画了正则语言。这两句话合起来，就有了一个很常用的三角形：DFA、NFA、正则表达式两两之间可以互相转换。

考试中最常出现的场景是给你一个语言描述，要求用有穷自动机证明它是正则的。这时大多数人的第一反应是画一个DFA，但有些语言用DFA画起来相当别扭，比如要求"第3个符号是0"或"不包含连续两个1"这类条件。遇到这种题目，先用NFA画会更顺手，画完再提子集构造法转成DFA交差。反过来，如果给的是正则表达式，比如(01)0(1∪0)，转NFA时按"单字符-连接-并-星号"的递归构造来拆，每一步只处理一个运算符，出错率比凭空画DFA低很多。

这里要特别提醒一个细节：NFA转DFA的子集构造法，最坏情况下状态数是指数级的。虽然考试计算量都不大，但如果你构造出来的DFA比NFA多出许多状态，先别急着怀疑自己算错——教材上"每一个NFA都能转成DFA"这句话只保证存在性，不保证状态数不膨胀。做题时如果只是判断"是否等价"，可以停留在NFA层面，不必强行转成DFA再验证。

2.3 ADFA、EDFA、EQDFA：可判定语言清单怎么区分记忆

清单里列了一串带下标的大写字母：ADFA表示"给定一个DFA和一个串，问它是否接受这个串"，ANFA把DFA换成NFA，AREX把输入换成正则表达式；EDFA问的是"这个DFA接受的语言是否为空"；EQDFA问的是"两个DFA是否接受同一个语言"。这五个问题全都是可判定语言，而且期末经常放在同一道选择题里，让你挑出"哪个不是可判定的"。

区分这组问题的关键不是背名字，而是理解每个问题的判定过程。ADFA直接模拟运行DFA，输入长度是n，运行时间是O(n)；ANFA可以先做子集构造再模拟，也可以同时维护多个当前状态；AREX把正则表达式转成NFA后走同一套逻辑；EDFA用一个图搜索从起始状态出发，看能不能到达任何接受状态——搜不到就是语言为空；EQDFA则要做一个对称差构造：两个DFA接受同一个串当且仅当它们的对称差DFA接受空语言。这样记下来，每个问题都有对应的算法直觉，比死记"ADFA可判定、EDFA可判定"要可靠得多。

顺带说一个经验：考试时遇到这些下标记号，先不要慌着做题，看一眼下标是什么。A开头的是"接受问题"（Acceptance），E开头的是"空性问题"（Emptiness），EQ开头的是"等价问题"（Equivalence），问题的输入已经写在名字里了。把下标翻译成人话，题目就简单了一半。

3. 图灵机判定与识别：可判定、可识别、循环的三态边界

3.1 格局与计算历史：图灵机的运行怎么"定格"

图灵机的形式定义可以写得非常简单，但要讨论"运行过程"时，只有状态和带子内容是不够的，还必须知道读写头当前指到哪个格子。于是知识点里给了一个组合概念：当前状态、当前带内容、读写头当前位置三者加在一起，叫作图灵机的格局。考试中如果需要你写格局序列，比如让一台图灵机在一个输入串上跑几步，你要把每一步的格局完整写出来，包括带上已经输出的部分、还没读到的部分，以及当前状态名。

计算历史则是格局的序列化形式，C1、C2、...、Cl，其中每一步都是上一步转移的结果，而且整个序列可以编码成一个串，交给另一台图灵机作为输入。这个"把运行过程编码成串"的想法是归约证明里的核心构件。我当年复习时不太理解为什么要定义计算历史，直到看到线性有界自动机相关问题的不可判定性证明，才明白计算历史是你在"无法直接运行一台机器"的情况下，唯一能构造出来的替代品。

还要记住三个边界结论：确定型机器在任何给定输入上最多只有一个计算历史；非确定型机器可能有多个计算历史，对应它的各个分支；如果机器在w上永不停机，那它既没有接受历史也没有拒绝历史。这三句话是判断题的常客，尤其是最后一句，很多同学会下意识认为"不停机意味着没有接受历史，但可能有拒绝历史"，实际上拒绝历史也要求停机在拒绝状态，不停机就什么都没有。

3.2 三种结果与判定器：为什么"可判定"比"可识别"强

在某个输入上运行一台图灵机，会得到三种结果：接受、拒绝或循环。图灵机与有穷自动机最大的不同就在这里——有穷自动机总是会读完输入后停机，图灵机则可能在一个循环里无限跑下去。于是就有了两个层次不同的概念：图灵可识别和可判定。如果一台图灵机在输入属于语言时一定接受，在不属于时可能拒绝也可能循环，那它识别这个语言；如果它永远在有限步内进入接受或拒绝状态，那它判定这个语言。

知识点里单独给判定器写了一句话："他们总是能决定接受还是拒绝"，语气里透着一种偏爱。为什么教材偏爱判定器？因为图灵机运行时间可能无限长，在实践中你根本分不清它是"还在算"还是"永远算不完"。判定器的价值就在于它从不给出第三种可能，每一个输入都明确落在接受或拒绝里。也正因如此，"可判定"是一个比"可识别"强得多的性质，可判定语言一定是可识别的，反过来则不成立。

考试中最常见的混淆发生在这里：题目问你某个语言是否图灵可识别，你下意识答了"不可判定"，甚至把不可判定和不可识别完全画等号。实际上不可判定的语言仍可能是可识别的，比如ATM的接受语言本身可识别，只不过补语言不可识别。记住这个例子，就能理解为什么"一个语言可判定当且仅当它既是图灵可识别的也是补图灵可识别的"这句话如此关键——它把可判定拆成了两个可识别的方向，两个方向都成立才算完。

3.3 形式化描述的三个层次与丘奇-图灵论题

知识点第11条描述了描述图灵机的三个层次。最底层叫形式化描述，把状态集、转移函数完整写出来，这是教科书里最繁琐、也最严谨的写法；中间层叫实现描述，用日常语言说明机器会怎么移动读写头、覆写带子符号，但不提供完整的状态转移表（我记得文档里写的正是"用日常用语来描述图灵机"）；最高层叫高水平描述，直接描述算法逻辑，连"用的是图灵机"这件事都可以不专门点出来。期末如果出"请用三种层次描述同一个图灵机"的题，你只需要遵循一个原则：形式化描述给状态转移图，实现描述讲读写头怎么动，高水平描述讲算法步骤，三层各说各的，不要混。

丘奇-图灵论题在这份清单里只占一句话："算法的明确定义"。它之所以重要，是因为它把"可计算"这个模糊的日常概念和"可以被某台图灵机计算"绑定在一起。注意论题不是定理，它是被广泛接受的工作假设——但目前所有已知计算模型在计算能力上都等价，所以至少到目前为止，用图灵机定义算法是最稳妥的做法。考试时如果问"为什么可以把算法理解为图灵机"，答"因为所有已知计算模型都和图灵机等价，且丘奇-图灵论题尚未被推翻"就够了。

3.4 多带与非确定型等价性：计算能力相同不等于效率相同

"每一个多带图灵机都等价于一个单带图灵机""非确定型图灵机都等价于一个确定型图灵机"，这两条经常被合并考察。它们给出的信息是计算能力层面上的等价，但模拟过程中的效率变化才是更深的地方。单带图灵机模拟多带图灵机，要在一条带上保存多条带的内容，用分隔符隔开，每次模拟一步都需要从带子的一头扫到另一头，所以如果原来的多带图灵机运行时间为t(n)，模拟它的单带图灵机运行时间约为O(t²(n))。

非确定型模拟确定型那一条更夸张，运行时间从t(n)涨到2^O(t(n))。道理也不难懂：非确定型图灵机在每个步骤都可能选择多条转移，模拟器要逐个尝试每个分支；最坏情况下所有分支都要探一遍，分支数随步数指数增长。期末复习时，把这两条时间损失结论放在一起记：单带模拟多带是平方损失，确定性模拟非确定性是指数损失。如果题目问"哪个损失更大"，答案永远是后者；如果问"两种模型是否等价"，答案仍是等价——只是效率不同而已。

4. 归约与不可判定：避坑与常见丢分点

4.1 坑1：把"图灵可识别"和"可判定"混为一谈

这个坑几乎每年都有人踩。现象是看到ATM就写"不可判定"，但题目接下来的追问是"它是否图灵可识别""它是否补图灵可识别"，于是就开始乱选。原因也很典型：复习时只记住了一张"不可判定名单"，把ATM、HALTTM、ETM、REGULAR_TM、EQ_TM这些东西的细节差异全部吞并了。但知识点里剥得很清楚：可判定当且仅当既可识别也可补识别，所以不可判定只是一张总标签，里面有"可识别但补不可识别""补可识别但不可识别""两者都不可识别"三种更细的分类。

解决办法是做题时先写三行判定式：是否可识别？是否补可识别？两者是否都成立？把三个答案写出来再下结论。比如ATM：可识别，补不可识别，所以不可判定且不可补识别。HALTTM：可识别、补可识别两条里只要有一个能否定，就能推出不可判定。养成这个"先写性质再写结论"的习惯，能直接掐断此类丢分。

4.2 坑2：映射可归约的方向搞反

现象很经典：题目说A≤mB，又告诉你A不可判定，很多人立刻得出结论"所以B不可判定"，但推理过程没写清楚，或者干脆想反了。根源在于映射可归约的定义里，注意力被"把A的实例转换成B的实例"这句话带偏了，以为"能转过去"意味着B更难。实际上A≤mB的含义是：有一个可计算函数f，使得w属于A当且仅当f(w)属于B。所以只要B有判定器，输入f(w)进去就能判断w是否属于A——等于用B的判定能力解决了A。

从这个角度看，归约的方向应该是"把难问题编码到目标问题上"。如果A不可判定，而A能归约到B，那B必须不可判定；否则就产生了一个A的判定器，矛盾。写证明题时我习惯先把这条逻辑链写出来：假设B可判定，则用B的判定器加归约f可以判定A，与A不可判定矛盾，因此B不可判定。这个模板比任何口诀都可靠。

4.3 坑3：把"清单里没列"当成"可判定"

知识点里列了很多可判定和不可判定的语言，可一到考试，题目只要换一个符号或者加一个修饰词，很多人就不能识别了。比如知道ETM不可判定，但问REGULAR_TM或EQ_TM就忘了；知道ELBA不可判定，但问ALL_CFG就不知道了。根本原因是复习时把这份清单当成孤立的名单在背，没有建立"为什么可判定/不可判定"的判断准则。

我的判断准则是这样的：如果一个问题本质上是"模拟一台机器在某个输入上运行，或解析一个有穷结构"，它大概率可判定，比如ADFA、ACFG，前者模拟DFA，后者用CYK解析文法；如果问题迫使你去判断"这台图灵机面对某些输入会不会停机"，它大概率不可判定，因为你要处理的是无限集合上的行为。把文档中每个带下标的记号按这个准则过一遍，你会发现可判定的那几个都很"具体"，不可判定的那几个都很"抽象"。考前用五分钟做这件事，比反复默写清单更有用。

4.4 坑4：乔姆斯基范式与PCP的理解偏差

现象是考试问"为什么上下文无关语言的成员性问题可判定"，你写不出关键步骤，或者见到文档里的"波斯地图对应实例"完全不知道是什么。原因在于两点：第一，不理解乔姆斯基范式的使用场景；第二，被一个音译笔误带偏了方向。

先解决第一个。乔姆斯基范式的意义在于，任何一个上下文无关文法都能转换成这种特殊形式——产生式要么是A→BC，要么是A→a。转换不是考点本身，但它让你能用动态规划（CYK算法）来解析字符串，这才是A_CFG可判定的实质。复习时画一下CYK的过程，理解"从单字符往上组合"的思路，比死记A_CFG可判定更有用。

第二个，"波斯地图对应实例"是文档里的笔误，实际对应的是Post Correspondence Problem，中文标准译名是"波斯特对应问题"，缩写PCP。它由一组骨牌对构成，问是否存在一个匹配序列让上下两行的字符串相等。PCP不可判定是结论，但它不属于正则或上下文无关那一族，而是归约证明里常见的终点。期末如果出判断题"PCP是否可判定"，答案是"不可判定"，但你要能想到为什么它和"判断图灵机是否停机"是同一难度级别。

5. 复杂度类：P/NP/PSPACE的层级图与考试怎么拿分

5.1 时间复杂性类：TIME、P、NP的直觉与常见判断

文档里定义了时间复杂性类TIME(t(n))：所有能被时间O(t(n))的图灵机判定的语言集合。这里有两个容易被忽略的细节——"判定"意味着机器必须在所有输入上停机，不是说某个输入上算得快就行；"O(t(n))"是一个渐近记号，具体常数不重要。P类就是所有多项式时间内可判定的语言类。为什么用多项式作为分界线？因为多项式对加法、乘法、复合都封闭，一个多项式时间算法调用另一个多项式时间算法，结果还是多项式时间，这让"归约"这个概念能自洽地定义出来。

NP的定义在文档里用的是"能被某个非确定型多项式时间的图灵机判定"。初学者很容易误解成"有一种机器能并行验证所有解"，但更实用的理解是"存在一个多项式时间的验证器"：你给出一个证书（比如SAT的一组赋值），验证器能在多项式时间内检查它是否可行。从这个角度看，P和NP的差别就在"直接求解"和"验证解"之间。考试如果问"SAT属于NP当且仅当？"答案就是"存在多项式时间验证器"，而不是"存在快速求解算法"。

5.2 空间复杂性类：萨维奇定理与PSPACE=NPSPACE

空间复杂性类SPACE(f(n))和NSPACE(f(n))的定义与时间版本平行，只不过把运行时间换成工作带使用的格子数。注意文档里的定义很严谨："被O(f(n))空间的确定型图灵机判定"，关键在"判定"二字——判定器在所有输入上都停机，这保证空间消耗不会出现无限增长。萨维奇定理说NSPACE(f(n)) ⊆ SPACE(f²(n))，其中f(n)≥n。这个结论的证明思路是非确定型机器在输入上的所有计算分支可以看成一个图，确定型机器在这个图上做深度优先搜索，只要记住当前分支节点和搜索深度，就能逐一遍历所有分支，而不需要同时保存整棵搜索树。

这条定理的一个直接推论是PSPACE=NPSPACE。比较一下时间复杂性那边：非确定型多项式时间对应的是NP类，而目前没有人知道NP是否等于P。空间那边却很干脆，平方还是多项式，非确定型空间并没有跳出多项式空间的边界。很多考生记不住这个对比，做题时错把"非确定型"和"指数增长"绑在一起。实际上，非确定型时间会指数增长，非确定型空间只有平方增长，这是空间比时间"更宽容"的根源。

5.3 对数空间归约与NL完全：画层级图比背列表更管用

知识点里列出了几个NL完全语言，比如PATH，说明"存在一个NL完全语言属于L当且仅当L=NL"。这里的归约是"对数空间归约"，不是多项式时间归约。对数空间转换器的定义很具体：一条只读输入带、一条只写输出带、一条可读写的工作带，工作带只能使用O(log n)个符号。因为工作带空间限制在对数规模，所以归约函数的每个输入位都只能被读有限次，这比多项式时间归约更严格。

期末复习时，我建议把L、NL、P、NP、PSPACE画成一条自下而上的包含链：L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE，同时注意NL=coNL也是一条重要结论（文档里没有细讲，但期末考试很可能提到）。在这条链的每个节点旁边，写上一个代表语言：PATH是NL完全的，RELPRIME属于P，SAT和3SAT属于NP，TQBF是PSPACE完全的。这样画一遍，比对着文档把字母背十遍都管用。

5.4 从3SAT到CLIQUE的归约路径

清单里有一条具体的归约结论：3SAT可以多项式时间归约到CLIQUE。这样一条归约的意义在于证明CLIQUE是NP完全的，考试则经常让你复述构造过程。构造思路是这样的：对3SAT的每个子句，为其中的三个文字各画一个节点；同一子句内两两连边；不同子句之间，只要两个文字不是互补的，就也连边。归约函数把这个图输出后，原公式可满足当且仅当图中存在一个大小为子句数的团。

复习这个归约时，注意两个考点。第一，图中的"团"恰好对应一条满足赋值里选中的文字集合；第二，归约是多项式时间的，因为图的节点数和边数都是公式规模的线性或平方级别。考试如果只考结论，你要能说出"3SAT是NP完全的，CLIQUE也是NP完全的，且3SAT≤pCLIQUE"；如果考证明，则要把"可满足当且仅当存在大小K的团"这个双向论证写完整，缺一个方向都要扣分。

6. 考前一周怎么用这份清单做自测：三张表加两轮默写

6.1 先把知识点转成三张自测表

第一张表按"语言类"组织，行写正则语言、上下文无关语言、可判定语言、图灵可识别语言，列写识别装置、封闭性、代表问题、是否可判定。填完后你会发现，正则语言对应有穷自动机和正则表达式，上下文无关语言对应下推自动机和乔姆斯基范式，可判定语言对应判定器，可识别语言对应一般图灵机。第二张表把文档里所有带下标的记号按"可判定、不可判定、可识别、不可识别"四个象限归类。第三张表画归约链：从3SAT出发，指向CLIQUE、HAMPATH、SUBSET-SUM，最终指向不可判定问题。

三张表的核心用法不是"填完就扔"，而是"闭卷填、开卷对"。我一般会先默写一遍，然后翻开文档逐条对照，错了就用红笔在原来的错误位置旁边补一行正确内容。这个过程比从头到尾读三遍文档都有效，因为强迫自己回忆本身就是一种检索练习，而检索练习的记忆效果远高于反复阅读。

6.2 两轮限时默写与考前一天的速度训练

第一次默写针对封闭性和等价性定理，比如"正则语言在哪些运算下封闭""多带图灵机与单带图灵机的关系""非确定型与确定型图灵机的关系"，限时十分钟。第二次默写针对可判定/不可判定语言清单，要求把ADFA、EDFA、ACFG、ATM、HALTTM、EQTM、PCP这些记号能否判定、能否识别、能否补识别全部写出来，限时五分钟。两轮默写都通过之后，再留出考前一小时做速度训练：随机抽文档里的五条结论，给自己两分钟，把相关的条件和结论完整复述出来。

计算理论这门课说到底就是一系列"若则"和"当且仅当"的关系网。我当年最惨的一次翻车，是把EQTM的不可判定性背得滚瓜烂熟，却在考场上被"EQTM是否可识别"问懵——因为我没有自己画过那张四象限分类表。从那以后，我每次复习这种以理论清单为主的科目，都会强制自己先做一遍"清单→关系图→分类表"的输出练习，再谈阅读。这份docx就放在手边，一条一条对着教材过，比从头到尾傻读三遍省时间得多，希望帮到你。

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