CSCI3130 L11–L12 语言层级与文法 · Part 6 归约与不可计算函数
课程：CSCI3130 Formal Languages and Automata Theory 本讲：合讲第 6 部分 / 共 6 部分 · 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.107–140 定位：用实例转换传递不可判定性，再用停机时间上界说明函数可以有定义却不可计算。 前后：上一份 可判定性与停机问题 · 下一讲 计算复杂度 承接：#L11-13 归约、#L11-14 空白带停机、#L11-15 停机时间上界与不可计算函数
归约的方向（p.107–109）【新】
p.107 是 Reducibility 分节页。
p.108 If we can solve problem B then we can solve problem A
p.109 If A is undecidable then B is undecidable
把 A 的实例有效转换成 B 的实例，保留 YES/NO 答案，意味着 B 的算法可被拿来解决 A。这里写 表示一次可计算的实例映射；讲义使用较宽泛的 reduced to 措辞，后面两个构造都满足这个较具体的形式。
若 B 可判定，转换完调用 B 的判定器就判定 A。取逆否命题：已知 A 不可判定，则 B 也不可能可判定。要证明新问题 B 难，应从已知难的 A 转向 B；只证明 B 能转到停机问题不能得出 B 不可判定。
算一遍（演示归约逻辑）：若一个总算法能把每个 A 实例 x 转为 f(x)，且 x 的答案与 f(x) 在 B 中的答案一致，假设 B 的程序运行 20 步后回答 NO，则 A 的程序在转换结束后再运行这 20 步也回答 NO。20 是自取示意，不是统一时间界；本节只要求每次有限结束。
状态进入问题究竟问什么（p.110–112）
题面块（讲义 · The state-entry problem · PDF p.111）：
p.111 Inputs: •Turing Machine M •State q •String w
p.111 Question: Does M enter state q on input w ?
p.110 宣布 HALT 归约到状态进入；p.112 提出不可判定性定理。目标 q 也是输入的一部分，问运行过程中是否曾到 q，不要求 q 是接受态，也不要求进入后停机。初始配置已经在 q 时也应按既定“到达”约定处理；下面构造用一个全新的非初态，避开此边界。
用一个假想的状态进入判定器（p.113–115）
p.114 We want to build a decider for the halting problem
p.113 假设存在状态进入判定器 D，输入三元组 M、w、q，总能回答是否进入。p.114 目标却只有原停机实例 M、w。p.115 在二者之间放一台待构造 M′：把 M′、指定 q、原 w 交给 D，原样返回答案。
图（p.115）：M、w 在左，M′、q、w 在中间，State-entry decider 在右，YES→YES、NO→NO。看什么：构造不能先模拟 M 到停机才生成 M′；否则遇到不停的 M，转换步骤自己就卡住了。
把所有停止出口接到一个新状态（p.116–118）
p.117 Add new state q
p.117 From any halting state of M add transitions to q
p.116 标出缺少的转换模块。p.117 的构造复制 M，并在原停止位置接入新 q。p.118 的关键是双向等价：M 在 w 上停，当且仅当 M′ 在 w 上进入 q。
图（p.117）：M 的三个示意停机出口都箭向盒外但仍在 M′ 内的 q；q 是唯一新停止状态。看什么：这些箭头只汇总原来的停机情形，没有让其他计算提前走到 q。
补充（部分转移函数的规范）：如果课程模型因某个“状态、读到符号”组合没有转移而停，而非每个停机状态对所有符号都无转移，应对每个原先未定义的组合补一条到 q 的转移；不能给这个状态的所有读符号组合都加出口。另一做法是先有效规范成显式停机状态。两种处理都只是改有限转移表，不运行待分析输入。
算一遍（自取简单机器）：M 在 q0 读 a 时右移并仍在 q0，读空白时停。输入 aa 的 M 走两步后停；M′ 先同样走两步，再从原未定义的空白组合到 q。若 M 改成读任意符号都右移，则没有被执行到的停机出口，M′ 也永不到 q。
两个方向都要证明（p.119–120）
p.120 Since the halting problem is undecidable, the state-entry problem is undecidable
p.119 将 Generate M′ 与 D 接起来。若 M 停，M′ 接着进入 q，D 回答 YES；若 M′ 进入 q，因为 q 是新状态且唯一入口来自原停止情形，M 必已停，故不存在虚假的 YES。M 不停则 M′ 始终模拟，不进入 q。生成是总可计算的，D 又假设总停机，所以组合本会判定 HALT，矛盾。
考试角度：（C 级 通识）常见考法是检查转换有没有偷用停机判断，以及是否同时证明 YES 保留和 NO 保留。
空白带也能藏下任意实例（p.121–123）
题面块（讲义 · The blank-tape halting problem · PDF p.122）：
p.122 Input: Turing Machine M
p.122 Question: Does M halt when started with a blank tape?
p.121 指定从普通 HALT 归约到空白带 HALT，p.123 给出定理。虽然不再另外输入 w，机器描述仍可变化；任何固定有限字符串都可以写进机器的有限控制。因此“输入带空白”不等于“所有实例是同一个程序”。
输入从二元组变成一台机器（p.124–126）
p.125 We want to build a decider for the halting problem
p.124 假设空白带判定器 D；p.125 仍要解决任意 M、w 的停机；p.126 给 D 的对象叫 。下标 w 表示针对这个实例生成的代码，w 不再作为 D 的单独数据输入。
图（p.126）：M、w → → Blank-tape decider → 原样输出。看什么：归约不是把 w 丢掉，而是把它移进程序。
先写入，再模拟（p.127–129）
p.128 When started on blank tape, writes w
p.128 Then continues execution like M
p.127 提问如何转换。p.128 的两阶段构造先在空白带写出 w，再把读头摆回 M 的标准初始位置、进入 M 的初态，随后逐步模拟。有限 w 的写入和回位必结束。p.129 因而得到普通运行停机与空白运行停机的等价。
图（p.128）：step 1 写 w，箭接 step 2 execute M with input w。看什么：两个阶段顺序执行，第一阶段不需要预测第二阶段何时结束。
算一遍（自取输入）：w=ab，生成机器先写 a、右移写 b，再回到 a 下方启动 M。若 M 从输入左端读两格后拒绝， 也在初始化之后有限拒绝，故空白带 HALT 应回答 YES；拒绝仍是停机。
闭合归约证明（p.130–131）
p.130 组合生成器与假想 D。p.131 用等价性得出：D 若存在，普通 HALT 就可判定，矛盾。
把本讲两个实例转换并排写出，可以核查归约的输入输出：
| 原实例 | 有限时间生成的新实例 | 保留的等价条件 |
|---|---|---|
| (M,w) | (M′,q,w)，q 全新，仅原停机处转入 | M(w) 停机，当且仅当 M′(w) 进入 q |
| (M,w) | Mw，其初始化在空白上写 w 并归位 | M(w) 停机，当且仅当 Mw 从空白带停机 |
两行都只生成代码，不先求原问题的答案。若转换过程先问 M(w) 会不会停，就把尚待证明不可能的判定器偷偷用进了构造。
四个问题的输入和答案（p.132–133）
p.132 汇总一般停机和成员问题；p.133 汇总空白带停机和状态进入。
| 问题 | 输入 | YES 的含义 |
|---|---|---|
| 成员 | M、w | M 接受 w |
| 停机 | M、w | M 在 w 上有限停止，无论接不接受 |
| 空白带停机 | M | M 从全空白初始带有限停止 |
| 状态进入 | M、w、q | 运行中到达 q |
它们的共同结论是没有适用于全部实例的判定器，不是所有实例都不能分析。表只整理本讲已证的四个问题。
有定义的函数未必有算法（p.134–136）【新】
p.134 是 Uncomputable Functions 分节页。
p.135 A function is uncomputable if it cannot be computed for all of its domain
p.136 maximum number of moves until any Turing machine with n states halts when started with the blank tape
讲义把 f(n) 定义为 n 状态机器从空白带出发、在会停的机器中最长的运行步数。不能把永不停止的运行当作一个无限大的候选值，否则定义就不是后面证明所需的自然数函数。
补充（原页未写出的模型条件）：必须固定有限带字母表、转移格式和状态计数约定。这样 n 固定时，规范命名后的转移表只有有限多份，其中会停的各有一个有限步数，才能取有限最大值。若允许字母表任意增大，仅限制状态数就不够。本讲原文没列这个条件，不能将缺少条件的句子当作完整数学定义。没有会停机器的边界可约定 f(n)=0，或只考虑有候选机器的状态规模。
若能计算最大步数，就能判定停机（p.137–138）
p.138 Count states of M : m
p.138 Simulate M for f (m) steps starting with empty tape
p.137 假设 f 可计算。p.138 先数输入机器的 m 个状态，算出 f(m)，再只模拟有限的 f(m) 步。如果其间已经停，回答 YES；若到这个界仍未停，回答 NO。原因不是“等得够久了”，而是定义保证任何最终会停的 m 状态机器都必须在这个界内停止。
算一遍（数字为演示自取，非真实函数值）：假设某模型某 m 的 f(m)=12。模拟时先检查初始配置是否已经停，再检查第 1 至第 12 步之后的配置。若第 12 步正好停，仍要回答 YES；仅在检查完界内所有时刻仍未停时回答 NO。这里 12 只展示算法，不声称计算出了任何 Busy Beaver 数值。
上界存在和上界可算是两件事（p.139–140）
p.139 However, the blank-tape halting problem is undecidable
p.139 与已证明的空白带停机不可判定矛盾，p.140 排除 f 可计算的假设。有限集合有最大值是存在性论证；若不能有效筛出哪些机器会停，就不等于能把这个最大值算出来。
见附录 A1 检查为什么“把所有机器同时跑，记录目前最大值”不能计算 f。
考试角度：（C 级 通识）常见考法是从假想的可计算运行时间上界构造停机判定器，并交代固定机器模型及模拟边界。
考试角度：（A 级：期末-2022T1-资料包.pdf Q7，对应所有输入都循环的不可判定性；扫描件视觉读取。）见附录 A2。
生成一段程序，不等于执行这段程序（补充）
给定 M 与 w，转换器写出 N 的有限描述：“忽略自身输入；在内部模拟 M(w)；模拟停机时再执行指定动作。”转换器只需复制 M 的转移表、嵌入有限 w、连接若干控制状态，因此无论 M(w) 将来是否停，它都能结束。N 真正运行时才进行那段可能不终止的模拟。若错误地把模拟放到转换器里，归约函数在 NO 实例上就可能无输出，失去总可计算要求。
同样，有限多台机器的最大停机步数在数学上存在，不等于可以枚举“所有会停的机器”并知道什么时候枚举完。不断改进的下界可以在某时达到真值，却无法确认此后不再改变。要计算一个自然数函数，必须在有限时刻输出正确值并结束；“最终会稳定但不知道哪一刻”是另一种承诺，不能拿来给停机模拟设可计算截止时间。
自检：若已知新问题 B 可转成 HALT，能推出 B 不可判定吗？
把假想算法的调用顺序写成箭头。
展开推理与答案
不能。这只说明有 HALT 的解法就能解决 B；连容易判定的问题也能这样归约。要从 HALT 的困难推出 B 困难，应把任意 HALT 实例有效映为 B 实例，使 B 的判定器若存在就能解决 HALT。
本讲核心考点
- A 归约到 B 意味着 B 的判定器能判定 A，难度传递方向不可反（p.108–109，C 级）。
- 状态进入归约通过新增目标状态收集所有原停机情形（p.110–120，C 级）。
- 空白带归约把任意有限输入硬编码到初始化模块（p.121–131，C 级）。
- 构造必须有效且有限结束，等价性要证明两个方向（p.116–130，C 级）。
- 固定模型中的最大停机步数有定义但不可计算（p.135–140，C 级）。
附录
A1 为什么逐步枚举仍拿不到最终上界
固定 n 后列出有限多台机器，以轮转方式各模拟一步。每次有机器停机，就更新“目前见到的最大步数”。任何会停的机器最终都会被观察到，因此记录最终会稳定到 f(n)。但观察者不知道何时已经稳定：某台尚未停的机器可能再过很久才停，也可能永远不停。若有统一的有限算法知道“可以停止等候并输出了”，它就计算了 f，并按正文构造判定空白带停机，矛盾。无限过程趋向正确值与有限算法交出正确值不同。
A2 作业/往年题演练（非讲义内容）：所有输入都循环的不可判定性
题面块（期末-2022T1-资料包.pdf（本地课件） · Q7 · p.5，扫描件视觉读取）：
p.5 Fact: is undecidable. So is .
p.5 Prove that the following language is undecidable.
p.5 .
反设L有总停机判定器D。给任意HALT实例(M,w)，有效生成新机器N：在任意输入x上忽略x，模拟固定M(w)；若模拟停机则N停机，若模拟继续则N继续。这里将M和w写入有限描述，生成代码不等待模拟结束。
若M(w)不停，N对每个输入都不停，D(N)=YES；若M(w)停，N对每个输入都停，D(N)=NO。因此运行D(N)并把YES/NO翻转就能判定HALT，矛盾。必须说明全称量词：由于N忽略自己的x，任何输入行为相同，才将一个原实例推广为“每个输入”。
若用保YES的多一归约记号，这个构造是HALT的补语言归约到L，而不是直接写HALT≤mL；HALT的补同样不可判定，否则翻转其判定器即可判定HALT。也可以如上直接写一次调用并翻转输出的完整反证算法，避免记号方向误导。
来源与证据
历史版本考试证据（本次未重新读取全部试卷）：读了 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.107–140；页脚 Ch 11。
-
本次独立学习修订：核对合讲140页文本，视觉复核 p.38、60、70–71、83、94；补全正文证明并保留原页与补充构造的区分。