Theory of Computation: Reduction
Published:
不知道在写什么。
学计算理论的时候发现规约这个东西太抽象了，而且可能会有很多考法。笔者在此整理了 PPT 上的例子，希望能够帮助大家理解这个东西，并且提供一些新的思考。
规约的定义
定义：对于 $A,B$ 两个在 $Σ$ 上的语言，如果存在一个 recursive function $f: Σ^* \to Σ^$，使得对于任意 $x \in Σ^$，有 $x \in A \Leftrightarrow f(x) \in B$，则称 $A$ 可规约到 $B$，记作 $A \leq B$。
思考一下这个当且仅当是为什么。他的意思就是，语言 $A$ 可以通过一系列可计算变化，变成语言 $B$ 的子集，而且这些变化一定是：
可计算的，也就是 recursive function。不然毫无意义。
对于非 $A$ 的字符串，变化后一定不在 $B$ 里面。
第二条是为什么呢？我们来看下面的内容。
规约的性质
定理：$A \leq B$ 且 $B$ 是可判定的，则 $A$ 也是可判定的。
这个定理的证明是很简单的，因为我们可以通过 $f$ 来构造一个判定 $A$ 的算法：
对于要判定的字符串 $a$，我们先计算 $f(a)$。
如果 $f(a) \in B$，则 $a \in A$；否则 $a \notin A$。
判断 $f(a) \in B$ 是直接用判定 $B$ 的图灵机即可。
推论就是其逆否命题：
推论：$A \leq B$ 且 $A$ 是不可判定的，则 $B$ 也是不可判定的。
可以发现，如果我搞一个 $f(x) = e$，那显然 ${e}$ 是可判定的，但是这样就毫无意义了。所以我们要求规约的 $f$ 是一个对于任意 $x \in Σ^*$，有 $x \in A \Leftrightarrow f(x) \in B$ 的函数。
还有一个推论：
推论：$A \leq B \Leftrightarrow \overline A \leq \overline B$。
判定
我们接下来要证明的判定问题，其语境是判定图灵机和一个输入，是否满足 XXX 性质。
在 Universal Turing Machine 的语境下，我们可以通过输入 $\langle M, x \rangle$ 来表示一个图灵机和一个输入。所以一个图灵机和一个输入就可以唯一确定一个字符串。我们接下来讨论的判定问题就是，给一个字符串（这个字符串是由图灵机和输入构成的，类似一个压缩包），判断这个图灵机和输入是否满足某种性质。
先做一些约定吧：
我们证明的思路，是已知停机问题是不可判定的，然后通过规约来证明其他问题是不可判定的。接下来证明的东西全都是不可判定的。
我们会把要判定的字符串统一写成 $\langle M, x \rangle$，代表一个压缩包。最后我们要判定的语言肯定不包括「无效的压缩包」。图灵机的压缩可以参考 PPT 和学长笔记，这里不再赘述。
假设存在一个 Universal Turing Machine $U$，他可以接受一个字符串 $\langle M, x \rangle$，然后模拟 $M$ 在输入 $x$ 上的运行。后面我会直接写成 $U$ 这个符号。
可以发现，$f$ 不一定要是一个一一映射，他可以是多对一的。不过在现实语境下，我们只需要构造一个一一映射的 $f$ 就可以。那么在图灵机的语境下，很多一一映射其实在逻辑上是显然成立的，比如令 $f(\langle M, x \rangle)$ 为一个融合了老图灵机和输入的新图灵机，这显然是一个一一映射，后面会看到很多这样的做法。
重要！：$w$ 特别表示停机问题中 $w$ 的输入！！！不是改造后的自动机 $M_w$ 的输入！！！
例子
已知的结论是什么？
- 判定问题 $A_0$：给定一个图灵机 $M$，判断 $M$ 是否在输入 $w$ 上停机。
接下来我们统一写成这样的形式：
- \[A_0 = \{ \langle M, w \rangle | M \text{ halt on } w \}\]
根据停机问题的结论，这是不可判定的。
三个最简单的判定问题
- \[A_1 = \{ \langle M \rangle | M \text{ halt on } e \}\]
意思是说，判定一个图灵机是否在空串上停机。
一看就是不可判定的啊，第一眼的思路是，这不就是停机问题的子集嘛？这其实就是判断一个图灵机是否在给定输入上停机的问题，只不过我们固定这个输入是 $e$。所以应该是不能判定的。但是我们只能把 $A_1$ 规约到 $A_0$ 上，无法证明 $A_1$ 是不可判定的。
所以我们证明的思路是，证明 $A_0$ 可以规约到 $A_1$ 上。这样就可以证明 $A_1$ 是不可判定的。
这不是很抽象么？但是好像只有这条路可以走。我们直接考虑把停机问题魔改一下，看看能不能转化成 $A_1$。
一个思路是，我把输入融合到图灵机里，这样输入是不是就是空串了？我们可以构造一个新图灵机 $M_w$，他的输入是 $e$，他的行为是：
先把输入 $w$ 写到输入带上。
然后再运行 $M$。
这样 $M_w$ 就是一个在空串上运行的图灵机了。我们只需要判断 $M_w$ 是否在空串上停机就可以了。这样我们就成功的完成了规约。
整理一下，我们的构造函数就是：
\[f(\langle M, w \rangle) = \langle Rw_1Rw_2\cdots L_{⌴ }M, e\rangle\]这显然是一个一一映射，因为对于 $M_w$ 我们都可以反解出 $M$ 和 $w$。所以我们证明了 $A_0 \leq A_1$，所以 $A_1$ 是不可判定的。
- \[A_2 = \{ \langle M \rangle | M \text{ halt on any input string} \}\]
这个问题是判断一个图灵机是否在某个输入上停机。这似乎不那么显然了，但是我们还是可以用刚才的思路去走。
我们只要大力套用 $A_1$ 的证明思路。我们沿用 $M_w$ 的构造，只不过我们加一个判断：
判断输入是否是空串，如果不是空串，就死循环。
先把输入 $w$ 写到输入带上。
然后再运行 $M$。
这样，我们就构造出了一个图灵机 $M_w$，我们判断 $M_w$ 是否存在一个输入可以停机即可。非常搞笑的是，如果 $M_w$ 停机，那给定的输入肯定是 $e$，这样我们就证明了 $A_0 \leq A_2$，所以 $A_2$ 是不可判定的。
仔细咀嚼一下这个思路，你就可以发现有多大力出奇迹了。关键是，这么大力的依据是什么呢？那就是，显然这个问题比停机问题强多了！人家只需要判断一个输入，而你需要判断所有输入。所以我们在证明的时候也可以大力一些。
- \[A_3 = \{ \langle M \rangle | M \text{ halt on every input string} \}\]
老思路，但是判断的 trick 用不了了，因为这样对于所有非 $w$ 输入都会停机…那我们还可以把输入给擦除啊！我们构造一个新图灵机 $M_w$，他的行为是：
先把输入全部抹除。
再把输入 $w$ 写到输入带上。
然后再运行 $M$。
这样，我们判断 $M_w$ 是否在任意输入上停机就可以了。这样我们就证明了 $A_0 \leq A_3$，所以 $A_3$ 是不可判定的。这个思路其实也可以用来证明 $A_2$。
我又想到，其实还可以构造这样的 $M_w$：
判断输入是否是空串，如果不是空串，就停机。
再把输入 $w$ 写到输入带上。
然后再运行 $M$。
读者可以想一下这样为啥可以规约。接下来的例子希望读者自己思考，然后再看答案 （因为我写这个讲义也是自己思考了一遍的，没直接看答案）。
两个图灵机？
- \[A_4 = \{ \langle M_1, M_2 \rangle | L(M_1) = L(M_2) \}\]
判断两个图灵机是否 halt on the same input string。这个问题看起来很复杂，但是我们可以用刚才的思路来证明。
直接规约好像毫无思路，我们想想看如果直接做怎么做，那肯定是遍历每一个输入，然后看是否停机，如果都停机/都不停机就尝试下一个输入，否则不接受。但这显然有两个问题：
无穷多个输入，根本无法给出「接受」。
无法判断是否停机。
那答案肯定是无法判定的，因为比停机问题强太多。借此，我们可以想到，好像可以把停机问题规约过来，如果用刚才的 $M_w$，然后构造一个永远停机的图灵机 $H_{\text{halt}}$，$L(H_{\text{halt}})=\sum^*$，判断他们是否等价不就可以了嘛？
答案呼之欲出，构造一个新图灵机 $M_w$，他的行为是：
再把输入 $w$ 写到输入带上。
然后再运行 $M$。
注意：如果 $M$ 在 $w$ 上停机，那么 $L(M_w)$ 是 $\sum^*$，否则是空语言。
这样我们只要判断 $M_w$ 和 $H_{\text{never}}$ 是否 halt on the same input string 就可以了，如果 halt on the same input string 说明停机——$L(M_w)$ 是 $\sum^*$ 嘛，否则不停机。这样我们就证明了 $A_0 \leq A_4$，所以 $A_4$ 是不可判定的。
PPT 上的证明和我的思路不一样，其实是等价的，他是证明 $A_3$ 可以规约到 $A_4$ 上。然后怎么做 $A_3$ 呢？他构造了一个新的永远停机的 $M’$，然后判断 $M’$ 和 $M$ 是否等价。这样也是可以的，只不过我的做法更好想（x）
正则/上下文无关/可递归？
- \[A_5 = \{ \langle M \rangle | L(M) \text{ is regular} \}\]
- \[A_6 = \{ \langle M \rangle | L(M) \text{ is context-free} \}\]
- \[A_7 = \{ \langle M \rangle | L(M) \text{ is recursive} \}\]
其实 $A_7$ 肯定是不可判定的，因为这就是 $A_3$，我们先思考一下 $A_5$ 怎么做吧。
还是可以大力一点，我们继续考虑停机问题。我们可以构造一个新的图灵机 $M_w$ 实现这样的效果：
如果 $M$ 在 $w$ 上停机，那么 $L(M_w)$ 是 regular。
如果 $M$ 在 $w$ 上不停机，那么 $L(M_w)$ 是 non-regular。
| 当然，上下可以相反，那么我们先随便找一个 non-regular 的语言，比如 $L = {0^n1^n | n \geq 0}$。然后构造这样的 $M_w$： |
判断输入（注意这里的输入不是 $w$，是 $M_w$ 的输入）是否属于 $L$，如果属于 $L$，就停机。
再把输入 $w$ 写到输入带上。
然后再运行 $M$。
这样如果 $M$ 在 $w$ 上停机，那么 $L(M_w)=\sum^*$ 是 regular 的，如果 $M$ 不停机，那么 $L(M_w)$ 是 non-regular 的，因为它只在一个非正则的语言 $L$ 上停机。所以我们判断 $L(M_w)$ 是否正则，就可以推断停机问题。我们也就此证明了 $A_0 \leq A_5$，所以 $A_5$ 是不可判定的。
$A_6$ 的证明思路显然也是同理的。
Rice 定理
之前我们利用停机问题规约证明的不可判定方法有一个共性就是，他们都是为了判定这样的集合：
\[A = \{ \langle M \rangle | L(M) \text{ 满足某种性质 P} \}\]如果设满足所有性质 P 的 recursively enumerable 语言集合为 $L_P$，那么等价于判定：
\[A = \{ \langle M \rangle | L(M) \in L_P \}\]有这样的定理：
定理（Rice 定理）：如果 $L_P$ 是空集或者包含所有 recursively enumerable 语言，那么 $A$ 是可判定的；反之那么 $A$ 是不可判定的。
意思是说，对于所有 recursively enumerable 语言都满足的性质（或者都不满足），才可以被判定。这是一个非常强的定理，因为他告诉我们，只要有一个例外，就不可判定。你观察一下前面的例子，就会发现他们都是这样的。所以我们可以用 Rice 定理来判断很多不可判定的问题。
思考一下这个很强的定理的证明，还是考虑规约。
首先如果 $L_p$ 是空集，那么显然 $A$ 是空语言，这是可判定的。
然后是一个分类讨论：
情况 1
如果 $L_p$ 不包含空语言，我们尝试把 $A_0$ 规约到 $A$ 上。我们只需要构造一个新图灵机 $M_w$，他的行为是：
把输入 $w$ 写到输入带上。
然后再运行 $M$。
如果 $M$ 在 $w$ 上不停机，那么 $L(M_w)$ 是空语言，不属于 $L_p$。如果 $M$ 停机，那么 $L(M_w)$ 为 ${e}$，但是我们不知道它是不是属于 ${L_p}$。所以我们随便找一个 $L_p$ 中的语言 $L_0$，修改 $M_w$ 的行为：
判断是否属于语言 $L_0$，这里直接用 $L_0$ 对应图灵机判断即可，如果不属于则自动死机。
把输入 $w$ 写上。
然后再运行 $M$。
这样的话，如果 $M$ 在 $w$ 上停机，那么 $L(M_w)$ 是 $L_0$，属于 $L_p$。如果 $M$ 不停机，那么 $L(M_w)$ 是空语言，不属于 $L_p$。这样我们又规约成功了。
情况 2
如果 $L_p$ 包含空语言，最简单的方法是考虑其补集 $\overline{L_p}$。显然 $\overline{L_p}$ 不包含空语言。
如果 $L_p$ 是 recursively enumerable 集合的全集，那么补集是空集，补集可判定，$L_p$ 对应的集合 $A$ 也可判定。
反之，如果 $L_p$ 不是全集，那么补集不是空集，补集不可判定，$L_p$ 对应的集合 $A$ 也不可判定。
这样我们就证明了 Rice 定理。冷静下来看，其实这个证明正是 $L_5$、$L_6$、$L_7$ 证明的一般形式。所以写了这么多，前面都白写了啊，艹了。
这些题目都是最简单的，但是也是最经典的，后面有很多很多的变式题，大家可以参考一下 98 资料。