📜 [原文1]
Owen Keith 和 Owen Terry<br>COMS 3261 2024 年秋季
这部分内容指明了该讲义的作者是 Owen Keith 和 Owen Terry，并且这份材料是为哥伦比亚大学的课程 COMS 3261（计算机科学理论）在 2024 年秋季学期所准备的。这为讲义提供了出处和背景信息，帮助学生和读者了解其来源和适用范围。
本节清晰地标明了讲义的作者、所属课程和学期。
这部分的存在是为了确保学术诚信，明确知识产权归属，并为学习者提供课程背景信息，方便他们将资料与具体的教学活动联系起来。
这就像一本书的封面，上面写着书名、作者和出版社。它告诉你这本书是谁写的，属于哪个系列，让你对它的内容有一个初步的定位。
想象你拿到一本武功秘籍，第一页写着“华山派，剑宗，风清扬著，甲子年秋”。你立刻就知道了这本秘籍的门派、分支、作者和年代，对接下来的内容有了基本的预期。
📜 [原文2]
无练习。
这部分说明在“可数性”（Countability）这个主题下，本讲义没有提供相关的练习题。可数性是计算理论中的一个基础数学概念，用于区分集合的大小，特别是区分有限集、可数无穷集（如自然数集）和不可数无穷集（如实数集）。虽然这里没有练习，但这个概念是理解为什么有些问题（如所有可能的图灵机的集合是可数的）而有些不是（如所有可能的语言的集合是不可数的）的基础。
本节表明关于可数性理论部分没有附加练习题。
这部分的存在是为了告知读者，本讲义的重点在于后续的图灵归约和不可判定性，而可数性只是作为一个背景知识前提，在此不作深入练习。
这就像课程表上的一节课被标记为“复习，无作业”。老师会带你回顾一下之前的知识点，但不会布置新的练习，目的是让你把精力集中在接下来的新内容上。
想象你在一个博物馆参观，走到一个展厅门口，牌子上写着“史前文明展厅（背景介绍，无互动展品）”。你知道这里是为了让你了解一些基础背景，为参观后面的主展厅做铺垫，所以你快速浏览一下，然后走向重点区域。
📜 [原文3]
证明 $H A L T_{T M} \leq_{T} A_{T M}$。
证明. 注意，在此处以及所有后续的图灵机描述中，都隐含着输入应对应一个有效的编码，否则图灵机将拒绝。对于此问题，这意味着我们省略了隐含的第一步：“如果 $\langle M, w\rangle$ 是一个无效编码，则拒绝。”
假设存在一个 $A_{T M}$ 的判定器 $\mathcal{O}$。我们将使用 $\mathcal{O}$ 构造一个 $H A L T_{T M}$ 的判定器 R，如下所示：
R，在输入 $\langle M, w\rangle$ 上：
在 $\langle M, w\rangle$ 上运行 $\mathcal{O}$。如果 $\mathcal{O}$ 接受，则接受。
准备 $\left\langle M^{\prime}\right\rangle$，其中
$M^{\prime}=$ “在输入 $x$ 上，运行 $M$ 在 $x$ 上。
如果 $M$ 接受，则拒绝。
如果 $M$ 拒绝，则接受。”
在 $\left\langle M^{\prime}, w\right\rangle$ 上运行 $\mathcal{O}$。如果 $\mathcal{O}$ 接受，则接受。
拒绝。
如果 $\langle M, w\rangle \in H A L T_{T M}$，那么 $M$ 要么接受 $w$，要么拒绝 $w$。在前一种情况下，$\mathcal{O}$ 接受 $\langle M, w\rangle$。在后一种情况下，$M^{\prime}$ 接受 $w$，因此 $\mathcal{O}$ 接受 $\left\langle M^{\prime}, w\right\rangle$。无论哪种情况，R 都接受 $\langle M, w\rangle$。
如果 $\langle M, w\rangle \notin H A L T_{T M}$，那么 $M$ 在 $w$ 上无限运行。因此，$M^{\prime}$ 也在 $w$ 上无限运行。因此，$\langle M, w\rangle \notin A_{T M}$ 且 $\left\langle M^{\prime}, w\right\rangle \notin A_{T M}$，所以 $\mathcal{O}$ 拒绝这两种情况。因此，R 拒绝 $\langle M, w\rangle$。
这个证明的目标是展示停机问题（$H A L T_{T M}$）可以图灵归约到接受问题（$A_{T M}$）。这意味着，如果我们有一个能解决接受问题的“神谕”（oracle），我们就能利用它来解决停机问题。
该证明通过构造一个判定器 R，利用一个假设存在的 $A_{T M}$ 判定器（神谕）$\mathcal{O}$，成功地解决了 $H A L T_{T M}$ 问题。R 通过两次询问 $\mathcal{O}$，一次直接问 $M$ 是否接受 $w$，一次问“反向的”$M'$ 是否接受 $w$，覆盖了 $M$ 停机的两种情况（接受或拒绝）。如果两次询问都得不到“是”的答复，则说明 $M$ 一定是无限循环。这表明任何能解决 $A_{T M}$ 的方法都能被用来解决 $H A L T_{T M}$，从而确立了 $H A L T_{T M} \leq_T A_{T M}$ 的归约关系。
这个证明的目的是建立计算理论中两个核心不可判定问题（$A_{T M}$ 和 $H A L T_{T M}$）之间的难度关系。我们已经知道 $A_{T M}$ 是不可判定的，通过证明 $H A L T_{T M} \leq_T A_{T M}$，我们可以理解这两个问题的难度是“同级别的”。更重要的是，图灵归约是证明其他新问题不可判定性的强大工具。
想象一下，你有一个神奇的朋友 $\mathcal{O}$，他只能回答“是”或“不是”关于“某个文件A是否包含关键词'success'”的问题 ($A_{T M}$)。现在你想解决一个不同的问题：判断“某个程序M在处理文件w时会不会死机” ($H A L T_{T M}$)。
你怎么利用你的朋友 $\mathcal{O}$ 呢？
一个程序不死机，意味着它最终会结束，要么报告 'success' (接受)，要么报告 'failure' (拒绝)。
通过这两次询问，你完美地解决了“会不会死机”的问题。你把 $H A L T_{T M}$ 归约到了 $A_{T M}$。
想象你是一个医生 R，想要判断一个病人 M 吃下某种食物 w 后是否会“停止消化”（停机）。你有一个神奇的检测仪 $\mathcal{O}$，但它只能检测“病人是否吸收了营养”（接受）。
通过这个过程，你使用一个只能检测“吸收”的仪器，成功地判断了更复杂的“是否停止消化”的问题。
📜 [原文4]
证明 $L=\{\langle M, D\rangle \mid M$ 是一个图灵机，$D$ 是一个DFA，并且 $L(M)=L(D)\}$ 是不可判定的。
证明. 我们将通过证明 $A_{T M} \leq_{T} L$ 来证明这一点。假设存在一个 $L$ 的判定器 $\mathcal{O}$。我们将使用 $\mathcal{O}$ 构造一个 $A_{T M}$ 的判定器 R，如下所示：
R，在输入 $\langle M, w\rangle$ 上：
创建新图灵机 $\left\langle M^{\prime}\right\rangle$ 的编码，如下所示：$M^{\prime}$，在输入 $x$ 上：
如果 $x \neq w$，则拒绝。
如果 $x=w$，则在 $w$ 上运行 $M$。如果 $M$ 接受，则接受。否则，拒绝。
创建新 DFA $\left\langle D^{\prime}\right\rangle$ 的编码，使得 $L\left(D^{\prime}\right)=L(w)=\{w\}$。这是可行的，因为我们知道从正则表达式构造 DFA 的算法。
在 $\left\langle M^{\prime}, D^{\prime}\right\rangle$ 上运行 $\mathcal{O}$ 并输出相同结果。
如果 $\langle M, w\rangle \in A_{T M}$，那么 $M$ 接受 $w$。因此，$M^{\prime}$ 接受 $w$ 并拒绝其他所有输入，所以 $L\left(M^{\prime}\right)=w$。因此，$L\left(M^{\prime}\right)=L\left(D^{\prime}\right)$，所以 $\mathcal{O}$ 接受 $\left\langle M^{\prime}, D^{\prime}\right\rangle$。因此，R 接受 $\langle M, w\rangle$。
如果 $\langle M, w\rangle \notin A_{T M}$，那么 $M$ 不接受 $w$。因此，$L\left(M^{\prime}\right)=\emptyset$。因此，$L\left(M^{\prime}\right) \neq L\left(D^{\prime}\right)$ 因为 $L\left(D^{\prime}\right)=\{w\}$。因此，$\mathcal{O}$ 拒绝 $\left\langle M^{\prime}, D^{\prime}\right\rangle$，因此 R 拒绝 $x$。
这个证明的目标是展示一个新问题 L 是不可判定的。所使用的策略是归约：从一个已知的不可判定问题（这里是 $A_{T M}$）归约到 L。这就像说：“如果我能解决 L，我就能解决 $A_{T M}$。但我们已经知道 $A_{T M}$ 是解决不了的，所以 L 也肯定解决不了。”
假设我们要用 R 判定 $\langle M, \text{"abc"} \rangle$ 是否属于 $A_{T M}$。
这个证明通过一个巧妙的归约，展示了如何证明一个关于“语言相等”的问题是不可判定的。它将一个已知的不可判定问题 $A_{T M}$ 的实例 $\langle M, w \rangle$ 转化为一个 L 问题的新实例 $\langle M', D' \rangle$。这个转化的关键在于构造的 $M'$，它的语言要么是 $\{w\}$ 要么是 $\emptyset$，这完全取决于 $M$ 是否接受 $w$。通过向判定 L 的神谕询问 $L(M')$ 是否等于 $L(D') = \{w\}$，我们就能反推出 $M$ 是否接受 $w$，从而解决了 $A_{T M}$。由于 $A_{T M}$ 是不可判定的，因此 L 也必须是不可判定的。
这个练习的目的是训练学生使用图灵归约来证明新的问题是不可判定的。它展示了一种非常常见的归约模式：将一个关于图灵机在单一输入上行为的问题 ($A_{T M}$)，转化为一个关于图灵机的整个语言性质的问题 (L)。这是计算理论中一个核心的证明技巧。
假设你是一个星际法官 R，需要判断一个外星人 M 是否会说“你好”这个词 ($A_{T M}$)。但你手下只有一个机器人助手 $\mathcal{O}$，他非常死板，只会比较两本书的内容是否完全一样 (L)。
你怎么利用这个助手？
你通过一个只会“比较书籍”的傻瓜机器人，成功判断了一个外星人“会不会说某个词”的复杂问题。你把 $A_{T M}$ 归约到了 L。
想象你是一个化学家 R，想知道一种神秘物质 M 与试剂 w 混合后是否会产生金色沉淀（接受）。你只有一个非常特殊的分析仪 $\mathcal{O}$，它不能直接测沉淀颜色，但能精确判断“两种溶液的化学成分是否完全相同”。
通过这种方式，你用一个“成分比较仪”解决了“是否产生金色沉淀”的问题。
📜 [原文5]
证明以下是等价的：$A \leq_{T} B, \bar{A} \leq_{T} B, A \leq_{T} \bar{B}, \bar{A} \leq_{T} \bar{B}$。
证明. $1 \Longrightarrow$ 2: 设 $A \leq_{T} B$。因此，如果存在 $B$ 的判定器 $\mathcal{O}$，我们可以为 $A$ 创建一个判定器 $R$。在输入 $x$ 上，令 $R^{\prime}$ 在 $x$ 上运行 $R$ 并返回相反的结果。$R^{\prime}$ 是使用 $\mathcal{O}$ 的 $\bar{A}$ 的判定器，因为 $x \in \bar{A} \Longleftrightarrow R$ 拒绝 $\Longleftrightarrow R^{\prime}$ 接受，并且 $x \notin \bar{A} \Longleftrightarrow R$ 接受 $\Longleftrightarrow R^{\prime}$ 拒绝。因此，$\bar{A} \leq_{T} B$。
$2 \Longrightarrow$ 3: 设 $\bar{A} \leq_{T} B$。因此，如果存在 $B$ 的判定器，那么存在 $\bar{A}$ 的判定器。假设我们有一个 $\bar{B}$ 的判定器 $\mathcal{O}^{\prime}$，那么我们必须有一个 $B$ 的判定器 $\mathcal{O}$，即在输入 $x$ 上，$\mathcal{O}$ 在 $x$ 上运行 $\mathcal{O}^{\prime}$ 并返回相反的结果。现在，由于我们有一个 $B$ 的判定器，并且由于我们假设 $\bar{A} \leq_{T} B$，我们必须有一个 $\bar{A}$ 的判定器 $R^{\prime}$。所以，我们必须有一个 $A$ 的判定器 $R$，即在输入 $x$ 上，$R$ 在 $x$ 上运行 $R^{\prime}$ 并返回相反的值。
$3 \Longrightarrow$ 4: 设 $\bar{A} \leq_{T} \bar{B}$。因此，如果存在 $\bar{B}$ 的判定器 $\mathcal{O}$，我们可以为 $\bar{A}$ 创建一个判定器 R。令 $\mathrm{R}^{\prime}$ 运行 R 并返回相反的结果。$\mathrm{R}^{\prime}$ 是使用 $\mathcal{O}$ 的 A 的判定器。因此，$A \leq_{T} \bar{B}$。$4 \Longrightarrow$ 1: 设 $A \leq_{T} \bar{B}$。如果存在 $B$ 的判定器 $\mathcal{O}$，那么我们可以通过运行 $\mathcal{O}$ 并返回相反结果来为 $\bar{B}$ 创建一个判定器 $\mathcal{O}^{\prime}$。但由于 $A \leq_{T} \bar{B}$，我们可以使用 $\mathcal{O}^{\prime}$ 来为 A 创建一个判定器。因此，$A \leq_{T} B$。
这个练习要求证明四个关于图灵归约的命题是等价的。这意味着只要其中一个成立，其他三个也必然成立。证明策略是展示一个蕴含关系的循环：$1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$。
核心概念:
分步证明解析:
结论: 我们已经证明了 $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$ 的循环，因此这四个命题是等价的。
让我们用具体的语言来感受一下。令 $A = A_{T M}$，这是一个不可判定但可识别的语言。令 $B = H A L T_{T M}$，这也是一个不可判定但可识别的语言。（注意：$A_{TM}$ 和 $HALT_{TM}$ 都不是可判定的，所以这里不能真的构建判定器，只是一个思想实验）。
这个例子展示了，图灵归约衡量的“难度”与语言是否可识别（图灵机层级结构）不完全一样。它只关心在有神谕帮助的情况下是否可判定。
该证明通过一个逻辑链（$1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$）展示了四个关于图灵归约的命题是相互等价的。核心思想是，图灵归约下的“神谕”是一个完整的判定器，它能明确回答“是”或“否”。因此，如果一个语言 B 可被神谕判定，那么它的补集 $\bar{B}$ 也等效地可被判定（只需将神谕的答案反转）。同理，如果我们利用神谕构造了一个判定器 R 来判定 A，我们也能立刻得到 $\bar{A}$ 的判定器。这种对称性导致了这四个命题的等价。
这个练习的目的是揭示图灵归约的一个重要性质：它对语言的补集运算是对称和封闭的。这意味着在讨论图灵等价类（所有与某个问题相互图灵归约的问题的集合）时，一个语言和它的补集总是在同一个等价类里。这简化了问题的分类，因为我们不需要区分一个问题和它的补问题哪个“更难”。
[直觉心-智模型]
想象图灵归约 $A \leq_T B$ 就像说：“如果我有一本能解答所有关于B的是非题的答案书，我就能通过查阅这本书和做一些简单的逻辑推理，来解答所有关于A的是非题。”
想象A和B是两个神秘的房间，进入房间需要回答一个密码问题。$A \leq_T B$ 意味着“如果你知道B房间的密码生成规则，你就能推算出A房间的密码”。
这个比喻说明，在拥有一个完整的“规则手册”（判定器）的前提下，知道一个东西“是”什么，和知道它“不是”什么，是等价的信息。因此，在图灵归约的框架下，对问题或神谕进行取反操作不会改变问题的相对难度。
📜 [原文6]
莱斯定理是否适用于以下语言？如果不适用，请证明该语言是否可判定。要应用莱斯定理来证明语言 $P$ 是不可判定的，$P$ 必须满足以下条件：
这部分首先阐述了应用莱斯定理（Rice's Theorem）的前提条件。莱斯定理是一个非常强大的工具，可以用来快速证明许多关于图灵机行为的问题是不可判定的。
莱斯定理的内容: 如果一个语言 P 满足以上所有三个条件，那么 P 是不可判定的。
莱斯定理提供了一个模板，用于快速识别一大类关于图灵机的不可判定问题。要使用此定理，必须验证三个条件：问题是关于图灵机的，问题是非平凡的，且问题只依赖于图灵机所接受的语言，而与机器的内部构造无关。
这部分的存在是为了引出并清晰地定义莱斯定理及其适用范围。它使得后续的许多证明过程可以被大大简化，避免了为每一个类似的问题都从头开始进行复杂的归约证明。
莱斯定理就像一个“AI鉴别器”的法则。假设你想判断一个AI程序（图灵机）是否具有某种“内在特性”P。
想象一个美食评论家大赛。评委们需要给厨师们（图灵机）打分。
📜 [原文7]
$L=\{\langle M\rangle \mid M$ 是一个图灵机且 $M$ 接受 0$\}$
是。
显然 $L \subset\left\{\langle M\rangle \mid M\right.$ 是图灵机 T 。如果 $M_{1}, M_{2}$ 是图灵机且 $L\left(M_{1}\right)=L\left(M_{2}\right)$，那么 $M_{1}$ 接受 $0 \Longleftrightarrow M_{2}$ 接受 $0$。因此，$\left\langle M_{1}\right\rangle \in L \Longleftrightarrow\left\langle M_{2}\right\rangle \in L$。
现在，取接受所有字符串的 $\langle M\rangle$，拒绝所有字符串的 $\left\langle M^{\prime}\right\rangle$。$\langle M\rangle \in L, \left\langle M^{\prime}\right\rangle \notin L$。因此，$L \neq \emptyset$ 且 $L \neq\{\langle M\rangle \mid M$ 是一个图灵机 $\}$。因此，L 是不可判定的。
这里我们将判断莱斯定理是否适用于语言 $L = \{\langle M \rangle \mid 0 \in L(M)\}$。
语言 L，即所有接受字符串'0'的图灵机的集合，满足莱斯定理的所有三个条件：它是关于图灵机的非平凡性质，并且该性质仅取决于图灵机的语言。因此，莱斯定理适用，并且 L 是不可判定的。
这是一个应用莱斯定理的经典、基础的例子。它展示了如何按部就班地验证定理的条件，并得出一个强有力的结论。这个问题实际上就是 $A_{TM}$ 的一个变种（固定了输入 w 为 '0'），所以我们本来就知道它是不可判定的，这里用莱斯定理提供了一个更快捷的证明路径。
你想判断一个AI程序是否能回答“地球是圆的吗？”这个问题。
你想给所有书籍进行一个分类：这本书是否提到了“龙”这个字。
📜 [原文8]
$L=\{\langle M\rangle \mid M$ 是一个图灵机且 $M$ 恰好有两个状态 $\}$
否。
L 不是可识别语言的一个性质。考虑任何具有两个状态的图灵机 M。我们总是可以添加无法到达的无用状态来创建具有相同语言的 $M^{\prime}$。因此，$L(M)=L\left(M^{\prime}\right)$ 并且 $\langle M\rangle \in L$ 而 $\left\langle M^{\prime}\right\rangle \notin L$。
实际上，L 是可判定的。我们可以创建一个图灵机，它简单地计算状态的数量，如果有两个则接受，否则拒绝。
这里我们判断莱斯定理是否适用于语言 L，即所有恰好有两个状态的图灵机的集合。
语言 L（恰好有两个状态的图灵机集合）是不可判定的吗？答案是否定的。莱斯定理不适用，因为“状态数量”是图灵机的实现细节，而不是其语言的性质。我们可以轻易构造出语言相同但状态数不同的图灵机。进一步分析发现，L 本身是可判定的，因为我们可以通过简单地解析图灵机编码并计算其状态数量来判定它。
这个练习是一个“反例”，旨在强调莱斯定理的适用边界。它告诉我们，并非所有关于图灵机的问题都是不可判定的。那些只涉及图灵机的“语法层面”或“静态结构”（如状态数、磁带符号数）而与其实际运行行为（它接受的语言）无关的问题，通常是可判定的。
你想判断一个AI程序的源代码是否恰好有两百行。
你想给所有书籍进行一个分类：这本书是否恰好有100页。
📜 [原文9]
$L=\{\langle M\rangle \mid M$ 是一个图灵机且 $M$ 拒绝 0$\}$
否。
L 不是可识别语言的一个性质。考虑 $M_{1}$ 是一个拒绝所有字符串的图灵机，$M_{2}$ 是一个在所有字符串上无限运行的图灵机。$L\left(M_{1}\right)=L\left(M_{2}\right)=\emptyset$。$M_{1}$ 拒绝 0，所以 $\left\langle M_{1}\right\rangle \in L$。然而，$M_{2}$ 在 0 上无限运行，并且特别不拒绝 0。因此，$\left\langle M_{2}\right\rangle \in L$。
尽管莱斯定理不适用，L 仍然是不可判定的。我们可以通过从 3.1 中的语言进行归约来证明这一点（证明省略）。
这里我们判断莱斯定理是否适用于语言 L，即所有拒绝字符串'0'的图灵机的集合。
语言 L（拒绝'0'的图灵机集合）是不可判定的，但其不可判定性不能通过莱斯定理来证明。这是因为“拒绝”是一个具体的停机行为，而不仅仅是关于语言成员的属性。两个可以产生相同语言（例如空语言）的图灵机，一个可能通过全部拒绝，另一个则通过全部无限循环来实现。这破坏了莱斯定理的“语言性质”前提。尽管如此，通过从其他已知的不可判定问题（如 $Halt_{TM}$）进行归约，可以证明 L 本身仍然是不可判定的。
这个练习是一个非常重要的例子，它深刻地揭示了莱斯定理中“语言性质”的精确含义。它强迫我们区分图灵机的不同行为（接受、拒绝、循环），并理解语言 $L(M)$ 只捕捉了“接受”这一种行为。它也提醒我们，莱斯定理只是证明不可判定性的充分条件，而非必要条件；一个不满足其前提的问题，仍然可能是不可判定的。
你想判断一个AI程序在被问到“1+1=3吗？”时，是否会明确回答“错误”。
你想给所有书籍分类：这本书是否明确地以“故事讲完了，全剧终”作为结尾。
📜 [原文10]
$E_{T M}=\{\langle M\rangle \mid M$ 是一个图灵机且 $L(M)=\emptyset\}$
是。
显然 $E_{T M} \subset\{\langle M\rangle \mid M$ 是一个图灵机 $\}$。如果 $M_{1}, M_{2}$ 是图灵机且 $L(M 1)=L(M 2)$，那么 $L\left(M_{1}\right)=\emptyset \Longleftrightarrow L\left(M_{2}\right)=\emptyset$。因此，$\left\langle M_{1}\right\rangle \in E_{T M} \Longleftrightarrow\left\langle M_{2}\right\rangle \in E_{T M}$。
现在，取接受所有字符串的 M，拒绝所有字符串的 $M^{\prime}$。我们有 $L(M)=\emptyset, L\left(M^{\prime}\right)= \Sigma^{*}$。$M \in E_{T M}, M^{\prime} \notin E_{T M}$。因此，$E_{T M} \neq \emptyset$ 且 $E_{T M} \neq\{\langle M\rangle \mid M$ 是一个图灵机 $\}$。因此，$E_{T M}$ 是不可判定的。
笔误修正：原文中 “取接受所有字符串的 M，拒绝所有字符串的 $M^{\prime}$。我们有 $L(M)=\emptyset, L\left(M^{\prime}\right)= \Sigma^{*}$。” 应为 “取拒绝所有字符串的 M，接受所有字符串的 $M^{\prime}$。我们有 $L(M)=\emptyset, L\left(M^{\prime}\right)= \Sigma^{*}$。” 且 “$M \in E_{T M}, M^{\prime} \notin E_{T M}$” 也应相应调整。
这里我们判断莱斯定理是否适用于语言 $E_{T M}$（Emptiness problem for TMs），即所有语言为空集的图灵机的集合。
语言 $E_{T M}$（图灵机的空语言问题）满足莱斯定理的所有条件：它是关于图灵机的、非平凡的、且纯粹的语言性质。因此，莱斯定理适用，$E_{T M}$ 是不可判定的。
这是应用莱斯定理的另一个核心例子。$E_{T M}$ 在计算理论中是一个非常基本的问题。这个练习展示了如何用莱斯定理快速地证明它的不可判定性，并帮助学生巩固对“语言性质”这一关键概念的理解。
你想判断一个AI程序是否“什么有意义的话都说不出来”（即它的“正确答案集”为空）。
你想给所有食谱分类：这份食谱是否“做不出任何能吃的菜”（语言为空）。
📜 [原文11]
$L=\left\{\langle M\rangle \mid M\right.$ 是一个图灵机且 $L(M)=\overline{A_{T M}}\}$
否。
此处，L 确实是可识别语言的一个性质。然而，L 是平凡的。我们知道 $\overline{A_{T M}}$ 是不可识别的，因此不存在图灵机 M 使得 $L(M)=\overline{A_{T M}}$。因此，$L=\emptyset$。请注意，由于 $\emptyset$ 是一个可判定语言，L 也是可判定的。（对于判定器，考虑图灵机：“在输入 $x$ 上，拒绝。”）
这里我们判断莱斯定理是否适用于语言 L，即所有其语言恰好是 $\overline{A_{T M}}$ 的图灵机的集合。
语言 L（所有语言为 $\overline{A_{T M}}$ 的图灵机集合）是可判定的。莱斯定理不适用，因为 L 是一个平凡的语言（它是空集），这违反了定理的“非平凡性”前提。L 之所以是空集，是因为一个基本事实：$\overline{A_{T M}}$ 本身不是一个图灵可识别的语言，因此没有任何图灵机能接受它。一个总是拒绝的图灵机就能完美地判定 L。
这个练习考察了对莱斯定理前提条件，特别是“非平凡性”的理解。它还把定理的应用与计算理论层级（可识别、非可识别）中的其他重要结论联系起来，展示了这些知识点是如何相互关联的。它是一个很好的例子，说明了为什么在应用一个定理之前，检查所有前提是至关重要的。
你想判断一个AI程序的能力是否是“全知全能的”（即能回答宇宙中所有可能的是非题）。
你想给所有食谱分类：这份食谱是否能做出“一块比它自身更重的石头”。
📜 [原文12]
$L=\{\langle M\rangle \mid M$ 是一个图灵机且 $L(M)$ 是可识别的 $\}$
否。
对于每个图灵机 M，根据定义 $L(M)$ 是可识别的。因此，$L=\{\langle M\rangle \mid M$ 是一个图灵机 $\}$，所以 L 是平凡的。
请注意，$\{\langle M\rangle \mid M$ 是一个图灵机 $\}$ 是一个可判定语言，因此 L 也是可判定的。（对于判定器，考虑图灵机：“在输入 $\langle M\rangle$ 上，其中 M 是一个图灵机，接受。”）
这里我们判断莱斯定理是否适用于语言 L，即所有其语言是图灵可识别的图灵机的集合。
语言 L（所有其语言为可识别的图灵机集合）是可判定的。莱斯定理不适用，因为它是一个平凡的性质——所有图灵机都拥有这个性质。L 实际上就是所有图灵机编码的全集，判断一个字符串是否属于这个集合是一个简单的语法检查问题，因此是可判定的。
这个练习是另一个关于“平凡性”的例子，与练习4.5（空集）相对应。4.5 是平凡的因为它不包含任何图灵机，而这个练习是平凡的因为它包含了所有图灵机。这再次强调了在应用莱斯定理前检查所有前提的重要性。
你想判断一个AI程序的能力是否是“可被AI实现的”。
你想给所有食谱分类：这份食谱是否是“一份食谱”。
📜 [原文13]
$L=\{\langle M\rangle \mid M$ 是一个图灵机且 $L(M)$ 是可判定的 $\}$
是。
显然 $L \subset\{\langle M\rangle \mid M$ 是一个图灵机 $\}$。如果 $M_{1}, M_{2}$ 是图灵机且 $L\left(M_{1}\right)=L\left(M_{2}\right)$，那么 $L\left(M_{1}\right)$ 是可判定的 $\Longleftrightarrow L\left(M_{2}\right)$ 是可判定的。因此，$\left\langle M_{1}\right\rangle \in L \Longleftrightarrow\left\langle M_{2}\right\rangle \in L$。
让 M 拒绝所有字符串，并让 U 成为 $A_{T M}$ 的识别器。我们知道 M 是一个判定器（并且 $L(\langle M\rangle)=\emptyset$ 是一个可判定语言），因此 $\langle M\rangle \in L$。然而，$L(U)=A_{T M}$ 是不可判定的，因此 $\langle U\rangle \notin L$。因此，L 是非平凡的。
这里我们判断莱斯定理是否适用于语言 L，即所有其语言是可判定的图灵机的集合。
语言 L（所有其语言为可判定的图灵机集合）是不可判定的。它满足莱斯定理的所有条件：它是关于图灵机的，它是非平凡的（因为存在可判定和不可判定的图灵可识别语言），并且它是一个纯粹的语言性质（一个语言是否可判定是其内在属性）。因此，莱斯定理适用。
这个练习是莱斯定理应用的一个更深层次的例子。它涉及到了计算理论中不同的语言类别（可判定的 vs 不可判定的可识别语言），要求学生对图灵机的能力和局限性有更清晰的认识。它也再次强化了“语言性质”这个概念，说明即使是像“可判定性”这样高阶的属性，也仍然是一种语言性质。
你想判断一个AI程序的能力是否是“有限且可被完全理解的”（可判定的）。
你想给所有游戏规则手册分类：这份规则书描述的游戏是否“必有输赢”（即游戏过程总会结束，可判定）。
本文件中所有出现的行间公式
无行间公式。
[[END_OF_RESPONSE]]所有解释内容已全部输出完毕。