停机问题

图书管理员悖论

为了完整地介绍形式语言，我们需要构造一个递归可枚举（RE）但不是递归的语言。我们将构造一种能被图灵机识别，但不可判定的语言（即：对于不属于该语言的字符串，图灵机可能不会停机）。这样的语言就是递归可枚举的，但不是递归的。通过这个语言，我们可以进一步发现其他非递归语言，并通过取补集的方式，得到那些既不是递归也不是递归可枚举的语言。但在那之前，我们先来看一些与自指相关的有趣现象。

从前有一位图书馆实习生，任务是列出图书馆中所有不提及自身的书籍。他发现这份清单变得越来越长，于是决定把这份清单本身也做成一本书，放在图书馆中作为参考。

完成这项冗长而繁琐的工作后，实习生自豪地将这本“不自指书籍名录”摆上了参考书架。过了一阵子，他和其他人突然意识到：这本书本身也是图书馆中的一本书，因此也需要被分类——它是否应该被列入自己的目录之中？起初似乎应该列入，因为它并未在内容中提到自己；但一旦被列进去，它就变成了“提及自身”的书，因此必须从目录中移除；而一旦被移除，它又不再提及自己，于是又该被加回去……

这个故事被称为图书管理员悖论。当自指与否定性命题结合时，就会产生这种逻辑上的矛盾。

停机问题

计算领域中最经典的不可判定问题是停机问题，它最初由艾伦·图灵提出。假设存在一个算法，也就是一台图灵机 $H$，它接受另一个图灵机 $M$ 的编码以及任意输入字符串 $w$ 作为输入，并且总是能够停机：如果 $M$ 在输入 $w$ 上会停机，则接受；否则拒绝。关键在于，这个判断不能通过实际运行 $M(w)$ 来完成，因为那样可能导致无限循环，从而使 $H$ 无法成为一个真正的算法。如果这样的 $H$ 存在，那它将非常有用——我们可以调用 $H(M,w)$ 来预先判断是否值得执行 $M(w)$，从而实现一种能够检测程序中无限循环的预判式调试技术。

直观上，我们怀疑停机问题是不可解的，因为并非所有图灵机都能在每个输入上停机。毕竟，什么样的“预言机”才能预知任意图灵机在任意输入下的行为呢？不过，像往常一样，我们需要一个严格的证明。我们将采用反证法：先假设这样的 $H$ 存在，然后从中推出矛盾，从而证明其不可能存在。

假设 $H$ 确实存在，那么我们可以将其作为子程序来构建其他图灵机。为简化问题，我们定义一个新的图灵机 $H'$，它只接收一个输入，即任意图灵机 $M$ 的编码，并将该编码同时作为两个参数传给 $H$。换句话说，$H'(M)$ 实际上调用了 $H(M,M)$。后续推理中具体输入并不重要，因此这种简化不会影响结论。下图分别展示了 $H$ 和 $H'$ 的结构：

![图灵机 H]

![图灵机 H']

接着，我们构造一台新的机器 $D$，它与 $H'$ 的区别在于：当 $H'$ 输出“Y”（接受）时，$D$ 会进入无限循环；其余情况保持一致。如下图所示：

![图灵机 D]

用 Python 表示，$D$ 的实现如下：

1def D(M):
2    if H(M,M):
3        while True:     # 无限循环
4            pass
5    else:
6        return 'N'

现在我们提出关键问题（这里出现自指了）：$D(D)$ 的结果是什么？

• 如果 $D$ 在其自身编码上会停机，那么根据定义，它将进入无限循环，即不会停机！
• 反之，如果 $D$ 不会停机，那么 $H(D,D)$ 返回假，$D$ 就会返回 'N'，即会停机！

无论哪种情况都导致矛盾。因此，我们的初始假设——$H$ 存在——必定是错误的。

注意：停机问题是不可判定的。

构造一个非递归的递归可枚举语言

我们现在可以定义一个递归可枚举但不是递归的语言。首先定义一个图灵机（或程序）$R$，它接收两个任意字符串 $M$ 和 $w$ 作为输入。如果 $M$ 是某个图灵机的有效编码（即符合正则表达式 $1^+(01^+)^4((001^+(01)+)^4)^*$），则 $R$ 会在输入 $w$ 上运行 $M$；否则返回 'N'（表示“否”）。若 $M$ 在 $w$ 上停机，则 $R$ 返回 'Y'；否则 $R$ 会陷入无限循环而不停机。以下是 $R$ 的 Python 实现：

1import re
2def R(M,w):
3    if re.match('1+(01+){4}((001+(01)+){4})*',M):
4        M(w)    # 可能陷入无限循环！
5        return 'Y'
6    else:
7        return 'N'

代码解释

• 第1行：导入 Python 的 re 模块，用于处理正则表达式。
• 第2行：定义函数 R，接收两个字符串参数 M 和 w。
• 第3行：使用 re.match 判断 M 是否符合指定的正则表达式。若匹配，则执行下方代码块；否则执行 else 分支。
• 第4行：若 M 是合法的图灵机编码，则在 w 上运行 M。如果 M 在 w 上陷入无限循环，R 也会随之挂起，不会返回任何值。
• 第5行：若 M 是合法编码且在 w 上停机，则返回 'Y'。
• 第6行：若 M 不是合法的图灵机编码，则执行 else 分支。
• 第7行：返回 'N'，表示输入无效。

现在我们定义语言 $L_H = \{\langle M,w\rangle \;|\; M\text{ 是图灵机的编码，且 }M\text{ 在输入 } w \text{ 上停机}\}$。这是所有满足“图灵机在其输入上停机”的编码对组成的集合。我们知道 $L_H$ 是递归可枚举的，因为图灵机 $R$ 能够识别这些 $(M, w)$ 对（即：当 $M$ 在 $w$ 上停机时，$R$ 也会停机并接受）。但 $L_H$ 不是递归的，因为 $R$ 并不总能停机——当 $M$ 在 $w$ 上不停机时，$R$ 也会陷入无限循环。由于停机问题不可解，像 $R$ 这样的方法是定义该语言的唯一方式。因此，$L_H$ 是递归可枚举的，但不是递归的。

说明：符号 $\langle M,w\rangle$ 表示将 $M$ 和 $w$ 的编码组合成一个单一的输入字符串。

我们还可以得出另一个相关结论：语言 $L_d = \{\langle M\rangle \;|\; M \text{ 拒绝输入 } \langle M\rangle\}$ 不是递归的。假设存在某台图灵机 $M'$ 能够判定 $L_d$，并考虑这样一个问题：“$M'$ 是否属于 $L_d$？” 换句话说，当 $M'$ 接收到自己的编码 $\langle M'\rangle$ 作为输入时，它的行为如何？

• 如果 $M'$ 接受 $\langle M'\rangle$，那么根据定义，$M'$ 属于 $L_d$；
• 但根据 $L_d$ 的定义，属于它的图灵机必须拒绝自己的编码，这就意味着 $M'$ 应该拒绝 $\langle M'\rangle$，矛盾！

反之，如果 $M'$ 不属于 $L_d$，那么它应当拒绝 $\langle M'\rangle$，但这又意味着它不接受自己的编码，从而应属于 $L_d$，再次矛盾！

说明：符号 $\langle M\rangle$ 表示图灵机 $M$ 的字符串编码。

因此，语言 $L_d = \{\langle M\rangle \;|\; M \text{ 拒绝 } \langle M\rangle\}$ 是递归可枚举的，但不是递归的。

现在我们可以进一步给出一个非递归可枚举的语言：$\overline{L_H}$，即 $L_H$ 的补集。如果 $L_H$ 和它的补集都是递归可枚举的，那么它们都将是递归的。但 $L_H$ 并非递归的（因为停机问题不可解），所以 $\overline{L_H}$ 必须是非递归可枚举的。同理，由于 $L_d$ 是递归可枚举但非递归的，其补集 $\overline{L_d}$ 也是非递归可枚举的。