Undecidability⚓︎

令 \(H_1 = \{“M”: \text{Turing machine } M \text{ halts on input string } “M”\}\)。

1. 假设前提：如果 \(H\) 是递归的（可判定的），那么它的特例 \(H_1\)（机器是否在输入自身编码时停机）也必须是递归的，进而 \(H_1\) 的补集 \(\overline{H_1}\) 也必须是递归的。
2. 构造矛盾：通过对角线法考察 \(\overline{H_1}\)（即“不接受自身编码的图灵机”的集合）。如果存在一个机器 \(M^*\) 能识别 \(\overline{H_1}\)，那么当问及“\(M^*\) 是否接受它自己的编码”时，会陷入“接受即不接受，不接受即接受”的逻辑悖论
3. 得出结论：由于 \(\overline{H_1}\) 连递归可枚举都做不到，因此初始假设不成立，证明了 \(H\) 不是递归的

假设 \(L_2\) 是可递归的，即能被图灵机 \(M_2\) 判定。令 \(T\) 为计算归约 \(\tau\) 的图灵机。那么图灵机 \(TM_2\) 就能判定 \(L_1\) 了。但 \(L_1\) 是不可判定的，于是发生矛盾。所以 \(L_2\) 也不是递归的。

1. 前面证明过了
2. 给定机器 \(M\) 和输入 \(w\)，构造一个新机器 \(M_w\)。\(M_w\) 在空纸带上启动时，会先在带子上写上 \(w\)，然后开始模拟 \(M\)。因此，\(M_w\) 在空纸带上停机，当且仅当 \(M\) 在输入 \(w\) 上停机。
3. （将问题 2 归约到此问题上）给定 \(M\)，构造 \(M'\)，它会擦除任何给定的输入，然后在空串上模拟 \(M\)。显然，\(M'\) 在“某个”字符串上停机，当且仅当它在“所有”字符串上停机，这也当且仅当 \(M\) 在空串上停机。
4. 问题 3 的论证同样适用于此，因为构造出的 \(M'\) 要么接受所有输入（如果 \(M\) 在空串停机），要么不接受任何输入。
5. （将问题 4 归约到此问题上）给定 \(M\)，构造字符串 \(“M”“y”\)，其中 \(y\) 是一台立即接受任何输入的机器。显然，\(M\) 和 \(y\) 接受相同的输入，当且仅当 \(M\) 接受所有输入。
6. （将问题 2 归约到此问题上）构造 \(M'\)：它先保存输入，然后运行 \(M\) 在空串 \(e\) 上的模拟。
   • 如果 \(M\) 在 \(e\) 上停机，\(M'\) 恢复输入并运行通用图灵机 \(U\)（此时 \(M'\) 接受的语言是 \(H\)）
   • 如果 \(M\) 在 \(e\) 上不停机，\(M'\) 就永远不停（此时 \(M'\) 接受的语言是 \(\emptyset\)）。由于无法判断 \(M\) 是否在 \(e\) 上停机，也就无法判断 \(L(M')\) 是 \(\emptyset\)（正则且递归）还是 \(H\)（非递归）
7. 这台特定机器正是通用图灵机 \(U\)

下面将展示从停机问题到（a）的归约：给定任何图灵机 \(M\) 和字符串 \(w\)，我们只需对 \(M\) 应用在「文法」一节的第一个定理的证明中给出的构造，得到一个文法 \(G\)，使得 \(L(G)\) 是由 \(M\) 半决定的语言。因此，当且仅当 \(M\) 在输入 \(w\) 时停机，\(w\) 属于 \(L(G)\)。

其他问题的证明也可以采用非常类似的归约，这里就不再赘述了。

整个证明的核心策略是归约，难点主要集中在第 1 个问题，一旦 1 被证明，问题 2、3、4 都可以通过简单的逻辑推导得出。以下是分步的清晰解释：问题 1 的证明思路是将一个已知不可判定的问题转化为“判断 \(L(G)\) 是否等于 \(\Sigma^*\)”的问题。

1. 我们已知“判断一个广义文法 \(G_1\) 是否生成任何字符串（即是否 \(L(G_1) \neq \emptyset\)）”是不可判定的

2. 构造“推导历史”集合 \(D_{G'_1}\)：

   • 我们将 \(G_1\) 转换为标准形式 \(G'_1\)
   • 定义集合 \(D_{G'_1}\) 为 \(G'_1\) 中所有合法的推导过程的字符串集合
   • 为了方便下推自动机（PDA）进行检查，这里采用了一种「牛耕式」（boustrophedon）的写法，即把推导步骤中的奇数项反转（ \(S_1 \Rightarrow x_1^R \Rightarrow x_2 \Rightarrow x_3^R \dots\)）；这样做是因为 PDA 的栈是后进先出的，反转后才能让栈顶元素与后续输入字符一一对应匹配
   • 关键逻辑：\(G_1\) 生成空语言（\(L(G_1) = \emptyset\)），当且仅当不存在合法的推导过程，即 \(D_{G'_1} = \emptyset\)

3. 转向考察补集 \(\overline{D_{G'_1}}\)：

   • 与其去描述合法的推导（这需要上下文敏感的能力），不如去描述不合法的推导，即 \(\overline{D_{G'_1}}\)
   • 如果 \(D_{G'_1}\) 是空的（意味着 \(G_1\) 不生成任何串），那么它的补集 \(\overline{D_{G'_1}}\) 就应该是全集 \(\Sigma^*\)
   • 只要我们能构造一个上下文无关文法 \(G_2\) 来生成 \(\overline{D_{G'_1}}\)，那么判断“\(L(G_2) = \Sigma^*\)”就等同于判断“\(L(G_1) = \emptyset\)”

4. 证明 \(\overline{D_{G'_1}}\) 是上下文无关的：一个字符串只要满足以下任意一个条件，它就是“非法推导”（属于 \(\overline{D_{G'_1}}\)）：

   • 开头不对
   • 结尾不对
   • 分隔符 \(\Rightarrow\) 数量不对
   • 偶数步推导错误（不符合规则）
   • 奇数步推导错误（不符合规则）

   可以证明这 5 种情况对应的语言都是上下文无关的。前三种和正则语言相关，证明较简单；而后两种可以通过非确定性 PDA 构造出来，利用栈来对比相邻的推导步骤。由于上下文无关语言对并集封闭，所以它们的并集 \(\overline{D_{G'_1}}\) 也是上下文无关的，因此存在一个文法 \(G_2\) 生成它。

如果我们能判定 \(L(G_2) = \Sigma^*\)，我们就能判定 \(L(G_1) = \emptyset\)，因为后者不可判定，所以前者也不可判定。

基于问题 1 的推论，我们继续完成问题 2, 3, 4 的证明：

1. 如果这个问题可解，那我们只需要把 \(G_2\) 设为一个能生成全集 \(\Sigma^*\) 的平凡文法；这样问题就变成了“判断 \(L(G_1) = \Sigma^*\)”，回到了问题 1。既然 1 不可解，2 也就不可解
2. 上下文无关文法可以转化为等价的 PDA；如果能判断 PDA 的等价性，也就等于能判断 CFG 的等价性，回到了问题 2，因此不可解
3. 如果能求出最小状态 PDA，我们就可以检查它是否是那个“接受 \(\Sigma^*\) 的单状态 PDA”；也就是说，如果能最小化，就能判断一个 PDA 是否接受全集 \(\Sigma^*\)，这等同于判断一个 CFG 是否接受全集 \(\Sigma^*\)，回到了问题 1，因此不可解

证明的核心在于用并行模拟把两个可能不停机的过程变成一个必然停机的过程。

• 正向（\(\Rightarrow\)）：若 \(L\) 是递归的，它和它的补集 \(\bar{L}\) 自然都是递归可枚举的（这是定义的直接推论）
• 反向（\(\Leftarrow\)）：
  • 设机器 \(M_1\) 识别 \(L\)，机器 \(M_2\) 识别 \(\bar{L}\)，构造新机器 \(M\) 同时并行运行 \(M_1\) 和 \(M_2\)
  • 因为任意输入 \(w\) 必在 \(L\) 或 \(\bar{L}\) 中，所以 \(M_1\) 和 \(M_2\) 必有一个会停机
  • 一旦其中一个停机，\(M\) 就立即给出最终结果（\(M_1\) 停则接受，\(M_2\) 停则拒绝）
  • 既然 \(M\) 总能停机并给出结果，说明 \(L\) 是递归的

1. 假如 \(L\) 是递归可枚举的 \(\rightarrow\) 它可以被机器枚举

   • 难点：如果依次测试字符串 \(s_1, s_2, s_3...\)（看机器是否接受它们），一旦机器在某个字符串上陷入死循环，就永远没机会测试后面的字符串了
   • 解法（燕尾法 (dovetailing)）：采用分阶段并行的策略
     • 阶段 1：对第 1 个字符串跑 1 步
     • 阶段 2：对前 2 个字符串各跑 2 步
     • 阶段 \(k\)：对前 \(k\) 个字符串各跑 \(k\) 步
   • 结果：这样保证了机器 \(M\) 永远不会卡死在某一个输入上，只要一个字符串属于 \(L\)，它最终一定会在某个阶段被接受并被打印出来

2. 假如 \(L\) 可以被机器枚举 \(\rightarrow\) 它是递归可枚举的

   • 思路：这个方向很简单。假设有一台“枚举机器”在不断吐出属于 \(L\) 的字符串
   • 构造：我们要判断输入 \(w\) 是否在 \(L\) 中，只需运行这台枚举机器，并盯着它的输出看
   • 判定：每当枚举机器吐出一个新串，就拿来和 \(w\) 比对；如果相等，就停机接受；如果不等，就继续等下一个；如果 \(w \in L\)，它迟早会被吐出来并被接受

1. 正向（\(L\) 是递归的 \(\rightarrow\) 可以按字典序枚举）

   • 关键点：递归语言的判定机器 \(M\) 总是会停机（不会死循环）
   • 做法：构造一个新机器，按字典序（\(s_1, s_2, s_3...\)）依次生成所有可能的字符串，并用 \(M\) 去测试每一个
   • 结果：因为 \(M\) 对每个串都能快速给出 Yes/No 而不卡死，可以按顺序一个个测下去；测过并通过的就打印出来，输出自然就是严格按字典序排列的

2. 反向（可以按字典序枚举 \(\rightarrow\) \(L\) 是递归的）

   • 关键点：有序性让我们知道“何时该放弃等待”

   • 做法：假设有一个能按顺序吐出字符串的枚举机；要判定输入 \(w\) 是否在 \(L\) 中，就盯着这个枚举机看：

     • 如果枚举机吐出了 \(w\)，直接接受
     • 如果枚举机吐出了一个比 \(w\) 还要大（字典序更靠后）的字符串，说明 \(w\) 肯定已经被跳过去了，以后永远也不会出现了，直接拒绝

   • 结论：因为总是能等到上面两种情况之一（不会无休止地等下去），所以判定过程必然停机，证明 \(L\) 是递归的

利用归约法，把停机问题转化为判断一个语言是否属于类 \(\mathcal{C}\) 的问题

• 设定：设 \(\mathcal{C}\) 是递归可枚举语言的一个真子集。不妨假设空集 \(\emptyset \notin \mathcal{C}\)，而存在某个特定语言 \(L \in \mathcal{C}\)（由机器 \(M_L\) 识别）
• 构造：对于给定的停机问题实例（机器 \(M\) 和输入 \(w\)），我们构造一个新的机器 \(T_{M,w}\)
  • \(T_{M,w}\) 在处理任何输入 \(x\) 时，先强制运行 \(M\) 在 \(w\) 上的计算
  • 若 \(M\) 死循环：\(T_{M,w}\) 也会永远卡在这里，不接受任何 \(x\)，此时它识别的语言是 \(\emptyset\)（不在 \(\mathcal{C}\) 中）
  • 若 \(M\) 停机：\(T_{M,w}\) 就会继续去运行 \(M_L(x)\)，此时它识别的语言就是 \(L\)（在 \(\mathcal{C}\) 中）
• 结论：这样一来，判断“\(T_{M,w}\) 识别的语言是否属于 \(\mathcal{C}\)” 就完全等价于判断 “\(M\) 是否在 \(w\) 上停机”；因为停机问题不可判定，所以“判断语言是否属于类 \(\mathcal{C}\)” 也是不可判定的