CSCI3130 L11–L12 语言层级与文法 · Part 5 可判定性与停机问题

课程：CSCI3130 Formal Languages and Automata Theory 本讲：合讲第 5 部分 / 共 6 部分 · 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.73–106 定位：从总停机的 YES/NO 算法，走到成员问题与停机问题的不可判定性。 前后：上一份 乔姆斯基层级 · 下一份 归约与不可计算函数 承接：#L11-10 可判定性、#L11-11 成员问题、#L11-12 停机问题

什么算解决了一个判定问题（p.73–75）【新】

p.73 是 Decidability 分节页。

p.74 Consider problems with answer YES or NO

p.75 A problem is decidable if some Turing machine decides (solves) the problem

一个问题有许多实例；算法必须对每个合法实例都有限给出正确答案，才叫可判定。p.74–75 的三个例子分别检查机器描述是否恰有三个状态、字符串是否为二进制数、DFA 是否接受至少一个输入。前两个扫描有限描述即可；第三个在有限状态图里检查初态能否到达终态，不必枚举无限多输入。

算一遍（数字为演示自取）：DFA 有 q0、q1、q2，初态 q0，唯一终态 q2。若 q0 只能到 q1，q1 只能回 q0，则可达集合从 {q0} 扩为 {q0,q1} 后不再改变；没有 q2，所以“接受任何输入吗”的答案为 NO。这里 any 是“至少一个”，不是“所有”。

YES 和 NO 都必须真的到达（p.76–78）

p.76 The Turing machine that decides (solves) a problem answers YES or NO for each instance of the problem

p.78 YES and NO states are halting states

p.76 的输入实例经过 TM 后分成 YES/NO；p.77 把两种答案落实为两类停机状态；p.78 强调它们都不能再计算。运行很久却没有到 YES，不等于已经到 NO。若某些 NO 实例永远运行，这至多是识别器，不是判定器。

图（p.76、78）：实例进入机器，输出分为 YES 状态组和 NO 状态组。元素：两个输出组都属于停机配置。看什么：图画了两条出口，并不自动证明每个输入都能抵达出口；总停机要另外证明。

状态命名与能力不是一回事（p.79–81）

p.79 The YES states may not be final states

讲义 p.79 区分判定问题的 YES 状态与语言识别器的 final states，这是输出约定。把 YES 状态标为接受、NO 状态标为拒绝，就得到对应递归语言的判定器；不形成新的计算能力。

p.80 there is no Turing Machine that solves all instances of the problem

p.80 的不可判定量词是“不存在同一个算法解决所有实例”。它不表示每个实例都难，更不表示任何特定简单机器的行为都不可知。

题面块（讲义 · The Membership Problem · PDF p.81）：

p.81 Input: •Turing Machine M •String w

p.81 Question: Does M accept w ?

公式按讲义重排：问 $w\in L(M)$ 是否成立。机器本身也随输入变化，所以这与某一固定简单语言的成员测试不同。

假设一个万能成员判定器（p.82–84）

p.82 The membership problem is undecidable

p.82 采用反证法：假设存在总停机机器 H，输入 M 的编码及 w，总能判断 M 是否接受 w。p.83 给出 H 的接口；p.84 取任意 RE 语言 L，固定一个识别它的 M。

图（p.83）：M、w 输入 H，YES 接到 “M accepts w”，NO 接到 “M rejects w”。看什么：原图的 NO 用词过窄。成员判定的 NO 应为“没有接受”，包括停机拒绝和无限运行两种情况；若只处理有限拒绝，就不是本证明需要的 H。

算一遍（自取行为例）：M 在输入 a 上接受、b 上拒绝、c 上永远右移。假想 H 必须分别输出 YES、NO、NO，并且三次都有限结束；模拟 M 本身只能完成前两次。

由假想 H 把任意 RE 变成递归（p.85–87）

p.86 Since L is chosen arbitrarily, every recursively enumerable language is also recursive

p.85 的新机器读 w，把固定 M 的编码和 w 交给 H；YES 就接受，NO 就拒绝。它正确，因为 H 回答的正是成员资格；它总停机，因为 H 总停机。于是任意 RE 语言都有判定器。p.86 与 Part 1 已证明的“存在 RE 而非递归的语言”矛盾，p.87 得出成员问题不可判定。

这一证明无需知道 M 的循环何时结束；所有魔法都被放进假设中的 H，随后证明这样的 H 不存在。不能先写“运行 M，等它不接受后拒绝”，那一步本身没有算法。

停机与接受是两个问题（p.88–90）

p.88 是停机问题的引入页。

题面块（讲义 · The Halting Problem · PDF p.89）：

p.89 Input: •Turing Machine M •String w

p.89 Question: Does M halt on input w ?

p.90 The halting problem is undecidable

停机问题把有限接受和有限拒绝都算 YES；只有无限运行算 NO。成员问题只把接受算 YES。因此从“会停”还不能直接推出“属于语言”。p.90 再次假设有一个总停机判定器，用它制造矛盾。

将停机预测取反为实际行为（p.91–93）

p.93 If H returns YES then loop forever

p.93 If H returns NO then halt

p.91 的 H 预测 M 在 w 上是否停机。p.92 将 M 写成有限字符串编码 $w_M$，与 w 放到同一输入带。两部分必须可解析；分隔符或自定界编码是表示细节，不是预知运行结果。p.93 建造 H′：先运行 H，然后让自身行为与预测相反。因为 H 总停机，H′ 总会进入其中一个分支。

补充（实现细节）：无限循环可用一个状态不断右移；有限停机可进入无后继的状态。这里反转的是“停/不停”，并非简单交换接受与拒绝。

把机器自己的编码送进去（p.94–96）

图（p.94）：初态 q0 在内部运行 H，到 YES 状态 qy 后进入 qa、qb 的双向循环；NO 状态 qn 保持停机。元素：qa→qb、qb→qa 是循环边，qy→qa 是接入边；q0 到 qy/qn 是内部计算的概括箭头，不是单步转移。看什么：原来的 YES 停机出口被延长为永不停止的计算。

p.95 If M halts on input wM Then loop forever Else halt

p.95 定义带帽 H：它只有一个输入 $w_M$，判断 M 在自己的编码上是否停机，再反向行动。p.96 用“复制输入”模块生成两份 $w_M$，送入 H′。复制有限字符串是可计算操作，因而带帽 H 仍是一台普通 TM，不是额外神谕。

图（p.96）：输入 $w_M$ → copy 模块 → 编码对 $(w_M,w_M)$ → H′。看什么：左份指定被模拟机器，右份是该机器收到的数据；相同字串承担两种角色。

自指带来的两种矛盾（p.97–99）

p.98 If Ĥ halts then loops forever

p.98 If Ĥ doesn’t halt then it halts

p.97 取带帽 H 的编码作为带帽 H 的输入。若 H 预测它会停，构造迫使它循环；若预测它不停，构造迫使它停。p.98 两种可能都与正确预测冲突，p.99 排除最初假设。

问题不在“机器不能输入自己”：编码就是普通有限串，复制和解释都合法。问题在于假想 H 必须连这个特制实例也回答正确。见附录 A1 将两种情况写成完整逻辑式。

考试角度：（C 级 通识）常见考法是补全自指机器的两个分支，说明反转的是停机行为，并指出假设中的判定器必须总停机。

正文推导补全

设 H 总停机且正确判断停机。定义 D(x)：若 x 是合法机器编码，令 H(x,x) 运行；回答 YES 时无限循环，回答 NO 时停机。非法编码可直接停机，不影响合法实例。有限代码能描述 D，故 D 有编码 d。

若 H(d,d)=YES，按 H 的正确性 D(d) 应停机，但按 D 定义它进入无限循环，矛盾。若 H(d,d)=NO，按正确性 D(d) 应永不停止，但按 D 定义它立即停机，仍矛盾。H 总停机保证没有第三种“迟迟不回答”可逃开讨论。因此 H 不存在。D 就是正文的带帽 H，名称变换不改变构造。

不用直接自指的第二条证明线（p.100–102）

p.100 If the halting problem was decidable then every recursively enumerable language would be recursive

p.100 宣布另一证明路线；p.101 重新假设停机可判定；p.102 给出 H 的 YES/NO 接口。它与前面成员问题的证明相似，但 H 只知道是否停机，尚不知道停止后是否接受，因此还需要一次真实模拟。

先确认会停，再放心模拟（p.103–105）

p.103 Let L be a recursively enumerable language

p.103 固定 L 的识别器 M。p.104 的算法先问 H(M,w)：若 NO，M 永不接受，立即拒绝；若 YES，模拟 M 到停机，再根据停在 final/non-final 状态接受或拒绝。YES 分支模拟必结束，是因为已经有 H 的正确保证，不是因为 RE 识别器本来总停机。p.105 因而把任意 RE 变成递归，产生同一个矛盾。

图（p.104）：H 的 NO 直接连 reject；YES 连 Run M，再按停机状态分 accept/reject。看什么：若把 H 的 YES 直接连 accept，会把有限拒绝的实例误收。

算一遍（沿用自取行为例）：M(a) 接受、M(b) 拒绝、M(c) 循环。H 的回答是 YES、YES、NO；新的成员判定器输出接受、拒绝、拒绝。前两项依赖后续模拟来区分。

结论的适用范围（p.106）

p.106 Therefore, the halting problem is undecidable

不能有一个处理所有 TM、所有输入的总停机预测算法，并不排除分析特定程序，也不排除有限状态系统的可达性算法。证明的输入域不能偷偷缩成只会停机的机器；否则原来的反例机器被排除了，已经换题。

三种运行结果怎样进入两个不同问题（补充）

这一表不是判定算法，而是目标答案的语义。成员问题的 NO 将后两行合在一起；停机问题的 YES 将前两行合在一起。自指证明若想反转停机预测，必须制造“停/不停”差异，只交换接受/拒绝不会改变表中停机列，因此得不到矛盾。

对非法机器编码也应有固定处理，例如直接拒绝或视作某台固定机器；这样外层构造真是一个定义完整的程序。矛盾只需要合法编码 d，故非法输入策略不会救回假想 H。关键不是某个解析器会崩溃，而是对所有合法实例的总停机正确预测本身不可能。

本讲核心考点

• 判定器在每个合法实例上都有限给出 YES/NO（p.74–79，C 级）。
• 成员问题的 NO 包括拒绝和循环；原图 “rejects” 须按此理解（p.81–86，C 级）。
• 停机、接受的 YES 集合不同（p.89、104，C 级）。
• 自指证明：编码复制、反向行为、将自身编码输入自身（p.92–99，C 级）。
• 停机判定器若存在，可以把任意识别器变成判定器（p.100–106，C 级）。

附录

A1 自指证明的两分支展开

设 H 总停机且正确判断停机。定义 D(x)：若 x 是合法机器编码，令 H(x,x) 运行；回答 YES 时无限循环，回答 NO 时停机。非法编码可直接停机，不影响合法实例。有限代码能描述 D，故 D 有编码 d。

若 H(d,d)=YES，按 H 的正确性 D(d) 应停机，但按 D 定义它进入无限循环，矛盾。若 H(d,d)=NO，按正确性 D(d) 应永不停止，但按 D 定义它立即停机，仍矛盾。H 总停机保证没有第三种“迟迟不回答”可逃开讨论。因此 H 不存在。D 就是正文的带帽 H，名称变换不改变构造。

返回正文

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L11-L12-语言层级与文法-资料包.pdf（本地课件），PDF p.73–106；页脚 Ch 11。

• 本次独立学习修订：核对合讲140页文本，视觉复核 p.38、60、70–71、83、94；补全正文证明并保留原页与补充构造的区分。