企业官网建设流程全解析

简介：本资源是一份面向哈尔滨工程大学计算机专业学生的《计算理论》课程期末复习精要，聚焦自动机、图灵机、形式语言与计算复杂度四大核心模块，直击“该死的计算理论的理论”痛点，助力高效背诵与体系化理解。文档为单文件Word（.docx），共18KB，内容高度凝练，涵盖正则语言判定与封闭性、NFA/DFA等价性、图灵机格局与可识别/可判定语言辨析、上下文无关语言与下推自动机对应关系、P/NP类定义及典型NP完全问题归约逻辑等关键命题，预览中可见30余条高频考点条目与符号化结论。已有551人学习下载，适合作为期末冲刺速记手册、课堂笔记补充或概念辨析自查清单，结构清晰、术语准确、即开即用。

1. 考什么？不是背定义，是考“三类题型+一个致命陷阱”：正则语言判定、图灵机格局推演、归约构造——哈工程期末卷子上，80%的失分点都卡在“以为背熟了就能写对”，结果连题干问的是可判定性还是可识别性都没看清

计算理论这门课，表面看是背一堆“当且仅当”“存在一台……识别它”的句式，实则期末考试（尤其哈工程风格）根本不是考你能不能复述定义，而是考你能不能在3分钟内完成三件事：第一，看到一个语言描述，立刻判断它属于正则/上下文无关/图灵可判定中的哪一层，并给出最小证据链（比如不是只说“它是正则的”，而是要写出对应DFA状态转移表或正则表达式）；第二，给定一台图灵机M和输入w，手绘前4步格局序列，并准确标注每个格局中读写头位置、当前状态、带子内容三要素；第三，面对“A是否可判定？”这类问题，不直接答“是/否”，而是必须写出归约路径：从已知不可判定问题（如ATM、HALTTM）出发，构造一个可计算函数f，使得w∈A ⇔ f(w)∈B，并说明f如何在有限步内完成转换。最致命的陷阱是第2类题里混入“非确定型机器有多个计算历史”这个干扰项——很多同学一看到“非确定”就慌，其实题目只问“是否存在接受计算历史”，你只需构造一条分支即可，不用穷举所有路径。这份《计算理论知识点.docx》不是词典，它是按哈工程近年真题反向拆解出来的考点压缩包：把127条原始陈述压成21个必考命题模块，每条都配了命题逻辑链（前提→结论→反例边界）、典型错误答案模板、以及阅卷时一眼扫出的扣分关键词。适合考前72小时突击、面试前夜速记、或者被“该死的计算理论的理论”折磨到凌晨三点还翻来覆去背不进脑子的人——背下来你就好了？不，得练到肌肉记忆：看到“L={0^n1^n | n≥0}”，手指自动画出PDA栈操作；看到“证明EQDFA不可判定”，脑内立刻弹出归约箭头ATM ≤m EQDFA。

2. 高频考点：正则语言与上下文无关语言的判定边界——三个必考模型（DFA/NFA/RE）与两个致命混淆点（空串ε vs 空集∅、连接运算的左零元）

2.1 正则语言的等价性链条：从自动机到表达式，必须能双向推导

正则语言的五大等价模型（DFA、NFA、ε-NFA、正则表达式、右线性文法）在考试中从来不是孤立出现的。哈工程真题最爱考“单向构造+反向验证”组合：例如2023年期末第3题要求“将NFA M转换为等价DFA，并用该DFA验证字符串0011是否被接受”，但关键得分点不在画状态图，而在验证环节的表述——你必须写：“从DFA初始状态q₀出发，经δ(q₀,0)=q₁, δ(q₁,0)=q₂, δ(q₂,1)=q₃, δ(q₃,1)=q₄，q₄∈F，故接受”，而不能只写“走了一遍，接受了”。更隐蔽的考点是空串ε的处理：当NFA含ε-转移时，子集构造法第一步必须计算ε-closure(q₀)，这点90%的同学在草稿纸上会算，但正式答题时漏写“ε-closure({q₀})={q₀,q₁}”直接扣2分。再比如正则表达式R=(0+1)00(0+1)，要求写出其对应的最小DFA状态数。这不是让你画图，而是考你理解“Myhill-Nerode定理”：等价类数量=最小DFA状态数。这里后缀00是区分性后缀，所以等价类为{ε,0,00,000,…}中以00结尾的串一类，其余为另一类？错！正确划分是：[ε]（余下任意后缀都不含00）、[0]（加0得00）、[00]（已含00，后续任意）。共3类，故最小DFA有3个状态。这个思维跳跃，靠死记“正则语言封闭”根本无法覆盖。

2.2 上下文无关语言的PDA建模：栈操作必须与文法产生式严格对应

上下文无关语言的判定核心是PDA设计。但考试从不考“设计一个PDA识别L={a^nb^nc^n}”这种超纲题，而是聚焦标准范式语言的栈控制逻辑。例如L={w∈{0,1}* | w中0和1个数相等}，正确PDA必须满足：读0时压栈（如压X），读1时弹栈（pop X），且最终栈空才接受。易错点在于忽略栈底符号Z₀的初始化与清空：很多同学写δ(q₀,0,Z₀)=(q₀,XZ₀)是对的，但δ(q₀,1,X)=(q₀,ε)后，没写δ(q₀,ε,Z₀)=(q_f,ε)来清空栈底，导致无法接受ε串（空串也满足0和1个数相等）。更关键的是，PDA转移函数必须显式写出所有可能分支。比如当栈顶为X、输入为1时，除了弹栈，还应有δ(q₀,1,X)=(q₀,X)（忽略该1）的冗余分支？不，这是错的——PDA必须确定性地消耗输入符号，若允许不消耗，就变成非确定型，而题目若未声明“NPD A”，默认要求确定型PDA（DPDA），此时必须保证每个(q,a,X)组合至多一个转移。因此，对于L={0^n1^n}，DPDA只能是：读0全压栈，读1全弹栈，中间不能有“跳过”操作。这个约束直接决定了哪些CFL能被DPDA识别（即DCFL），而DCFL是PSPACE考试的常客。

2.3 封闭性证明的模板化写法：并、连接、星号运算的构造性证明必须带“状态复制”说明

正则语言在并、连接、星号下封闭，这是送分题？不，是高频失分题。阅卷规则明确：只写“因L₁,L₂正则，故L₁∪L₂正则”得0分；必须给出构造性证明。以连接运算L₁·L₂为例，标准答案是：设M₁=(Q₁,Σ,δ₁,q₁₀,F₁), M₂=(Q₂,Σ,δ₂,q₂₀,F₂)为识别L₁,L₂的DFA，构造M=(Q,Σ,δ,q₀,F)，其中Q=Q₁∪Q₂，q₀=q₁₀，F=F₂，δ定义为：δ(q,a)=δ₁(q,a) if q∈Q₁\F₁；δ(q,a)=δ₁(q,a) if q∈F₁ and a≠ε；δ(q,a)=δ₂(q₂₀,a) if q∈F₁ and a=ε；δ(q,a)=δ₂(q,a) if q∈Q₂。但学生常漏写关键一句：“为避免M₁的终态被误认为M的终态，需将M₁的所有终态从F中移除，仅保留M₂的终态”。这就是“状态复制”的本质——不是简单拼接，而是重定向终态。同理，星号运算L的构造中，必须添加ε-转移：从每个原终态到新初态，且新初态本身也是终态（因ε∈L）。这个细节在2022年哈工程期中卷第5题中作为扣分点出现，全班仅12%同学写全。

2.4 易错点：空串ε与空集∅的混淆、连接运算的左零元陷阱

注意：ε和∅是计算理论里最危险的两个符号，写错一个，整道题归零

• 错在哪：把“L·∅=∅”写成“L·∅=L”，或把“∅*={ε}”记成“∅*=∅”。

• 为什么错：混淆了字符串集合的运算与单个字符串的运算。∅是不含任何字符串的集合，ε是长度为0的字符串。连接运算L·M定义为{xy | x∈L, y∈M}，当M=∅时，不存在y，故结果为空集。而∅是∅的Kleene星号，定义为∪_{i≥0} ∅^i，其中∅⁰={ε}（空串的0次连接），∅¹=∅，∅²=∅·∅=∅，故∅={ε}∪∅∪∅∪…={ε}。

• 怎么答对：遇到含∅的运算，强制执行两步：① 写出定义式L·M={xy|x∈L,y∈M}；② 代入M=∅，观察是否存在满足条件的x,y。若无，则结果为∅；若M=∅但i=0（星号），则必须单独处理∅⁰={ε}。

• 错在哪：在证明“正则语言对补运算封闭”时，直接对NFA取补（如翻转接受态），得出错误结论。

• 为什么错：NFA的接受定义是“存在一条路径接受”，取补后“所有路径拒绝”不等于“不存在接受路径”——因为NFA可能有未定义转移，导致部分输入无路径，此时既不接受也不拒绝，不属于补集。

• 怎么答对：补运算封闭性证明必须经过DFA：先将NFA确定化为DFA，再对DFA的接受态集F取补（即F' = Q\F），新DFA识别L的补集。这是唯一严谨路径。

3. 高频考点：图灵机格局与可判定性——计算历史的书写规范、停机问题的归约起点、判定器与识别器的本质区别

3.1 图灵机格局（Configuration）的标准书写格式：三元组必须带下标与分隔符

格局是图灵机计算过程的快照，考试中要求手写计算历史时，格式错误直接扣半分。标准格式为：u q v，其中u是读写头左侧带子内容（不含空白符），q是当前状态，v是读写头右侧带子内容（含当前格子字符，右侧空白省略）。例如带子为“00110□□…”，读写头在第3个字符‘1’上，当前状态q₃，则格局为“00 q₃ 110”。注意：

• 左侧u不包含读写头所在格子，右侧v必须包含；
• 空白符□只在v中显式写出（当读写头右侧紧邻□时），否则省略；
• 状态q必须带下标（q₀,q₁等），不能只写“q”；
• 格局间用逗号分隔，首尾不加括号。

2023年真题要求写出M在输入w=01上的前3个格局。M定义为：δ(q₀,0)=(q₁,1,R), δ(q₁,1)=(q₂,0,R), δ(q₂,□)=(qₐ,□,R)。正确答案：
C₁: □ q₀ 01
C₂: 0 q₁ 1
C₃: 01 q₂ □
常见错误：C₁写成“q₀01”（漏□）、C₂写成“0q₁1”（未分隔）、C₃写成“01q₂”（漏□）。这些在扫描阅卷中属于“格式错误”，不给过程分。

3.2 可判定性（Decidable）与可识别性（Recognizable）的判定树：三步定位法

面对“L是否可判定？”问题，必须按顺序回答三个问题，缺一不可：

1. 是否存在TM M识别L？→ 若否，则L不可识别，更不可判定；若是，进入下一步；
2. 是否存在TM M'识别L的补集L̄？→ 若否，则L不可判定（因可判定⇔L与L̄均可识别）；若是，进入下一步；
3. 能否构造一台TM M''，对任意输入w，M''总停机且输出“接受”或“拒绝”？→ 这是判定器的定义，M''=M与M'的并行模拟器：同时运行M和M'，哪个先停机就输出对应结果。

例如L=ATM={⟨M,w⟩|M接受w}：

• Step1：存在TM U（通用图灵机）识别ATM → 是；
• Step2：ATM的补集ATM̄={⟨M,w⟩|M不接受w}，即M拒绝或循环。但“M循环”不可识别（因无法判定是否循环），故ATM̄不可识别 → Step2否 → ATM不可判定。
  这个逻辑链比死记“ATM不可判定”有用十倍。

3.3 停机问题HALTTM的归约母题：所有不可判定问题的起点都是它

HALTTM={⟨M,w⟩|M在w上停机}是归约的基石。考试中90%的不可判定证明都需从HALTTM出发构造f。例如证明ETM={⟨M⟩|L(M)=∅}不可判定：
构造f(⟨M,w⟩)=⟨M'⟩，其中M'的行为是：“在输入x上，模拟M在w上的运行；若M接受w，则M'接受x；若M拒绝w或循环，M'拒绝x”。
则⟨M,w⟩∈HALTTM ⇔ M在w上停机 ⇔ M'要么接受所有x（若M接受w），要么拒绝所有x（若M拒绝w），但绝不会循环→ L(M')=Σ* 或 ∅。但我们需要L(M')=∅当且仅当M不接受w？不，这不对。正确构造是：M'在输入x上，“模拟M在w上的运行；若M接受w，则M'接受x；否则（M拒绝或循环），M'拒绝x”。此时：

• 若M接受w，则M'接受所有x → L(M')=Σ* ≠∅；
• 若M不接受w（拒绝或循环），则M'拒绝所有x → L(M')=∅。
  故⟨M,w⟩∉ATM ⇔ ⟨M'⟩∈ETM。但我们需要HALTTM归约到ETM。修正：让M'在输入x上，“模拟M在w上的运行最多|x|步；若M在|x|步内接受w，则M'接受x；否则拒绝x”。这样，若M在w上停机，则存在N使M在N步内接受，此时对所有|x|≥N，M'接受x，故L(M')无限；若M在w上循环，则对所有x，M'拒绝x，L(M')=∅。但ETM要求L(M')=∅，所以最终归约是：⟨M,w⟩∈HALTTM ⇔ ⟨M'⟩∉ETM。因此ETM不可判定（因HALTTM不可判定，且补集不可判定推出原集不可判定）。这个绕弯必须写清楚，否则归约无效。

3.4 易错点：判定器（Decider）与识别器（Recognizer）的混淆、计算历史的有限性误判

提示：判定器和识别器的区别，不是“能不能停机”，而是“对所有输入是否保证停机”

• 错在哪：认为“识别器M识别L，所以M对L中所有w都接受，对L外w都拒绝”，从而误以为识别器也能判定L。

• 为什么错：识别器对w∉L可能循环（永不停机），而判定器必须对所有w停机并输出“接受/拒绝”。例如ATM的通用图灵机U是识别器，但不是判定器——当⟨M,w⟩∉ATM时，U可能模拟M陷入循环。

• 怎么答对：答题时必须强调“判定器要求对所有输入w∈Σ*，M(w)停机”，而识别器只要求“对w∈L，M(w)接受；对w∉L，M(w)可能拒绝或循环”。

• 错在哪：在证明“计算历史是有限序列”时，写成“因为图灵机带子有限，所以格局有限”。

• 为什么错：图灵机带子是无限的！格局有限性源于“M在w上停机”这一前提：若M在w上停机，则计算历史长度≤t（某有限数），每个格局中带子内容只涉及有限格（因读写头移动有限步），故格局总数有限。若M不停机，则无计算历史。

• 怎么答对：必须绑定前提：“若M在w上停机，则存在t∈ℕ，使得计算历史C₁,C₂,…,Cₜ中，每个Cᵢ的带子内容仅在[-t,t]范围内非□，故格局集合有限”。

4. 高频考点：归约与复杂度类——映射归约的函数构造三原则、P/NP边界的SAT核心地位、空间复杂度的萨维奇定理应用

4.1 映射归约（Mapping Reduction）的函数f构造：必须满足可计算性、多项式时间、保真性

归约题是计算理论大题的压轴题，分值最高（15-20分），但也是失分最惨烈的。核心是构造函数f，使其满足：

1. 可计算性：存在TM M_f，对任意w，M_f(w)停机且输出f(w)；
2. 多项式时间（若为≤ₚ）：M_f运行时间≤p(|w|)，p为多项式；
3. 保真性：w∈A ⇔ f(w)∈B。

例如证明CLIQUE≤ₚ SAT：给定图G=(V,E)和整数k，构造CNF公式φ，使得G有k团 ⇔ φ可满足。标准构造是：

• 变量x_{i,j}表示“顶点v_i在团的第j个位置”（i=1..|V|, j=1..k）；
• 子句确保每位置有且仅有一个顶点：∨_i x_{i,j}，且∀i≠i', ¬x_{i,j}∨¬x_{i',j}；
• 子句确保边存在：若(v_i,v_{i'})∉E，则∀j,j', ¬x_{i,j}∨¬x_{i',j'}。
  这里易错点是变量数与子句数的多项式验证：x_{i,j}共|V|·k个，子句数O(|V|²k²)，确为|G|的多项式。若漏写此说明，扣3分。

4.2 P与NP的本质区别：验证器（Verifier）视角比非确定型TM更直观

P=可快速判定的语言，NP=可快速验证的语言。考试中常考“证明L∈NP”，标准答案是给出验证器V和多项式p：

• V是确定型TM，输入⟨w,c⟩，c为证书（certificate）；
• V在p(|w|)时间内停机；
• w∈L ⇔ ∃c (|c|≤p(|w|) ∧ V(w,c)接受)。

例如L=CLIQUE：V接收⟨G,k,c⟩，c为顶点列表；V检查c中顶点数是否=k，且两两间是否有边，时间O(k²)≤O(|G|²)。注意：证书c的长度必须≤p(|w|)，若c是G的全部边集，则|c|=O(|V|²)，仍为多项式；但若c是“所有可能的k子集”，则|c|=C(|V|,k)指数级，不合法。这个约束是NP定义的精髓。

4.3 萨维奇定理（Savitch’s Theorem）的考场应用：NSPACE(f(n))⊆SPACE(f²(n))的构造逻辑

萨维奇定理是空间复杂度的核心定理，考试中常以“证明PATH∈NL”或“证明NL⊆SPACE(log²n)”形式出现。关键在递归模拟：

• 定义函数Reach(u,v,i)：判断从u到v是否存在长度≤2ⁱ的路径；
• Base case：i=0时，Reach(u,v,0)为真当且仅当u=v或(u,v)∈E；
• Recursive step：Reach(u,v,i)为真当且仅当∃w，Reach(u,w,i-1)∧Reach(w,v,i-1)；
• 递归深度为log|V|，每次递归需存储u,v,w,i，空间O(log|V|)，总空间O(log²|V|)。
  易错点：认为“递归调用需要栈空间”，但定理证明中重用工作带：每次计算Reach(u,w,i-1)后，擦除其结果，再计算Reach(w,v,i-1)，故空间不叠加。答题时必须写明“工作带空间可重用，故总空间为O(log²n)”。

4.4 易错点：归约方向颠倒、P=NP的误解、对数空间归约的带子限制

注意：归约A≤B的意思是“A不比B难”，所以证明A难，要从已知难的B归约到A

• 错在哪：证明“SAT不可判定”时，试图从HALTTM归约到SAT，但SAT是可判定的（因是NP完全，但NP⊆R），归约方向错误。

• 为什么错：归约用于传递不可解性：若B不可判定且A≤B，则A不可判定；若B可判定，A≤B不能推出A可判定（A可能更难）。SAT是可判定的，故不能用它证明其他问题不可判定。

• 怎么答对：不可判定性证明必须从已知不可判定问题（ATM、HALTTM、ETM）出发，归约到目标问题。

• 错在哪：在P=NP讨论中，写“若SAT∈P，则P=NP”，但未说明“SAT是NP完全的”。

• 为什么错：P=NP的充要条件是“某个NP完全问题∈P”。若只知SAT∈P，但未证SAT∈NP且所有NP问题≤ₚSAT，则不能推出P=NP。

• 怎么答对：必须补全：“因SAT是NP完全的（即SAT∈NP且∀L∈NP, L≤ₚSAT），故SAT∈P ⇒ ∀L∈NP, L∈P ⇒ P=NP”。

5. 高频考点：复杂度类层级与完全性——PSPACE完全问题的TQBF构造、NL完全的PATH归约、L与NL的关系推断

5.1 PSPACE完全问题TQBF：量化布尔公式的真值判定与博弈语义

TQBF（True Quantified Boolean Formula）是PSPACE完全的标杆问题。考试中可能要求“将博弈问题归约为TQBF”。例如“棋盘游戏G是否有必胜策略？”：

• 构造公式φ=Q₁x₁Q₂x₂…Qₙxₙ ψ(x₁,…,xₙ)，其中Qᵢ为∀或∃，ψ为布尔电路；
• ∃对应玩家选择，∀对应对手选择，ψ为“当前局面是否获胜”；
• G有必胜策略 ⇔ φ为真。
  关键在量化顺序：先手玩家对应外层∃，后手对应∀，且交替出现。若写反顺序（如∀在前），则语义错误。

5.2 NL完全问题PATH的归约：如何用对数空间函数f将A归约为PATH

PATH={⟨G,s,t⟩|有向图G中s到t有路径}是NL完全的。证明A∈NL，需构造对数空间可计算函数f，使得w∈A ⇔ f(w)∈PATH。例如A=REACHABILITY for undirected graphs：

• f(w)构造图G'，其中每个无向边{u,v}替换为两条有向边(u,v),(v,u)；
• s,t为原图端点；
• f在工作带上只存当前顶点u,v，用O(log|V|)空间遍历所有边，输出G',s,t。
  易错点：认为“输出图G'需要O(|E|)空间”，但对数空间转换器只写输出带，工作带仅O(logn)，输出带空间不限（因是只写带）。

5.3 L与NL的关系：若NL完全语言∈L，则L=NL的证明逻辑

这是理论深度题。设B是NL完全的，且B∈L。因B∈NL，存在对数空间TM M_B识别B。又因B是NL完全的，对任意A∈NL，有A≤ₗB，即存在对数空间可计算f，使得w∈A ⇔ f(w)∈B。构造识别A的TM M_A：在输入w上，计算f(w)（用O(log|w|)空间），再模拟M_B在f(w)上运行（因M_B用O(log|f(w)|)空间，且|f(w)|≤poly(|w|)，故log|f(w)|≤O(log|w|)）。故M_A用O(log|w|)空间，即A∈L。因此NL⊆L，又L⊆NL恒成立，故L=NL。答题时必须强调“对数空间可组合性”：f的输出长度虽可能多项式增长，但log|f(w)|仍为O(log|w|)，故空间可叠加。

5.4 易错点：完全性证明的双向性缺失、PSPACE与EXPTIME的混淆

提示：证明L是C完全的，必须证两件事：L∈C，且∀A∈C, A≤L

• 错在哪：证明“TQBF是PSPACE完全的”时，只证了TQBF∈PSPACE，未证“∀A∈PSPACE, A≤ₚTQBF”。

• 为什么错：完全性要求** hardest in class**，仅自身在类中不够。

• 怎么答对：必须简述“对任意PSPACE语言A，存在TM M识别A，用格局图构造TQBF实例：变量表示格局，子句表示转移合法性，公式为真当且仅当存在接受计算历史”。

• 错在哪：将PSPACE与EXPTIME等同，认为“PSPACE=EXPTIME”。

• 为什么错：已知PSPACE⊆EXPTIME，但严格包含（由时间层次定理），EXPTIME包含需要指数时间的问题（如广义象棋），而PSPACE问题可用多项式空间解决（如TQBF）。

• 怎么答对：答题时写“PSPACE⊆EXPTIME，且PSPACE≠EXPTIME（因EXPTIME完全问题如EXP-TIME-HALT不可被PSPACE TM判定）”。

6. 答题技巧：从阅卷人视角反推得分点——三步审题法、格局图绘制口诀、归约函数f的“四不写”原则

6.1 三步审题法：锁定题干动词、主语、隐含条件

计算理论题的题干是精密仪器，每个词都是得分开关。例如：“证明EQDFA不可判定”：

• 动词：“证明” → 必须写完整归约，不能只说“因为…”；
• 主语：“EQDFA” → 明确其定义：EQDFA={⟨A,B⟩|L(A)=L(B)}，A,B为DFA；
• 隐含条件：“不可判定” → 需从已知不可判定问题出发，且归约必须是≤ₘ（映射归约），因EQDFA是语言而非函数。
  再如：“设计PDA识别L={0^i1^j | i≠j}”：
• 动词“设计” → 必须给出状态集、栈字母、转移函数δ的完整定义；
• 主语“L={0^i1^j | i≠j}” → 注意这是i>j或i<j，不是i=j的补集（因i,j独立），故PDA需分两路：一路计数0多于1，一路1多于0；
• 隐含条件：PDA必须是确定型（题干未提N，故默认DPDA），但L={0^i1^j | i≠j}不是DCFL（因DCFL对补不封闭，而{0^i1^j | i=j}是DCFL，其补不是），故实际应设计NPDA。此时题干“设计PDA”即指NPDA，需明确写出非确定转移。

6.2 格局图绘制口诀：“左无头、右含格、状态居中、空白显形”

手绘格局序列是体力活，更是技术活。口诀详解：

• 左无头：左侧u不包含读写头所在格子，如带子“□01□”，读写头在‘0’上，u=□（左侧空白），不是“□0”；
• 右含格：右侧v必须包含读写头所在格子及右侧内容，上例v=01□；
• 状态居中：q写在u与v之间，不加空格，如“□ q₀ 01□”；
• 空白显形：v中若读写头右侧紧邻□，必须写出□，如“01 q₂ □”，不能省略。
  练习：M: δ(q₀,0)=(q₁,1,R), δ(q₁,1)=(q₂,0,R), δ(q₂,□)=(qₐ,□,R)，w=01。
  C₁: □ q₀ 01
  C₂: 0 q₁ 1
  C₃: 01 q₂ □
  C₄: 01□ qₐ □
  （C₄中，读写头移至□，状态qₐ，右侧仍为□）

6.3 归约函数f的“四不写”原则：不写代码、不写伪码、不写未定义变量、不写超限空间

阅卷人只认四要素：输入输出类型、保真性证明、可计算性说明、时间/空间复杂度。

• 不写代码：不要写Python实现，写“f(⟨M,w⟩)构造M'，其行为为：…”；
• 不写伪码：不要写“for each state do…”，写“M'的状态集为Q×{0,1}，转移函数δ'定义为：若δ(q,a)=(p,b,D)，则δ'((q,0),a)=((p,1),b,D)”；
• 不写未定义变量：如“令x为M的某个状态”，必须定义“x∈Q_M”；
• 不写超限空间：若要求对数空间归约，f的构造中不能出现“存储所有路径”，只能“逐边生成”。

6.4 从那以后我每次写归约，都强制走一遍“f输入→f输出→w∈A?→f(w)∈B?”的真值表验证

比如归约ATM≤ₘ HALTTM：f(⟨M,w⟩)=⟨M,w⟩。验证：

• 若⟨M,w⟩∈ATM，则M接受w → M在w上停机 → ⟨M,w⟩∈HALTTM；
• 若⟨M,w⟩∉ATM，则M拒绝或循环 → 若拒绝，则停机，仍∈HALTTM？错！HALTTM要求“停机”，拒绝是停机，所以⟨M,w⟩∉ATM不蕴含⟨M,w⟩∉HALTTM。正确归约是f(⟨M,w⟩)=⟨M',w⟩，其中M'在输入x上模拟M在w上运行，若M接受w则M'接受x，否则M'循环。则⟨M,w⟩∈ATM ⇔ M'在x上停机 ⇔ ⟨M',w⟩∈HALTTM。这个真值表必须手写一遍，哪怕考试只剩5分钟。希望帮到你。

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