5 Undecidability¶

说明

本文档仅涉及部分内容，仅可用于复习重点知识

1 The Church-Turing Thesis¶

课本原文 AI 翻译

在这本书中，我们探讨了这样一个问题：什么是可以被计算的？（更有趣的是，什么是不能被计算的？）我们已经介绍了各种各样的计算过程的数学模型，这些模型能够完成具体的计算任务——特别是判定、半判定或生成语言，以及计算函数。在上一章中，我们看到图灵机可以执行这类令人惊讶的复杂任务。我们也看到，某些可以添加到基本图灵机模型中的附加特性（包括随机访问能力），并不会增加可完成的任务集合。此外，沿着一条完全不同的路径（即尝试推广上下文无关文法），我们得到了一类语言生成器，其能力恰好与图灵机相同。最后，通过试图形式化我们关于哪些数值函数可以被视为可计算的直觉，我们定义了一类函数，结果发现它们恰好是递归函数

所有这一切表明，我们已经达到了计算设备所能设计完成任务的自然上限；我们对计算过程、算法这一终极且最一般化的数学概念的探索，已成功结束——而图灵机正是正确的答案。然而，我们在上一章也看到，并非所有的图灵机都值得被称为“算法”。我们认为，那些只能半判定语言（因此可能永远不会停止）的图灵机并不是有用的计算设备，而那些能判定语言并计算函数（因此在所有输入上都会停止）的图灵机才是。我们的“算法”概念必须排除那些在某些输入上可能不会停止的图灵机

因此，我们提议采用在所有输入上都会停止的图灵机，作为与“算法”这一直观概念相对应的精确形式化定义。如果某个过程无法被表示为一种在所有输入上都能保证停止的图灵机，那么它就不能被视为一个算法；而所有这样的图灵机都应被恰当地称为算法。这一原则被称为 Church-Turing thesis（丘奇-图灵论题）。这是一条论题，而非定理，因为它不是一个数学结果：它仅仅断言一个非正式的直觉概念（即“算法”）对应于某种特定的数学对象（即图灵机）。由于它不是数学命题，因此丘奇-图灵论题无法被证明。然而，理论上存在这样一种可能性：未来某一天，如果有人提出了一种新的计算模型，该模型被公认为合理且可信的计算模型，并且能够完成某些图灵机无法实现的计算，那么丘奇-图灵论题就可能被推翻。不过，没有人认为这种情形是可能发生的

采用一个精确的算法数学定义，开启了这样一个引人入胜的可能性：可以形式化地证明某些计算问题根本无法通过任何算法解决。我们已经知道这一点是可以预期的。在第一章中，我们曾论证过：如果用字符串来表示语言，那么并非所有语言都可以被表示出来——因为在一个字母表上的字符串只有可数无穷多个，而语言的数量却是不可数无穷多。有限自动机、下推自动机、上下文无关文法、无限制文法以及图灵机都是可用于指定语言的有限对象的例子，而且这些对象本身也可以用字符串来描述（在下一节中，我们将详细阐述如何用字符串表示图灵机）。因此，对于任意一个字母表，只存在可数无穷多个递归语言和递归可枚举语言。所以尽管我们已竭尽全力扩展计算机器的能力，但从绝对意义上讲，它们只能用于半判定或判定所有可能语言中微乎其微的一小部分

使用基数论（cardinality）的论证来说明我们方法的局限性是平凡的；而找到在某个模型中无法完成的具体计算任务的例子则更加有趣且富有意义。在前面的章节中，我们成功地找到了某些不是正则语言或上下文无关语言的语言；在本章中，我们将对递归语言做同样的工作。然而，这里有两点主要的不同之处。首先，这些新的负面结果不仅仅是暂时的挫折，它们将在后续章节中被克服，届时将定义一种更强大的计算设备：根据丘奇-图灵论题，不能由图灵机执行的计算任务是不可行的、无望的、不可判定的。其次，我们用来证明某种语言不是递归语言的方法必须不同于之前用于揭示上下文无关文法和有限自动机弱点的“抽屉”定理（pumping theorems）。相反，我们需要设计出一些技术，以利用图灵机本身所具有的强大能力，从而揭示其自身的局限性。我们将要探讨的图灵机能力的一个方面，是一种“内省能力”（introspective ability）：我们指出，图灵机可以接收图灵机的编码作为输入，并以有趣的方式操纵这些编码。接下来我们将探讨当一台图灵机操作它自身编码时会发生什么——这是对对角化原理（diagonalization principle）的一种巧妙而又简单的应用。如何对一台图灵机进行编码，以便它能被另一台（或者同一台！）图灵机所操纵，这正是我们接下来要讨论的主题

Church-Turing Thesis（丘奇-图灵论题）是计算理论中的一个核心假设，它试图形式化“什么是可以被有效计算的”这一直观概念。虽然它被称为“论题”（thesis）而非“定理”（theorem），因为它无法被严格数学证明（其基础涉及非形式化的直觉概念），但它在计算机科学和数学逻辑中具有基石地位

丘奇-图灵论题的核心思想可以简洁地表述为：任何在算法上可计算的函数，都可以由图灵机计算。换句话说：如果某个问题能通过“机械步骤”（即算法）在有限时间内解决，那么就存在一台图灵机可以在输入该问题时输出正确答案

2 Universal Turing Machines¶

课本原文 AI 翻译

计算的基础是硬件还是软件？你可能对这个问题有自己的看法——以及关于这个问题是否有意义、是否具有建设性。但事实是，我们在上一章中引入并发展的算法形式化模型——图灵机——是一种“不可编程”的硬件，专门用于解决某个特定问题，其指令在出厂时就已经“硬编码”（hard-wired）

现在我们将从相反的角度来看待这个问题。我们将论证：图灵机也是软件。也就是说，我们将证明存在一种“通用”的图灵机，它能够像通用计算机一样被编程，从而解决任何图灵机可以解决的问题。使这种通用机器表现出特定机器 $M$ 行为的“程序”，必须是 $M$ 的一种描述。换句话说，我们将把图灵机的形式化视为一种编程语言，我们可以在其中编写程序。用这种语言编写的程序随后可以由一台通用图灵机（universal Turing machine）来解释——也就是说，用同一种语言编写的另一个程序。一个用某种语言编写的程序能够解释该语言中的任意其他程序，并不是什么新颖的想法——这正是经典“引导式”（bootstrapping）语言处理器方法的基础。但为了继续本书中的研究，我们有必要在图灵机的背景下精确地阐明这一点

首先，我们需要提出一种通用的方式来描述图灵机，使得这些描述可以作为其他图灵机的输入。也就是说，必须定义一种语言，其字符串都是图灵机的合法表示形式。这个问题已经显现出来：无论我们为这种表示选择多么大的字母表，总会有图灵机的状态数和磁带符号数更多。因此，我们需要将状态和磁带符号编码为固定字母表上的字符串。我们采用如下约定：表示图灵机状态的字符串形式为 $\lbrace q\rbrace \lbrace 0,1\rbrace ^∗$，即字母 $q$ 后跟一个二进制字符串。类似地，磁带符号总是表示为形如 $\lbrace a\rbrace \lbrace 0,1\rbrace^∗$ 的字符串

设 $M=(K,Σ,δ,s,H)$ 是一台图灵机，令 $i$ 和 $j$ 为最小整数，满足 $2^i \geqslant |K|$ 且 $2^j \geqslant |\Sigma| + 2$。那么 $K$ 中的每个状态都将表示为字母 $q$ 后跟一个长度为 $i$ 的二进制字符串；$Σ$ 中的每个符号也将以字母 $a$ 后跟一个 $j$ 位二进制字符串的形式表示。头的移动方向 $←$ 和 $→$ 也将被视为“荣誉磁带符号”（它们正是定义 $j$ 时“+2”项的原因）。我们规定特殊符号 $⊔$、$\rhd$、$←$ 和 $→$ 分别用字典序最小的四个符号来表示：

$⊔$ 总是表示为 $a0^j$
$\rhd$ 表示为 $a0^{j-1}1$
$←$ 表示为 $a0^{j-2}10$
$→$ 表示为 $a0^{j-2}11$
起始状态 $s$ 总是表示为字典序中第一个状态 $q0^i$

注意，我们要求在符号 $a$ 和 $q$ 后的字符串前补零，以使总长度达到所需值

我们将整个图灵机 $M$ 的表示记作 “$M$”。这个“$M$”由转移表 $δ$ 构成。也就是说，它是一系列形如 $(q,a,p,b)$ 的字符串序列，其中 $q$ 和 $p$ 是状态的表示，$a$ 和 $b$ 是符号的表示，各部分之间用逗号分隔，并包含在括号中。我们采用惯例：四元组按字典序递增排列，从 $δ(s,⊔)$ 开始。停止状态集合 $H$ 将通过间接方式确定：如果某个状态未出现在任何四元组的第一个分量中，则该状态属于停机状态。如果 $M$ 判定某种语言，因此 $H={y,n}$，我们将采用惯例：$y$ 是两个停机状态中字典序较小的那个

通过这种方式，任何图灵机都可以被表示出来。我们将使用相同的方法来表示图灵机字母表中的字符串。任意字符串 $w∈Σ^∗$ 都将有一个唯一的表示，也记作 “$w$”，即其各个符号表示的拼接

现在我们已经准备好讨论一台通用图灵机 $U$，它使用其他机器的编码作为程序来指导其运行。直观上，$U$ 接受两个参数：一台机器 $M$ 的描述 “$M$”，以及一个输入字符串 $w$ 的描述 “$w$”。我们希望 $U$ 具有如下性质：当且仅当 $M$ 在输入 $w$ 上停机时，$U$ 在输入 “$M$”“$w$” 上才会停机。为了使用我们在上一章中为图灵机建立的功能性表示法，可以写成：$U(“M”“w”) = “M(w)”$

我们实际上描述的并不是单磁带机器 $U$，而是一个与之密切相关的三磁带机器 $U'$（之后，$U$ 将是模拟 $U'$ 的单磁带图灵机）。具体来说，$U'$ 使用其三条磁带如下：第一条磁带包含当前被模拟的机器 $M$ 的磁带内容的编码；第二条磁带包含 $M$ 本身的编码；第三条磁带包含在模拟计算的当前步骤中 $M$ 的状态的编码。

机器 $U'$ 以某个字符串 “$M$”“$w$” 作为其第一条磁带的输入，其余两条磁带为空。（如果输入字符串不是这种形式，$U'$ 的行为无关紧要。）首先，$U'$ 将 “$M$” 移动到第二条磁带上，并将 “$w$” 向左移动到第一条磁带的左端，前面加上符号 “$\rhd⊔$”。因此，在此时刻，第一条磁带的内容为 “$\rhd ⊔w$”。接着，$U'$ 在第三条磁带上写下 $M$ 的初始状态 $s$ 的编码，即始终为 $q0^i$（$U'$ 可以通过检查 “$M$” 轻松确定 $i$ 和 $j$）。现在，$U'$ 开始模拟 $M$ 的计算步骤。在每次模拟步骤之间，$U'$ 会将第二条和第三条磁带的读写头保持在最左端，而第一条磁带的读写头则扫描当前对应时刻 $M$ 所扫描符号的编码中的 $a$ 部分。

$U'$ 模拟 $M$ 的一个步骤如下：它扫描第二条磁带，直到找到一个四元组，其第一个分量与第三条磁带上的编码状态匹配，且第二个分量与第一条磁带上扫描到的编码符号匹配。如果找到了这样的四元组，它就将状态更新为该四元组的第三个分量，并在第一条磁带上执行由第四个分量建议的操作。如果第四个分量编码的是 $M$ 的磁带字母表中的一个符号，则将该符号写入第一条磁带。如果第四个分量是 $a0^{j-2}10$（即 $←$ 的编码），则 $U'$ 将其第一条磁带的读写头向左移动到下一个 $a$ 符号；如果是 $a0^{j-2}11$（$→$ 的编码），则向右移动。如果遇到 $⊔$ 的编码，$U'$ 必须将其转换为 $a0^j$，即 $M$ 中空白符号的编码

如果在某一步中，状态-符号组合在第二条磁带上未找到，这意味着该状态是一个停机状态。此时 $U'$ 也会进入相应的停机状态。至此，我们完成了对 $U'$ 运作方式的描述

3 The Halting Problem¶

课本原文 AI 翻译

假设你用自己最喜欢的编程语言编写了一个程序，它能完成一项非凡的壮举：该程序接收任意一个用相同语言编写的程序 $P$，以及该程序的一个输入 $X$。通过某种巧妙的分析，你的程序总能正确判断程序 $P$ 在输入 $X$ 上是否会停止（如果会，则返回“yes”），还是将永远运行下去（如果不会，则返回“no”）。你把这个程序命名为 halts(P, X)

这是一个极其宝贵的程序。它可以发现各种微妙的错误，这些错误会导致其他程序在某些输入上无限运行。使用这个程序，你可以实现许多惊人的功能。这里是一个略显微妙的例子：你可以用它来编写另一个程序，名字叫 diagonal(X)

// diagonal(X)
a: if halts(X, X) then goto a else halt

注意 diagonal(X) 的作用：如果 halts 程序判断程序 X 在以自身作为输入时会停止，那么 diagonal(X) 就会无限循环；否则，它就会停止

现在出现了一个无法回答的问题：diagonal(diagonal) 是否会停止？

它停止当且仅当调用 halts(diagonal, diagonal) 返回“no”；换句话说，它停止当且仅当它不会停止。这是一矛盾：我们只能得出结论——最初假设的那个程序 halts(P, X) 是不存在的。也就是说，不可能存在任何程序、任何算法，能够解决“任意程序是否会在给定输入上停止”这一问题

这种论证方式不仅来自你过去对计算机科学的学习，也来自二十世纪普遍文化中的经典悖论。关键在于，我们现在已经引入了所有必要的工具，来形式化、数学严谨地表达这个悖论。我们拥有了一种完整的算法形式化表示方法，一种“编程语言”式的工具：图灵机。事实上，在上一节中，我们引入了最后一个所需特性：我们已经构建了一个框架，使得我们的“程序”可以操作其他程序及其输入——这正是我们虚构的程序 halts(P, X) 所做的。因此，我们现在准备定义一个不可递归的语言，并证明它确实不可递归。令：$H=\lbrace“M”“w”:图灵机 M 在输入字符串 w 上停止\rbrace$

首先注意到，$H$ 是递归可枚举的：它恰好是我们在上一节中介绍的通用图灵机 $U$ 所半判定的语言。事实上，当输入为 “$M$”“$w$” 时，$U$ 正好在输入属于 $H$ 时停止

此外，如果 $H$ 是递归的，那么每一个递归可枚举语言都是递归的。换句话说，$H$ 是我们第 4.2 节所提出问题的关键：即所有递归可枚举语言是否也都是图灵可判定的——这个问题的答案是肯定的，当且仅当 $H$ 是递归的

Theorem 5.3.1

语言 $H=\lbrace“M”“w”:图灵机 M 在输入字符串 w 上停止\rbrace$ 不是递归的；因此，递归语言类是递归可枚举语言类的一个真子集

Proof

假设 $H$ 确实由某个图灵机 $M_0$ 判定。那么对于任意一个特定的图灵机 $M$，它半判定某个语言 $L(M)$，我们可以设计一台图灵机 $M'$ 来判定 $L(M)$，方法如下：首先，$M'$ 将其输入磁带从形式 $▹⊔w\underline{⊔}$ 转换为 $▹“M”“w”\underline{⊔}$，然后在该输入上模拟 $M_0$。根据假设，$M_0$ 将正确判断 $M$ 是否接受 $w$。我们可以这样说：所有递归可枚举语言都可以规约（reduce）到 $H$，因此 $H$ 是递归可枚举语言类中的完备语言（complete language）

但我们可以通过形式化上面关于 halts(P, X) 的论证来证明：$H$ 不是递归的。首先，如果 $H$ 是递归的，那么 $H_1=\lbrace“M”:图灵机 M 在输入字符串 “M” 上停止\rbrace$ 也将是递归的（$H_1$ 对应于对角程序中 halts(X, X) 的部分）。如果存在一台图灵机 $M_0$ 能够判定 $H$，那么一台判定 $H_1$ 的图灵机 $M_1$ 只需要将其输入字符串 $▹⊔“M”\underline{⊔}$ 转换为 $▹⊔“M”“M”\underline{⊔}$，然后将控制权交给 $M_0$ 即可。因此，只需证明 $H_1$ 不是递归的就足够了

其次，如果 $H_1$ 是递归的，那么它的补集也必然是递归的：$\bar{H_1}=\lbrace w:要么 w 不是图灵机的编码，要么它是某台图灵机 M 的编码 “M”，且 M 在输入 “M” 上不终止\rbrace$

这是因为递归语言类在取补运算下是封闭的。顺便提一下，$\bar{H_1}$ 就是我们所谓的“对角语言”，它对应于我们之前构造的对角程序，也是整个证明的最后一步

但 $H_1$ 不可能是递归可枚举的——更不用说递归了。假设存在一台图灵机 $M^*$ 半判定 $\bar{H_1}$。那么，$“M^*”$ 是否属于 $\bar{H_1}$？根据 $\bar{H_1}$ 的定义，$“M^*”$ 属于 $\bar{H_1}$ 当且仅当 $M^*$ 不接受输入字符串 $“M^*”$。但 $M^*$ 被假设为半判定 $\bar{H_1}$，因此 $“M^*”$ 属于 $\bar{H_1}$ 当且仅当 $M^*$ 接受 $“M^*”$。于是我们得出：$M^*$ 接受 $“M^*”$ 当且仅当它不接受 $“M^*”$。这是矛盾的，因此假设 $M_0$ 存在必须是错误的

让我们总结本节的发展过程。我们试图探究：是否每一个递归可枚举语言都是递归的。我们观察到，这成立当且仅当那个特定的递归可枚举语言 $H$ 是递归的。从 $H$ 出发，我们通过两步推导出语言 $\bar{H_1}$，而为了使 $H$ 是递归的，$\bar{H_1}$ 必须是递归的。然而，假设 $\bar{H_1}$ 是递归的会导致逻辑矛盾，这是通过对角化方法得到的

课本原文 AI 翻译

我们之前提到过，这个论证是第 1.5 节中用于证明 $2^N$ 不可数的对角化原理的一个实例。为了说明这一点，并再次强调证明的核心思想，我们定义一个在图灵机编码所用字母表上的字符串之间的二元关系 $R$：当且仅当 $u=“M”$，且存在一台图灵机 $M$ 接受 $w$ 时，有 $(u,w)∈R$（$R$ 是 $H$ 的一种形式化版本）

现在，对于每个字符串 $u$，定义：$R_u = \lbrace w:(u,w)\in R \rbrace$（这些 $R_u$ 对应于递归可枚举语言）

并考虑 $R$ 的对角线，即：$D = \lbrace w:(w,w) \notin R \rbrace$（$D$ 就是 $\bar{H_1}$）

根据对角化原理，对所有 $u$ 都有 $D \not ={R_u}$；也就是说，$\bar{H_1}$ 是一个与任何递归可枚举语言都不同的语言

为什么对任意 $u$ 都有 $D \not ={R_u}$？因为根据其构造，$D$ 与每一个 $R_u$（从而与每一个递归可枚举语言）在至少一个字符串上不同——即字符串 $u$ 本身

定理 5.3.1 否定了我们在第 4.2 节末尾提出的两个问题中的第一个：“每一个递归可枚举语言是否也是递归的？”以及“递归可枚举语言类在取补运算下是否封闭？”

但同样的证明也回答了第二个问题。显然，$H_1$ 像 $H$ 一样是递归可枚举的，而我们已经证明 $\bar{H_1}$ 不是递归可枚举的。因此，我们也证明了以下结论：

Theorem 5.3.2

递归可枚举语言类在取补运算下不封闭

4 Undecidable Problems About Turing Machine¶

课本原文 AI 翻译

我们已经证明了一个意义重大的结果。让我们稍作退后，从直观层面来理解这一结论，并结合丘奇-图灵论题（Church-Turing thesis）来看其含义。由于该证明表明语言 $H$ 不是递归的，而我们接受了“任何算法都可以转化为一台在所有输入上都能停机的图灵机”这一原则，因此我们可以得出结论：不存在一个算法，能够对任意给定的图灵机 $M$ 和输入字符串 $w$，判断 $M$ 是否接受 $w$

对于那些不存在算法来解决的问题，我们称之为 undecidable（不可判定的）或 unsolvable（不可解的）；本章中我们将看到许多这样的问题。其中最著名、最基本的一个不可判定问题是：判断一台给定的图灵机在某个给定输入上是否会停机——我们刚刚证明了这个问题的不可判定性。这个问题通常被称为 the halting problem for Turing machines（图灵机的停机问题）

需要注意的是，停机问题的不可判定性并不意味着在某些特定情况下无法预测图灵机是否会停机。例如，在例 4.1.2 中，我们能够推断出某台简单的机器在某个特定输入上必定不会停机。或者，我们可以检查图灵机的转移表，看看是否存在停机状态；如果不存在，则该机器在任何输入上都不会停机。这类更复杂的分析可能在某些特定情况下提供有用的信息；但我们的定理表明，任何此类分析最终要么无法完成，要么产生错误的结果：不存在一种完全通用的方法，能够正确地判断所有情况

一旦我们通过对角化方法确立了停机问题是不可判定的，那么大量其他问题的不可判定性便随之而来。这些结果并非通过进一步的对角化证明，而是通过归约（reductions）来证明的：我们在每种情况下都证明，如果某个语言 $L_2$ 是递归的，那么另一个已知为非递归的语言 $L_1$ 也必须是递归的——这会导致矛盾，从而说明 $L_2$ 也不可能是递归的

设 $L_1,L_2\subseteq \Sigma^*$ 是两个语言。从 $L_1$ 到 $L_2$ 的一个 reduction 是一个递归函数 $\tau:\Sigma^* \rightarrow \Sigma^*$，满足：当且仅当 $\tau(x) \in L_2$ 时，有 $x \in L_1$

读者必须注意理解“归约方向”的含义。为了证明某个语言 $L_2$ 不是递归的，我们需要找到一个已知为非递归的语言 $L_1$，然后将 $L_1$ 归约到 $L_2$。如果反过来将 $L_2$ 归约到 $L_1$，那就毫无意义：它只能说明如果我们能判定 $L_1$，那么就能判定 $L_2$ ——但我们已经知道无法判定 $L_1$，因此这种归约无助于证明 $L_2$ 的不可判定性

Theorem 5.4.1

如果语言 $L_1$ 不是递归的，并且存在从 $L_1$ 到 $L_2$ 的规约，那么 $L_2$ 也不是递归的

Proof

假设 $L_2$ 是递归的，即由某个图灵机 $M_2$ 判定，并设 $T$ 为计算归约 $τ$ 的图灵机。那么图灵机 $TM_2$（即 $T$ 后面接 $M_2$ 的组合）将会判定 $L_1$。但 $L_1$ 是不可判定的。矛盾

Theorem 5.4.2

以下关于图灵机的问题都是不可判定的：

给定一个图灵机 $M$ 和一个输入字符串 $w$，$M$ 在输入 $w$ 上是否会停机？
给定一个图灵机 $M$，$M$ 在空带上是否会停机？
给定一个图灵机 $M$，是否存在某个字符串使得 $M$ 在其上会停机？
给定一个图灵机 $M$，$M$ 是否在所有输入字符串上都会停机？
给定两个图灵机 $M_1$ 和 $M_2$，它们是否在相同的输入字符串上停机？
给定一个图灵机 $M$，它半判定的语言是否是正则语言？是否是上下文无关语言？是否是递归语言？
此外，对于某个特定的固定图灵机 $M$，以下问题也是不可判定的：给定一个字符串 $w$，$M$ 是否在 $w$ 上停机？

Proof 2

我们描述一个从 $H$ 到语言 $L=\lbrace“M”:M 在 ϵ 上停机\rbrace$ 的归约

给定一台图灵机 $M$ 的描述和一个输入 $x$，我们的归约简单地构造出一台图灵机 $M_w$ 的描述，其操作方式如下：当 $M_w$ 从空白磁带（即配置 $(s, \rhd\sqcup)$）开始运行时，它会在磁带上写下 $w$，然后开始模拟 $M$。换句话说，如果 $w = a_1 \cdots a_n$，那么 $M_w$ 就是简单的机器 $Ra_1Ra_2R \cdots Ra_nL_\sqcup M$

很容易看出，将$“M”“w”$映射到$“M_w”$的函数 $\tau$ 确实是递归的

Proof 3

我们可以将 2 部分中所示的语言 $L$ 归约到语言 $L'=\lbrace“M”:M 在某个输入上停机\rbrace$

给定任意图灵机 $M$ 的表示，我们的归约构造出一个图灵机 $M'$ 的表示，该机器会先擦除其接收到的任何输入，然后在空字符串上模拟 $M$。显然，$M'$ 在某个字符串上停机当且仅当它在所有字符串上停机，当且仅当 $M$ 在空字符串上停机

Proof 4

3 部分中的论证在这里同样适用，因为 $M'$ 是这样构造的：它接受某个输入当且仅当它接受所有输入

Proof 5

我们将 4 部分中的问题归约到本问题。给定一台机器 $M$ 的描述，我们的归约构造出字符串 $τ(“M”)=“M”“y”$，其中 $“y”$ 立即接受任何输入的机器的描述。显然，两台机器 $M$ 和 $y$ 接受相同的输入当且仅当 $M$ 接受所有输入

Proof 6

我们将 5 部分中的问题简化为当前问题。我们展示了如何修改任意图灵机 $M$，以得到一个图灵机 $M'$，使得 $M'$ 要么在集合 $H$ 中的字符串上停机，要么在没有任何字符串上停机，具体取决于 $M$ 是否在空串上停机。由于没有算法可以判断 $M$ 是否在空串上停机，因此也就没有算法能够判断 $L(M)$ 是否为空（即是否是正则、上下文无关或递归语言），或者是否等于 $H$（而 $H$ 既不是正则、也不是上下文无关，更不是递归的）。首先，$M'$ 保存其输入字符串，并开始执行 $M$ 在输入 $\epsilon$ 上的操作。如果 $M$ 停机，则 $M'$ 恢复其输入，并在该输入上执行通用图灵机 $U$ 的操作。因此，$M'$ 要么在任何输入上都不停机（因为它从未完成对 $M$ 在输入 $\epsilon$ 上的模拟），要么恰好在 $H$ 中的字符串上停机

Proof 7

定理陈述中提到的固定机器 $M_0$ 正是通用图灵机 $U$

7 Properties of Recursive Languages¶

Theorem 5.7.1

一个语言是递归的，当且仅当它本身及其补集都是递归可枚举的

Proof

如果 $L$ 是递归的，那么根据定理 4.2.1，$L$ 是递归可枚举的；同时，$\overline{L}$ 也是递归的，因此根据定理 4.2.2，$\overline{L}$ 也是递归可枚举的

对于另一个方向，假设 $L$ 被图灵机 $M_1$ 半判定，而 $\overline{L}$ 被图灵机 $M_2$ 半判定。那么我们可以构造一台图灵机 $M$ 来判定 $L$。为方便起见，我们将 $M$ 描述为一台双带图灵机；根据定理 4.3.1，$M$ 可以被模拟成单带图灵机。机器 $M$ 首先将输入字符串 $w$ 同时复制到两条带上，并将两个读写头都置于输入副本的右端。然后，$M$ 并行地模拟 $M_1$ 和 $M_2$：在 $M$ 的每一步操作中，$M_1$ 的一步计算在第一条带上执行，$M_2$ 的一步计算在第二条带上执行。由于 $M_1$ 和 $M_2$ 中必有一个在 $w$ 上停机，但不会两者都停机，因此 $M$ 最终会进入一种状态，即模拟的 $M_1$ 或 $M_2$ 即将停机。当这种情况发生时，$M$ 判断出是哪一个（$M_1$ 还是 $M_2$）即将停机，并相应地在 $y$ 或 $n$ 上停机

Definition 5.7.1

我们说图灵机 $M$ enumerates（枚举）语言 $L$，当且仅当存在 $M$ 的某个固定状态 $q$，使得 $L = \lbrace w:(s,\rhd\underline{\sqcup})\vdash^*_M(q,\rhd\underline{\sqcup}w)\rbrace$

一个语言是 Turing-enumerable，当且仅当存在一台图灵机能够枚举它

课本原文 AI 翻译

也就是说，$M$ 从空白带开始运行，在计算过程中周期性地经过某个特殊状态 $q$（不是停机状态）。进入状态 $q$ 表示当前磁带上字符串属于语言 $L$；随后 $M$ 可以离开状态 $q$，并在之后再次进入该状态，此时磁带上可能是 $L$ 中的另一个成员。注意，$L$ 中的元素可以按任意顺序列出，并且允许重复

Theorem 5.7.2

一个语言是递归可枚举的，当且仅当它是图灵可枚举的

Proof

假设语言 $L$ 被图灵机 $M$ 半判定。那么我们可以设计一台机器 $M'$，它不以字符串作为输入，而是从空带开始，系统地生成（例如按字典序）该语言字母表上的所有字符串，并对每个字符串执行 $M$ 会进行的相同计算。不幸的是，实现这一目标的明显方法可能行不通：我们的新机器 $M'$ 不可能在开始处理下一个字符串之前完成对当前字符串的计算，因为它可能会在某个 $M$ 无法终止的字符串上“卡住”无限长时间，尽管还有其他 $M$ 会接受但尚未生成的字符串（如果 $L$ 是由 $M$ 决定的，那么这种策略当然有效；参见下一定理的证明）

解决方案基于我们在第 1.4 节中使用的一种“对角化”（dovetailing）过程，用来证明可数多个集合的并集是可数的。与试图在生成每个字符串时立即完成其计算不同，$M'$ 执行如下操作序列：

首先，$M'$ 对字母表上字典序第一个字符串执行 $M$ 的一步计算
然后，它对前两个字符串各执行 $M$ 的两步计算
接着，它对前三个字符串各执行 $M$ 的三步计算，依此类推

当 $M'$ 第一次发现 $M$ 会接受某个字符串（比如 $w_1$）时，$M'$ 将 $w_1$ 写入其磁带上，并在状态 $q$ 暂停，以表示 $w_1 \in L$

一般地，在第 $i$ 个属于 $L$ 的字符串被发现后（记为 $w_i$），$M'$ 首先在状态 $q$ 显示它，并从步骤 1 重新开始，同时保持 $w_i$ 在磁带上。每当它现在发现一个被 $M$ 接受的新字符串时，它首先将其与 $w_i$ 进行比较；如果它们不相等，则继续。如果发现刚刚发现的字符串与 $w_i$ 相同，则它寻找 $M$ 接受的下一个字符串。这个下一个字符串将是 $w_{i+1}$。再次，$w_{i+1}$ 在状态 $q$ 被显示、记住并比较。显然，$L$ 中的任何成员最终都会被显示出来

另一个方向要简单一些。如果 $M$ 枚举了语言 $L$，那么我们可以修改 $M$ 来半判定 $L$：重新设计 $M$，使其在开始枚举过程之前保存所提供的任意输入。此外，每当 $M$ 将进入特殊状态 $q$ 时，修改后的机器会将当前磁带内容与保存的输入字符串进行比较。如果匹配成功，则接受输入字符串；否则，枚举过程继续。这样，新机器恰好半判定由 $M$ 枚举的语言

Definition 5.7.2

设 $M$ 是一台枚举语言 $L$ 的图灵机。我们说 $M$ lexicographically enumerates（按字典序枚举）$L$，当且仅当以下条件成立，其中 $q$ 是特殊的显示状态：每当 $(q,\rhd\underline{\sqcup}w) \vdash^+_M(q,\rhd\underline{\sqcup}w')$，则 $w'$ 在字典序上大于 $w$。一个语言是 lexicographically Turing-enumerable（字典序图灵可枚举的），当且仅当存在一台图灵机能够按字典序枚举它

Theorem 5.7.3

一个语言是递归的，当且仅当它是字典序图灵可枚举的

Proof

假设 $M$ 是一台判定语言 $L$ 的图灵机。那么以下图灵机 $M'$（这是我们在证明定理 5.7.2 同一方向时第一次尝试构造的机器）会以字典序枚举 $L$：$M'$ 按照 $L$ 的字母表中所有字符串的字典序依次生成每个字符串，并对每个字符串运行 $M$。每当 $M$ 接受该字符串时，$M'$ 就显示该字符串并继续处理下一个字符串；如果 $M$ 拒绝，则 $M'$ 直接跳到下一个字符串，不进入显示状态

对于另一个方向，假设 $L$ 被一台图灵机 $M$ 按字典序枚举。这里有两种情况：如果 $L$ 是有限的，那么无需证明，因为在这种情况下 $L$ 必然是递归的（同时也是上下文无关、正则等）。因此，假设 $L$ 是无限的。下面的机器 $M'$ 可以判定 $L$：在输入 $w$ 上，启动枚举机 $ M $，等待直到要么 $w$ 被显示，要么某个字典序上位于 $w$ 之后的字符串被显示。在第一种情况下，接受 $w$；在第二种情况下，拒绝。由于在 $w$ 之前按字典序排列的字符串数量是有限的（少于 $|\Sigma + 1|^{|w|}$），而 $L$ 是无限的，我们知道这两个事件中必有一个会发生

Theorem 5.7.4 (Rice's Theorem)

假设 $\mathcal{C}$ 是所有递归可枚举语言类的一个真子集，且非空。那么以下问题是不可判定的：给定一台图灵机 $M$，其识别的语言 $L(M)$ 是否属于 $\mathcal{C}$？

Proof

我们可以假设 $\emptyset \notin \mathcal{C}$（否则，对不在 $\mathcal{C}$ 中的所有递归可枚举语言类重复其余论证，这同样是一个递归可枚举语言类的真非空子集）。接下来，由于 $\mathcal{C}$ 非空，我们可以假设存在一个语言 $L \in \mathcal{C}$，由机器 $M_L$ 半判定

我们将停机问题规约为判断某个给定图灵机所半判定的语言是否属于 $\mathcal{C}$ 的问题。假设我们给定一台图灵机 $M$ 和输入 $w$，我们希望判断 $M$ 是否在 $w$ 上停机。为了实现这一点，我们构造一台图灵机 $T_{M,w}$，使得它所半判定的语言要么是上面固定的语言 $L$，要么是空语言 $\emptyset$。对于输入 $x$，$T_{M,w}$ 模拟通用图灵机 $U$ 在输入 “$M$”“$w$” 上的运行。如果 $U$ 停机，则 $T_{M,w}$ 不直接停机，而是继续模拟 $M_L$ 在输入 $x$ 上的运行：它可能停机并接受，也可能永不终止，具体取决于 $M_L$ 在 $x$ 上的行为。自然地，如果 $U(\text{“}M\text{”}\text{“}w\text{”}) = \nearrow$，则 $T_{M,w}(x) = \nearrow$。回顾一下，$T_{M,w}$ 的定义如下：$T_{M,w}(x): \text{ if } U(\text{“}M\text{”}\text{“}w\text{”}) \neq \nearrow \text{ then } M_L(x) \text{ else } \nearrow$

断言：$T_{M,w}$ 所半判定的语言属于类 $\mathcal{C}$ 当且仅当 $M$ 在输入 $w$ 上停机

注意，该断言说明从 $M$ 和 $w$ 构造 $T_{M,w}$ 的过程，实际上是将停机问题规约为这样一个问题：给定一台图灵机，判断它所半判定的语言是否在 $\mathcal{C}$ 中。这将完成定理的证明

断言的证明：假设 $M$ 在输入 $w$ 上停机。那么 $T_{M,w}$ 在输入 $x$ 上会确定这一点，并且总是接着接受 $x$ 当且仅当 $x \in L$。因此，在这种情况下，$T_{M,w}$ 所半判定的语言是 $L$——而 $L \in \mathcal{C}$

假设 $M(w) = \nearrow$。在这种情况下，$T_{M,w}$ 永远不会停机，因此 $M_x$ 半判定的是空语言 $\emptyset$，而空语言已知不在 $\mathcal{C}$ 中

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问