1. 讲义 10a：不可识别性与映射归约

这个标题明确了本讲义的核心主题。“不可识别性”（Unrecognizability）和“映射归约”（Mapping Reductions）是计算理论中两个紧密相关且至关重要的概念，它们都属于可计算性理论（Computability Theory）的范畴。

• 不可识别性：这个概念用来描述一类比“不可判定”问题更“难”的问题。一个语言是可识别的（Recognizable），意味着存在一个图灵机，当输入属于该语言的字符串时，它会停机并接受；而当输入不属于该语言时，它要么停机并拒绝，要么永不停机（循环）。而一个“不可识别”的语言，则连这样的图灵机都不存在。这通常意味着我们无法系统性地验证一个字符串是否属于该语言。

• 映射归约：这是一种形式化的工具，用来比较两个问题的相对难度。如果问题A可以映射归约到问题B（记作 $A \leq_{m} B$），直观上意味着问题A“不比”问题B更难。我们可以通过一个可计算的函数，将问题A的任何实例转化为问题B的一个实例，并且转化后的实例的答案与原实例的答案完全相同。这个工具非常强大，因为一旦我们知道问题A是“难”的（比如不可识别的），并且我们证明了 $A \leq_{m} B$，那么我们就可以断定问题B也一定是“难”的（至少和A一样难）。

本讲义的目标就是介绍如何使用映射归约作为一种核心技术，来证明某些语言是不可识别的。

这部分首先回顾了可识别性 (Recognizability) 和协同可识别性 (Co-recognizability) 的基本定义，并重申了它们与可判定性 (Decidability) 之间的关键关系。

关于定义1.1 (可识别的):

一个语言 $L$ 被称为图灵可识别的（Turing-recognizable）或递归可枚举的（Recursively Enumerable）。这意味着我们可以构造一台图灵机 $M$，它扮演着一个“验证者”或“接收器”的角色。

• 对于属于 $L$ 的字符串 $w$ ($w \in L$)：当我们将 $w$ 作为输入给图灵机 $M$ 时，$M$ 会在有限的步骤后停机，并进入接受状态。这就像一个俱乐部会员，保安（图灵机）检查了你的会员卡（字符串 $w$），确认无误后让你进入（接受）。
• 对于不属于 $L$ 的字符串 $w'$ ($w' \notin L$)：当我们将 $w'$ 作为输入给图灵机 $M$ 时，$M$ 永远不会进入接受状态。这里有两种可能性：

1. $M$ 在有限步骤后停机，并进入拒绝状态。
2. $M$ 永不停机，即陷入一个无限循环。

这就像一个非会员，保安要么直接告诉你“你不能进”（拒绝），要么把你晾在一边，一直核对他的名单，永远不给你答复（循环）。重要的是，你绝对不会被允许进入。

关于定义1.2 (协同可识别的):

一个语言 $L$ 是协同可识别的（co-recognizable），这个概念是建立在“补集”和“可识别性”之上的。

• 首先，我们需要理解什么是补集 $\bar{L}$。补集指的是所有不在 $L$ 中的字符串的集合。如果我们把所有可能的字符串看作一个全集 $\Sigma^*$，那么 $\bar{L} = \Sigma^* - L$。
• 如果这个补集 $\bar{L}$ 本身是可识别的，那么我们就称原始语言 $L$ 是协同可识别的。
• 这意味着，存在一台图灵机 $M'$，它能识别 $\bar{L}$。也就是说：
• 如果一个字符串 $w$ 不属于 $L$ (即 $w \in \bar{L}$)，那么 $M'$ 会在 $w$ 上停机并接受。
• 如果一个字符串 $w$ 属于 $L$ (即 $w \notin \bar{L}$)，那么 $M'$ 在 $w$ 上要么拒绝，要么循环。

关于定理1.3 (可判定性与可识别性的关系):

这个定理是计算理论的基石之一，它精确地描述了可判定、可识别和协同可识别三者之间的关系。

• $L$ 是可判定的：意味着存在一台图灵机 $M_{decider}$，它对于任何输入字符串 $w$，总能在有限时间内停机，并明确地回答“是”（接受）或“否”（拒绝）。它从不循环。
• 定理内容：一个语言 $L$ 是可判定的，当且仅当它既是可识别的又是协同可识别的。
• $\Longrightarrow$ (如果 $L$ 可判定，则它既可识别又协同可识别):
• 如果 $L$ 可判定，那么存在一个总停机的图灵机 $M_{decider}$。这个 $M_{decider}$ 本身就可以作为 $L$ 的识别器，所以 $L$ 是可识别的。
• 因为 $L$ 是可判定的，它的补集 $\bar{L}$ 也是可判定的（我们可以构造一个图灵机，它模拟 $M_{decider}$，然后在接受时拒绝，在拒绝时接受）。既然 $\bar{L}$ 是可判定的，那么它也一定是可识别的。根据定义，如果 $\bar{L}$ 可识别，那么 $L$ 就是协同可识别的。
• $\Longleftarrow$ (如果 $L$ 可识别且协同可识别，则它可判定):
• 假设 $L$ 是可识别的，存在图灵机 $M_{rec}$ 识别它。
• 假设 $L$ 是协同可识别的，存在图灵机 $M_{co-rec}$ 识别它的补集 $\bar{L}$。
• 我们可以构造一个新的图灵机 $M_{decider}$，它在输入 $w$ 时，同时（例如，通过在纸带上交替模拟）运行 $M_{rec}$ 和 $M_{co-rec}$。
• 对于任何字符串 $w$，它要么属于 $L$，要么属于 $\bar{L}$。
• 如果 $w \in L$，$M_{rec}$ 必定会在有限步后停机并接受。此时，$M_{decider}$ 就停机并接受 $w$。
• 如果 $w \notin L$ (即 $w \in \bar{L}$)，$M_{co-rec}$ 必定会在有限步后停机并接受。此时，$M_{decider}$ 就停机并拒绝 $w$。
• 由于对于任何输入 $w$，$M_{rec}$ 和 $M_{co-rec}$ 中必有一个会停机，所以我们新构造的 $M_{decider}$ 总是会停机。因此，$L$ 是可判定的。

这部分列出了四种证明一个语言 $L$ 是不可识别的的策略，并解释了前两种策略的理论依据。

方法 1 和 2 的逻辑:

这两种方法的核心都依赖于定理1.3 ($L$ 是可判定的 $\Longleftrightarrow L$ 是可识别的且协同可识别的)。我们可以从这个定理的逆否命题来思考：

如果 $L$ 不是($L$ 可识别的 且 $L$ 协同可识别的)，那么 $L$ 是不可判定的。

这意味着，如果一个语言 $L$ 是不可判定的，那么它必然不满足“既可识别又协同可识别”这个条件。所以，至少下面一项成立：

• $L$ 是不可识别的。
• $L$ 不是协同可识别的（即 $\bar{L}$ 是不可识别的）。

方法1：证明 $L$ 是不可判定的且 $\bar{L}$ 是可识别的

• 我们已经知道 $L$ 是不可判定的。
• 我们又证明了 $\bar{L}$ 是可识别的。
• 假设 $L$ 是可识别的（为了引出矛盾）。
• 那么，我们现在有了：

1. $L$ 是可识别的（假设）。
2. $\bar{L}$ 是可识别的，即 $L$ 是协同可识别的（已知）。
   • 根据定理1.3，如果一个语言既可识别又协同可识别，那么它一定是可判定的。
   • 这与我们已知的“$L$ 是不可判定的”相矛盾。
   • 因此，最初的假设“$L$ 是可识别的”是错误的。
   • 结论：$L$ 必须是不可识别的。

方法2：证明 $\bar{L}$ 是可识别的但不可判定的

• 这与方法1本质上是同一个论证，只是观察角度不同。
• 我们已知 $\bar{L}$ 是可识别的。
• 我们已知 $\bar{L}$ 是不可判定的 (因为 $L$ 的可判定性等价于 $\bar{L}$ 的可判定性，所以证明 $\bar{L}$ 不可判定等同于证明 $L$ 不可判定)。
• 假设 $L$ 是可识别的（为了引出矛盾）。
• 这意味着 $\bar{L}$ 是协同可识别的 (因为 $L$ 可识别)。
• 那么，我们现在有了：

1. $\bar{L}$ 是可识别的（已知）。
2. $\bar{L}$ 是协同可识别的（由假设推出）。
   • 根据定理1.3，$\bar{L}$ 应该是可判定的。
   • 这与我们已知的“$\bar{L}$ 是不可判定的”相矛盾。
   • 结论：$L$ 必须是不可识别的。

示例分析：证明 $\overline{A_{T M}}$ 是不可识别的

这里，我们要证明的语言 $L$ 是 $\overline{A_{T M}}$。

1. 证明 $\overline{A_{T M}}$ 是不可判定的：我们已经知道 $A_{TM}$ 是不可判定的。由于一个语言是可判定的当且仅当其补集是可判定的，所以 $\overline{A_{T M}}$ 也一定是不可判定的。
2. 证明 $\overline{A_{T M}}$ 的补集是可识别的：$\overline{A_{T M}}$ 的补集是 $(\overline{\overline{A_{TM}}}) = A_{TM}$。我们已经知道 $A_{TM}$ 是可识别的（通用图灵机可以识别它）。
3. 应用方法1：令 $L = \overline{A_{TM}}$。我们有：
   • $L$ 是不可判定的。
   • $\bar{L} = A_{TM}$ 是可识别的。
   • 根据方法1的逻辑，我们可以得出结论：$L = \overline{A_{T M}}$ 是不可识别的。

方法3 和 4 的引入：

• 映射归约：这是本讲义的重点。它是一种更通用的证明技巧，特别是当一个语言和它的补集都不可识别时，前两种方法就失效了。例如，语言 $EQ_{TM}$（判断两个图灵机语言是否相等）和它的补集都是不可识别的。要证明这类问题，必须使用归约。
• 精炼的赖斯定理：这是赖斯定理的一个加强版，可以直接告诉我们一个关于图灵机语言的非平凡性质是不可识别的还是不可协同识别的，提供了另一条捷径。

这部分正式引入了映射归约 (Mapping Reduction)，也称为多一归约 (Many-one Reduction)。

定义2.1 (可计算函数):

• 可计算函数 $f$ 是一个可以被算法实现的函数。在计算理论中，最强大的计算模型是图灵机，所以“可计算”被精确地定义为“可由一台图灵机计算”。
• 这台图灵机（我们称之为 $T_f$）必须满足一个关键条件：对于任何输入字符串 $w$， $T_f$ 必须总是在有限时间内停机，并且当它停机时，其纸带上留下的内容恰好是 $f(w)$。
• “总停机”这个要求至关重要。这意味着函数 $f$ 的计算过程本身必须是一个可判定的过程。我们不能定义一个依赖于解决停机问题或其他不可判定问题的函数 $f$。

定义2.2 (映射归约):

• 映射归约是建立在可计算函数之上的一种关系，用来比较两个语言（问题）$A$ 和 $B$ 的难度。
• 我们说 $A$ 可映射归约到 $B$，记为 $A \leq_m B$，如果存在一个可计算函数 $f$，这个函数 $f$ 就像一个“翻译器”，它能把任何关于语言 $A$ 的问题实例 $w$ 转换成一个关于语言 $B$ 的问题实例 $f(w)$。
• 这个“翻译”必须是忠实的，即保持答案不变：
• 如果原始问题答案为“是”（$w \in A$），那么翻译后的问题答案也必须为“是”（$f(w) \in B$）。
• 如果原始问题答案为“否”（$w \notin A$），那么翻译后的问题答案也必须为“否”（$f(w) \notin B$）。
• 这个双向箭头 $\Longleftrightarrow$ 保证了这种忠实性。

定理2.3 (与图灵归约的关系):

• $A \leq_T B$ (图灵归约) 意味着我们可以用一个能解决 $B$ 的“黑箱”（神谕）来构造一个解决 $A$ 的算法。
• 映射归约是图灵归约的一种更强、更受限的形式。在映射归约中，我们只允许调用一次“神谕”$B$，并且是在计算出 $f(w)$ 之后，直接询问 $f(w)$ 是否在 $B$ 中，然后原封不动地返回答案。
• 所以，如果 $A \leq_m B$，那么显然 $A \leq_T B$。

定理2.4 (映射归约与可识别性):

这是利用映射归约证明不可识别性的理论基础。

1. 如果 $B$ 是可识别的，那么 $A$ 是可识别的。
   • 证明思路：假设 $B$ 是可识别的，存在识别器 $M_B$。我们要为 $A$ 构造一个识别器 $M_A$。
   • $M_A$ 在输入 $w$ 上工作如下：
   • 正确性：
   • 若 $w \in A$，则 $f(w) \in B$。$M_B$ 会接受 $f(w)$，因此 $M_A$ 会接受 $w$。
   • 若 $w \notin A$，则 $f(w) \notin B$。$M_B$ 不会接受 $f(w)$，因此 $M_A$ 也不会接受 $w$。
   • 这表明 $M_A$ 是 $A$ 的一个有效识别器，故 $A$ 是可识别的。
2. 如果 $A$ 是不可识别的，那么 $B$ 是不可识别的。
   • 这就是第1点的逆否命题。逻辑上是完全等价的。
   • 这个形式是我们实际应用中最常用的：为了证明 $B$ 是不可识别的，我们从一个已知的不可识别语言 $A$ 出发，然后构造一个从 $A$到 $B$ 的映射归约。

定理2.5 (与补集的关系):

• $A \leq_{m} B \Longleftrightarrow \bar{A} \leq_{m} \bar{B}$。
• 这个定理的证明非常直接。如果 $f$ 是 $A \leq_m B$ 的归约函数，那么对于任何 $w$：

$w \in A \Longleftrightarrow f(w) \in B$

• 两边同时取非，就得到：

$w \notin A \Longleftrightarrow f(w) \notin B$

• 这正好是：

$w \in \bar{A} \Longleftrightarrow f(w) \in \bar{B}$

• 这意味着同一个可计算函数 $f$ 也可以作为 $\bar{A} \leq_m \bar{B}$ 的归约函数。
• 应用：在证明 $L$ 的不可识别性时，我们想证明 $U \leq_m L$ (其中 $U$ 是已知的不可识别语言)。根据这个定理，我们也可以选择证明 $\bar{U} \leq_m \bar{L}$。有时，处理补集（例如 $A_{TM}$）比处理原语言（例如 $\overline{A_{TM}}$）要方便得多，因为 $A_{TM}$ 的定义更直接（“接受”），而 $\overline{A_{TM}}$ 的定义包含“拒绝或循环”以及格式错误的情况，比较复杂。

这部分提供了一个清晰、结构化的“食谱”，指导如何完成一个使用映射归约证明不可识别性的完整证明。

步骤 1：选择归约的起点

• 目标：证明语言 $L$ 是不可识别的。
• 策略：我们需要找到一个“垫脚石”，即一个我们已经知道是不可识别的语言 $U$。
• 最常用的已知不可识别语言：$\overline{A_{TM}}$ 是最经典的选择。它的定义是 $\{ \langle M, w \rangle \mid M \text{ 是一台图灵机且 } M \text{ 不接受 } w \}$。
• 选择归约形式：根据定理2.5，我们有两个选择：

1. 证明 $U \leq_m L$。
2. 证明 $\bar{U} \leq_m \bar{L}$。
   • 决策依据：比较 $U$ 和 $\bar{U}$，以及 $L$ 和 $\bar{L}$ 的定义。选择定义更清晰、逻辑更直接的一对进行归约。通常，包含“接受”或“停机”这种肯定性条件的语言（如 $A_{TM}$）比包含“不接受”、“循环”等否定性或复杂条件的语言（如 $\overline{A_{TM}}$）更容易处理。因此，如果我们的 $U$ 是 $\overline{A_{TM}}$，我们常常会选择证明 $\bar{U} (=A_{TM}) \leq_m \bar{L}$。

步骤 2：定义归约函数 $f$

• 这一步是整个证明的核心和最具创造性的部分。
• 任务：明确你选择的源语言 $A$ (例如 $A_{TM}$) 和目标语言 $B$ (例如 $\bar{L}$)，然后设计一个可计算函数 $f$。
• 函数 $f$ 的功能：$f$ 接受一个 $A$ 的实例 $w_A$ 作为输入，然后输出一个 $B$ 的实例 $w_B = f(w_A)$。这个 $f$ 通常是一个转换器，它读取输入的图灵机描述，并根据其逻辑构造一个新的图灵机描述。
• 关键要求 (可计算性)：$f$ 的计算过程必须总能停机。这意味着 $f$ 不能去尝试解决 $w_A$ 是否在 $A$ 中这个问题。它只能对 $w_A$ 的“语法结构”进行操作，生成一个新的字符串 $w_B$。

步骤 3：证明归约的正确性

这是对步骤 2 中设计的函数 $f$ 的严格验证。

• 子步骤 3a (构造 $f$ 的图灵机)：用高级语言描述一台计算 $f$ 的图灵机。例如：“在输入 $\langle M, w \rangle$ 上，构造一台新的图灵机 $M'$ 的描述，其中 $M'$ 的代码包含 $M$ 和 $w$。$M'$ 的行为是......最后，输出 $\langle M' \rangle$。”
• 子步骤 3b (确保可计算性)：再次检查你的描述，确保其中没有任何需要解决不可判定问题的隐藏步骤。
• 子步骤 3c (证明等价性)：这是逻辑证明部分，必须证明 $w \in A \Longleftrightarrow f(w) \in B$。这需要分两个方向进行：
• (i) 前向证明 ($w \in A \Longrightarrow f(w) \in B$)：假设 $w$ 在 $A$ 中，然后根据 $f$ 的构造逻辑，推导出 $f(w)$ 必然在 $B$ 中。
• (ii) 后向证明 ($w \notin A \Longrightarrow f(w) \notin B$)：假设 $w$ 不在 $A$ 中，然后根据 $f$ 的构造逻辑，推导出 $f(w)$ 必然不在 $B$ 中。
• 关于证明技巧的说明：有时，证明一个方向的逆否命题会更简单。
• 证明 "$w \in A \Longrightarrow f(w) \in B$" 等价于证明 "$f(w) \notin B \Longrightarrow w \notin A$"。
• 证明 "$w \notin A \Longrightarrow f(w) \notin B$" 等价于证明 "$f(w) \in B \Longrightarrow w \in A$"。
• 实践中，通常“假设 $w \in A$”和“假设 $w \notin A$”这两种直接的出发点更容易思考。

步骤 4：得出结论

• 连接逻辑链：在完成了 $A \leq_m B$ 的证明后，需要明确地写出最后的结论。
• 标准结论模板：

1. 我们已经证明了 $A \leq_m B$。
2. 我们知道源语言 $A$ 是不可识别的。
3. 根据定理2.4，如果一个不可识别的语言可以映射归约到另一个语言，那么后者也必须是不可识别的。
4. 因此，目标语言 $B$ 是不可识别的。
5. 如果你证明的是 $\bar{U} \leq_m \bar{L}$，那么你得出的结论是 $\bar{L}$ 是不可识别的。如果一个语言的补集不可识别，我们称这个语言是不可协同识别的。

这部分介绍了赖斯定理的加强版——精炼的赖斯定理（Refined Rice's Theorem），它不仅能判断一个语言是否不可判定，还能进一步指明它是不可识别还是不可协同识别。

回顾赖斯定理:

• 赖斯定理说：任何关于图灵机所识别的语言的非平凡性质都是不可判定的。
• 语言的性质：一个语言 $P$ 是“语言的性质”，意味着它只关心图灵机的语言 $L(M)$，而不关心图灵机 $M$ 的具体实现（状态数、纸带字母等）。如果两台图灵机 $M_1$ 和 $M_2$ 识别相同的语言 ($L(M_1)=L(M_2)$)，那么它们要么都属于 $P$，要么都不属于 $P$。
• 非平凡：$P$ 是非平凡的，意味着至少存在一台图灵机的编码在 $P$ 中，也至少存在一台图灵机的编码不在 $P$ 中。它不是空集也不是全集。

精炼的赖斯定理的动机:

• 赖斯定理告诉我们很多问题是不可判定的，比如 $E_{TM}$ (语言为空), $REG_{TM}$ (语言是正则的)。
• 根据定理1.3，一个不可判定的语言，要么是不可识别，要么是不可协同识别（或者两者都是）。
• 赖斯定理本身没有告诉我们是哪种情况。精炼的赖斯定理填补了这个空白。

定理3.1 (精炼的赖斯定理):

这个定理的适用条件和赖斯定理完全一样：语言 $P$ 必须是一个关于可识别语言的非平凡性质。

它增加了一个简单的判断标准，这个标准基于空语言。

• 令 $M_{\emptyset}$ 为一台识别空语言的图灵机，即 $L(M_{\emptyset}) = \emptyset$。例如，一个一启动就进入拒绝状态的图灵机。
• 定理的两个分支：

1. 如果 $\langle M_{\emptyset} \rangle \in P$ (空语言的性质为真)：
   • 这意味着性质 $P$ 包含空语言。
   • 结论：语言 $P$ 是不可识别的。
2. 如果 $\langle M_{\emptyset} \rangle \notin P$ (空语言的性质为假)：
   • 这意味着性质 $P$ 不包含空语言。
   • 结论：语言 $P$ 是不可协同识别的。
   • 不可协同识别意味着它的补集 $\bar{P}$ 是不可识别的。

理解其内在逻辑 (非严格):

这个定理的证明通常是通过从 $A_{TM}$ 或 $\overline{A_{TM}}$ 进行归约。

• 当 $\langle M_{\emptyset} \rangle \in P$ 时，证明 $\overline{A_{TM}} \leq_m P$ 是可行的。由于 $\overline{A_{TM}}$ 是不可识别的，所以 $P$ 也是不可识别的。
• 当 $\langle M_{\emptyset} \rangle \notin P$ 时，证明 $A_{TM} \leq_m P$ 是可行的。因为 $A_{TM}$ 是可识别的，这只能说明 $P$ 也是可识别的（这似乎与结论不符）。更准确地说，是证明 $A_{TM} \leq_m P$，因为 $A_{TM}$ 不可判定，所以 $P$ 不可判定。进一步的分析（这里省略）会发现，这种情况下 $P$ 是可识别的，因此它的补集 $\bar{P}$ 是不可识别的，即 $P$ 是不可协同识别的。

这部分将上一节介绍的精炼的赖斯定理具体化为一个四步操作流程，用于证明一个语言 $L$ 是不可识别的。

步骤 1：证明 $L$ 是一个语言性质

这是应用定理的第一个前提。

• 1a. 检查输入格式：首先要确认 $L$ 的成员都是图灵机的编码，即形如 $\langle M \rangle$ 的字符串。如果 $L$ 包含其他类型的字符串（比如 $\langle M, w \rangle$），那么赖斯定理不适用。
• 1b. 检查语义等价性：这是核心。必须证明，决定一个图灵机 $M$ 是否在 $L$ 中的唯一标准是它所识别的语言 $L(M)$。证明方法是：任取两个图灵机 $M_1$ 和 $M_2$，假设它们识别同一个语言 ($L(M_1) = L(M_2)$)。在此假设下，你需要证明 $\langle M_1 \rangle \in L$ 和 $\langle M_2 \rangle \in L$ 是等价的。

步骤 2：证明 $L$ 是非平凡的

这是应用定理的第二个前提。

• 2a. 证明性质存在：你需要构造或指出一台图灵机 $M_{yes}$，它的编码 $\langle M_{yes} \rangle$ 属于 $L$。这证明了 $L$ 不是空集。
• 2b. 证明性质并非普遍：你需要构造或指出另一台图灵机 $M_{no}$，它的编码 $\langle M_{no} \rangle$ 不属于 $L$。这证明了 $L$ 不是所有图灵机编码的集合。

步骤 3：检查空语言的归属

这是精炼的赖斯定理区别于普通赖斯定理的关键步骤。

• 定义一台图灵机 $M_{\emptyset}$，它不接受任何输入，因此 $L(M_{\emptyset}) = \emptyset$。
• 判断 $\langle M_{\emptyset} \rangle$ 是否属于 $L$。
• 如果你的目标是证明 $L$ 不可识别，你必须证明 $\langle M_{\emptyset} \rangle \in L$。

步骤 4：得出结论

• 如果步骤1、2、3全部满足，你就可以直接引用精炼的赖斯定理得出结论。
• 标准结论模板：

1. 根据步骤1，我们证明了 $L$ 是一个关于图灵机所识别语言的性质。
2. 根据步骤2，我们证明了该性质是非平凡的。
3. 根据步骤3，我们证明了识别空语言的图灵机满足此性质。
4. 因此，根据精炼的赖斯定理，$L$ 是不可识别的。

关于“不可协同识别”的说明:

• 如果在步骤3中，你发现 $\langle M_{\emptyset} \rangle \notin L$，那么你无法证明 $L$ 是不可识别的。
• 此时，你的结论应该改为：根据精炼的赖斯定理，$L$ 是不可协同识别的。
• 这意味着 $\bar{L}$ 是不可识别的。如果题目要求证明 $\bar{L}$ 不可识别，这也是一个有效的证明路径。

示例分析:

• $E_{TM} = \{\langle M \rangle \mid L(M)=\emptyset\}$

1. 性质：是。
2. 非平凡：是。
3. 空语言：$L(M_{\emptyset})=\emptyset$，满足 $E_{TM}$ 的条件，所以 $\langle M_{\emptyset} \rangle \in E_{TM}$。
4. 结论：$E_{TM}$ 是不可识别的。
   • $REG_{TM} = \{\langle M \rangle \mid L(M) \text{ 是正则的}\}$
5. 性质：是。
6. 非平凡：是。正则语言存在（如 $\emptyset$），非正则语言也存在（如 $\{0^n1^n\}$）。
7. 空语言：$L(M_{\emptyset})=\emptyset$。空语言是一个正则语言（它可以被一个没有接受状态的DFA识别）。所以 $\langle M_{\emptyset} \rangle \in REG_{TM}$。
8. 结论：$REG_{TM}$ 是不可识别的。
   • $\overline{ALL_{TM}} = \{\langle M \rangle \mid L(M) \neq \Sigma^*\}$
9. 性质：是。
10. 非平凡：是。
11. 空语言：$L(M_{\emptyset})=\emptyset$。显然 $\emptyset \neq \Sigma^*$。所以 $L(M_{\emptyset})$ 满足性质 “不等于 $\Sigma^*$”。因此 $\langle M_{\emptyset} \rangle \in \overline{ALL_{TM}}$。
12. 结论：$\overline{ALL_{TM}}$ 是不可识别的。

这部分列出了一些在可计算性理论中非常重要的、作为基准的不可识别语言。这些语言经常被用作“已知困难问题”的起点，通过映射归约来证明其他新问题的难度。

已证明的不可识别语言：

• $\overline{A_{TM}}$ (非接受性问题):
• 定义: $\{\langle M, w\rangle \mid M \text{ 不接受 } w\}$。
• 不可识别性原因: 它的补集 $A_{TM}$ 是可识别的（通过通用图灵机模拟），但 $A_{TM}$ 本身是不可判定的。根据方法1，$\overline{A_{TM}}$ 是不可识别的。这是所有不可识别问题的“鼻祖”，许多归约都从它开始。

• $E_{TM}$ (空语言问题):
• 定义: $\{\langle M\rangle \mid L(M)=\emptyset\}$。
• 不可识别性原因: 可以通过从 $\overline{A_{TM}}$ 进行映射归约来证明。也可以使用精炼的赖斯定理：这是一个关于语言的非平凡性质，且识别空语言的图灵机 $M_{\emptyset}$ 满足此性质，因此 $E_{TM}$ 是不可识别的。

• $ALL_{TM}$ (全语言问题):
• 定义: $\{\langle M\rangle \mid L(M)=\Sigma^*\}$。
• 这个语言本身是不可协同识别的，而不是不可识别的。这意味着它本身是可识别的（这个结论不正确，原文可能存在笔误或者语境省略。实际上 $ALL_{TM}$ 和它的补集都是不可识别的。更准确地说，根据精炼的赖斯定理，因为它不包含空语言，所以它是不可协同识别的）。
• 证明通常通过从 $A_{TM}$ 映射归约到 $ALL_{TM}$。
• 讲义原文此处可能有误或不精确。标准的结论是 $ALL_{TM}$ 是不可协同识别的。

• $\overline{ALL_{TM}}$ (非全语言问题):
• 定义: $\{\langle M\rangle \mid L(M) \neq \Sigma^*\}$。
• 不可识别性原因: 这是 $ALL_{TM}$ 的补集。由于 $ALL_{TM}$ 是不可协同识别的，根据定义，它的补集 $\overline{ALL_{TM}}$ 就是不可识别的。也可以用精炼的赖斯定理证明：这是一个非平凡的语言性质，且 $M_{\emptyset}$ 满足此性质 ($L(M_{\emptyset})=\emptyset \neq \Sigma^*$)，因此 $\overline{ALL_{TM}}$ 是不可识别的。

未证明但重要的不可识别/不可协同识别语言：

• $\overline{HALT_{TM}}$ (不停机问题):
• 定义: $\{\langle M, w\rangle \mid M \text{ 在 } w \text{ 上无限循环}\}$。
• 不可识别性: 类似于 $\overline{A_{TM}}$ 的情况。它的补集 $HALT_{TM}$ (停机问题) 是可识别的（模拟即可）但不可判定的。因此，$\overline{HALT_{TM}}$ 是不可识别的。

• $EQ_{TM}$ (等价性问题):
• 定义: $\{\langle M_1, M_2\rangle \mid L(M_1) = L(M_2)\}$。
• 复杂性: 这个问题“非常难”。它不仅不可判定，而且它和它的补集 $\overline{EQ_{TM}}$ 都是不可识别的。
• 证明思路: 通常通过从 $E_{TM}$ 映射归约到 $EQ_{TM}$ 来证明其不可协同识别性 ($E_{TM} \leq_m EQ_{TM}$)。然后通过从 $\overline{E_{TM}}$ 映射归约到 $EQ_{TM}$ 来证明其不可识别性（这里需要更复杂的归约）。

• $REG_{TM}$ (正则性问题):
• 定义: $\{\langle M\rangle \mid L(M) \text{ 是一个正则语言}\}$。
• 不可识别性: 可以使用精炼的赖斯定理。这是一个非平凡的语言性质，并且 $M_{\emptyset}$ (其语言为空集 $\emptyset$) 的语言是正则的，所以 $\langle M_{\emptyset} \rangle \in REG_{TM}$。因此，$REG_{TM}$ 是不可识别的。

这部分提供了一系列练习题，旨在巩固本讲义介绍的概念和证明技巧。

练习题 1: 证明 $L=\{\langle M, D\rangle \mid L(M)=L(D)\}$ 是不可协同识别的

• 目标: 证明 $\bar{L}$ 是不可识别的。
• 分析: $\bar{L} = \{\langle M, D\rangle \mid L(M) \neq L(D)\}$。这个问题看起来和 $EQ_{TM}$（等价性问题）的补集 $\overline{EQ_{TM}}$ 有关。一个更简单的方法可能是从一个已知的不可识别语言归约到 $\bar{L}$。
• 思路: 我们尝试从 $E_{TM}$ 的补集 $\overline{E_{TM}} = \{ \langle M \rangle \mid L(M) \neq \emptyset \}$ 进行归约。我们知道 $\overline{E_{TM}}$ 是不可识别的（这是错误的，$\overline{E_{TM}}$ 是可识别的但不可判定的；$E_{TM}$ 才是不可识别的）。
• 修正思路: 让我们从一个已知的不可识别语言归约到 $\bar{L}$。一个好的选择是 $E_{TM} = \{ \langle M \rangle \mid L(M) = \emptyset \}$。我们来证明 $E_{TM} \leq_m \bar{L}$。
• 函数 $f$ 的构造:
• 输入: $\langle M \rangle$ (一个图灵机的编码)
• 输出: $\langle M', D \rangle$ (一个图灵机和一个DFA的编码)
• 我们需要巧妙地选择 $M'$ 和 $D$。让 $D$ 固定为一个识别空语言的DFA，例如 $D_{empty}$，它没有任何接受状态。
• 令 $M' = M$。
• 所以 $f(\langle M \rangle) = \langle M, D_{empty} \rangle$。
• 证明归约正确性:
• $\langle M \rangle \in E_{TM} \implies L(M) = \emptyset$。因为 $L(D_{empty}) = \emptyset$，所以 $L(M) = L(D_{empty})$。这意味着 $\langle M, D_{empty} \rangle \notin \bar{L}$。
• 这个方向反了！ 我们需要 $w \in A \implies f(w) \in B$。
• 再次修正思路: 证明 $E_{TM} \leq_m \bar{L}$ 失败了。让我们尝试证明 $A_{TM} \leq_m \bar{L}$ 怎么样？这个看起来也不直接。
• 最终正确思路 (从 $\overline{E_{TM}}$ 归约): 我们知道 $\overline{E_{TM}}$ 是不可协同识别的。让我们证明 $\overline{E_{TM}} \le_m L$。
• 再次审题: 题目是证明 $L$ 是不可协同识别的，即证明 $\bar{L}$ 是不可识别的。让我们从 $ALL_{TM}$ 归约，我们知道 $ALL_{TM}$ 是不可协同识别的，但它的补集 $\overline{ALL_{TM}}$ 是不可识别的。我们证明 $\overline{ALL_{TM}} \leq_m \bar{L}$。
• 函数 $f$ 的构造:
• 输入: $\langle M \rangle$
• 输出: $\langle M', D \rangle$
• 选择一个固定的 $D$。让 $D_{all}$ 是一个识别所有字符串 $\Sigma^*$ 的DFA (例如，一个单状态的、既是起始态又是接受态的DFA)。
• 令 $M' = M$。
• 所以 $f(\langle M \rangle) = \langle M, D_{all} \rangle$。
• 证明归约正确性:
• $\langle M \rangle \in \overline{ALL_{TM}} \implies L(M) \neq \Sigma^*$。因为 $L(D_{all}) = \Sigma^*$，所以 $L(M) \neq L(D_{all})$。这意味着 $f(\langle M \rangle) = \langle M, D_{all} \rangle \in \bar{L}$。
• $\langle M \rangle \notin \overline{ALL_{TM}} \implies L(M) = \Sigma^*$。因为 $L(D_{all}) = \Sigma^*$，所以 $L(M) = L(D_{all})$。这意味着 $f(\langle M \rangle) = \langle M, D_{all} \rangle \notin \bar{L}$。
• 结论: 我们证明了 $\overline{ALL_{TM}} \leq_m \bar{L}$。因为 $\overline{ALL_{TM}}$ 是不可识别的，所以 $\bar{L}$ 也是不可识别的。因此，$L$ 是不可协同识别的。

练习题 2: 证明 $L=\{\langle M\rangle \mid M \text{ 不接受长度 } \geq 50 \text{ 的字符串}\}$ 是不可识别的

• 思路: 使用精炼的赖斯定理。
• 步骤 1 (性质): $L$ 是一个语言性质，因为它只取决于 $L(M)$ 是否包含长度 $\geq 50$ 的字符串。
• 步骤 2 (非平凡):
• 存在图灵机在 $L$ 中：例如 $M_{empty}$，其语言为空，不含任何长度 $\geq 50$ 的串。$\langle M_{empty} \rangle \in L$。
• 存在图灵机不在 $L$ 中：例如 $M_{all}$，其语言为 $\Sigma^*$，包含所有长度 $\geq 50$ 的串。$\langle M_{all} \rangle \notin L$。
• 步骤 3 (空语言):
• $L(M_{\emptyset}) = \emptyset$。空语言中没有任何字符串，自然也就不包含长度 $\geq 50$ 的字符串。
• 因此，$\langle M_{\emptyset} \rangle \in L$。
• 步骤 4 (结论): 根据精炼的赖斯定理，因为这是一个包含空语言的非平凡性质，所以 $L$ 是不可识别的。

练习题 3: 证明可识别语言在连接运算下是封闭的

• 目标: 证明若 $L_1, L_2$ 可识别，则 $L_3 = L_1 \cdot L_2$ 也可识别。
• 分析: $L_3 = \{ w \mid w = xy, \text{ 其中 } x \in L_1, y \in L_2 \}$。我们需要构造一个识别 $L_3$ 的图灵机 $M_3$。
• 思路 (非确定性): 使用非确定性图灵机 (NTM) 会让证明非常简单。
• 设 $M_1$ 和 $M_2$ 分别是 $L_1$ 和 $L_2$ 的识别器。
• 构造 NTM $M_3$ on input $w$:

1. 非确定性地将 $w$ 分割成两部分 $x$ 和 $y$ ($w=xy$)。
2. 将 $x$ 作为输入，模拟 $M_1$。
3. 如果 $M_1$ 接受 $x$，则继续将 $y$ 作为输入，模拟 $M_2$。
4. 如果 $M_2$ 也接受 $y$，则 $M_3$ 接受 $w$。
5. 在任何其他情况（分割不成功，或 $M_1$ 不接受，或 $M_2$ 不接受），该计算分支死亡或拒绝。
   • 正确性: 如果 $w \in L_3$，那么必然存在一种分割方式 $w=xy$ 使得 $x \in L_1$ 且 $y \in L_2$。$M_3$ 会有一条计算路径对应这个分割，并且在这条路径上 $M_1$ 和 $M_2$ 都会接受，最终 $M_3$ 接受。如果 $w \notin L_3$，那么对于所有可能的分割，$M_1$ 或 $M_2$ 至少有一个不接受，所以 $M_3$ 没有任何一条计算路径会接受。
   • 因为 NTM 识别的语言等价于 DTM（确定性图灵机）识别的语言，所以 $L_3$ 是可识别的。

练习题 4: 证明 $A \leq_m A$

• 思路: 我们需要找到一个可计算函数 $f$，使得 $w \in A \Longleftrightarrow f(w) \in A$。
• 构造: 选择最简单的可计算函数——恒等函数 $f(w) = w$。
• 证明: $w \in A \Longleftrightarrow w \in A$。这显然成立。
• 结论: 任何语言都可以映射归约到其自身。这体现了 $\leq_m$ 的自反性。

练习题 5: 必然有 $A \leq_m \bar{A}$ 吗？

• 回答: 否。
• 反例:
• 设 $A = A_{TM}$。我们知道 $A_{TM}$ 是可识别的，但不是协同可识别的（即 $\overline{A_{TM}}$ 是不可识别的）。
• 假设 $A_{TM} \leq_m \overline{A_{TM}}$。
• 根据定理2.4的第一条，“如果 $B$ 是可识别的，那么 $A$ 是可识别的”。
• 它的逆否命题是“如果 $A$ 是不可识别的，那么 $B$ 是不可识别的”。
• 我们在这里有 $A=A_{TM}$ (可识别), $B=\overline{A_{TM}}$ (不可识别)。
• 如果 $A_{TM} \leq_m \overline{A_{TM}}$ 成立，那么根据定理2.4，如果 $\overline{A_{TM}}$ 是可识别的，则 $A_{TM}$ 也是可识别的。这没有矛盾。
• 但是，让我们考虑其补集。如果 $A \leq_m \bar{A}$，那么 $\bar{A} \leq_m \overline{\bar{A}} = A$。
• 所以我们有 $\overline{A_{TM}} \leq_m A_{TM}$。
• 再次应用定理2.4：我们知道源语言 $\overline{A_{TM}}$ 是不可识别的。目标语言 $A_{TM}$ 是可识别的。
• 定理告诉我们，如果源语言不可识别，则目标语言也必须不可识别。
• 这里，源 ($\overline{A_{TM}}$) 是不可识别的，但目标 ($A_{TM}$) 是可识别的。这就产生了矛盾。
• 因此，假设 “$\overline{A_{TM}} \leq_m A_{TM}$” 必须是错误的。
• 既然 $\overline{A_{TM}} \leq_m A_{TM}$ 不成立，那么 $A_{TM} \leq_m \overline{A_{TM}}$ 也不成立。
• 所以，不是必然有 $A \leq_m \bar{A}$。

本讲义（Handout 10a）系统性地引导我们从可判定性的边界之外，进入一个更深、更复杂的计算理论领域：不可识别性。它不仅定义了什么是不可识别的语言，更重要的是，提供了三大武器来证明一个语言属于这个“最难”的计算问题类别。

首先，讲义通过回顾可识别（Recognizable）和协同可识别（Co-recognizable）的定义，并重申关键的定理1.3（$L$ 可判定 $\iff L$ 可识别且协同可识别），为“不可识别性”的出现铺平了道路。这个定理揭示了，一个不可判定的问题，其“病因”必然是“不可识别”或“不可协同可识别”（或两者都是）。这直接引出了第一个证明策略：补集法。如果我们能证明一个语言 $L$ 是不可判定的，同时其补集 $\bar{L}$ 是可识别的，那么 $L$ 必定是不可识别的。经典的 $\overline{A_{TM}}$ 就是通过这种方法被证明为不可识别的。

然而，补集法有其局限性。当一个语言和它的补集都不可识别时，此法便无能为力。为了应对更广泛的场景，讲义引入了第二个，也是最核心的武器：映射归约 ($A \leq_m B$)。映射归约是一种形式化的方法，用以证明“问题A不比问题B难”。它的强大之处在于其逆否命题的应用：如果我们从一个已知的不可识别语言 $A$ 出发，成功地构造了一个到目标语言 $B$ 的映射归约，那么我们就能断定 $B$ 也一定是不可识别的。讲义详细地拆解了构造一个有效归约的步骤：选择源语言、定义可计算的转换函数 $f$、并严谨地证明转换的逻辑等价性。这个工具的灵活性通过定理2.5 ($A \leq_m B \iff \bar{A} \leq_m \bar{B}$) 得到进一步增强，允许我们在原语言和其补集之间选择更容易处理的一对来进行归约。

最后，讲义介绍了第三个武器，一个优雅的“快捷方式”——精炼的赖斯定理。作为赖斯定理的加强版，它适用于所有关于图灵机语言的非平凡性质。它提供了一个极其简单的判据：只需检查识别空语言的图灵机 $M_{\emptyset}$ 是否满足该性质，就能直接判断该性质对应的语言是不可识别的（若满足）还是不可协同识别的（若不满足）。这为我们快速判断如 $E_{TM}$, $REG_{TM}$, $\overline{ALL_{TM}}$ 等一大类问题的不可识别性提供了极大的便利。

讲义通过列举一系列经典的不可识别语言（如 $\overline{A_{TM}}$, $E_{TM}$, $EQ_{TM}$ 等），为我们建立了一个“困难问题”的坐标系。这些问题不仅是理论上的重要里程碑，也成为我们进行新的归约证明时的“弹药库”。最后的练习题则旨在通过实践，让我们熟练掌握这三大武器，并深刻理解可计算性的层次结构和其内在的不对称性。