【计算理论】06 可归约性

本章要点

1. 可归约性定义；
2. 映射可归约：若$A{\le }_{m}B$且$A$不可判定，则$B$也是不可判定证明；$A{\le }_{m}B$与$\overline{A}{\le }_m\overline{B}$等价性证明；
3. $HAL{T}_{TM},E_{TM},REGULA{R}_{TM},E{Q}_{TM}$的归约；
4. $E{Q}_{TM}$和其补都不是图灵可识别的证明。

可归约性

在以图灵机为通用计算机的前提下，可判定章节讨论了一些在图灵机上可解的问题；并给出了一个图灵机不可解的实例：$A_{TM}$。

在可归约章节中，将进一步给出其他图灵机不可解的实例，并通过论证$A_{TM}$可以归约到这些实例，证明其不可解性。

简单来说，就是$A_{TM}$问题可以归约到$B$问题（可以使用$B$问题构造出$A_{TM}$的判定器），如果$B$问题可解（可判定），那么$A_{TM}$也会可判定，导致矛盾，从而反证出$B$不可判定。

映射可归约

和黑书顺序不同，这里先把这个概念明确一下。

映射可归约是一种简单的从一个问题归约到另一个问题的方法。核心理念是，通过一个可计算函数，将问题$A$转化为问题$B$的实例，然后解决问题$B$。这种思想在时间复杂度、空间复杂度的完全性问题，以及本章中将要讨论的几个不可解问题中，有充分体现。

首先给出可计算函数的定义：

定义：称$f:{\Sigma }^{?}\to {\Sigma }^{?}$是一个可计算函数，如果$f$对所有的输入$w$都停机，并且停机后只有$f(w)$出现在带子上。

进而定义映射可归约性：

定义：如果存在可计算函数$f:{\Sigma }^{?}\to {\Sigma }^{?}$，对每个$w\in A$，都有
$$w\in A?f(w)\in B$$
则称语言$A$映射可归约到语言$B$，记$A{\le }_{m}B$，称$f$为$A$到$B$的归约。

定理：如果$A{\le }_{m}B$且$B$是可判定的，则$A$也是可判定的。

证明：已知$B$可判定，使用$B$的判定器$M$，根据映射可归约的定义，构造$A$的判定器$N$：
$$\begin{array}{l}N=\text{“对输入}w:\\ 1.计算f(w);\\ 2.在f(w)上运行M，输出M的输出。\text{”}\end{array}$$
推论：若$A{\le }_{m}B$且$A$不可判定，则$B$也是不可判定的。

证明：若$A{\le }_{m}B$且$A$不可判定，假设$B$可判定，则根据定理可知，$A$应该是可判定的，矛盾，故$B$应该是不可判定的。

该推论是证明问题不可判定的常用工具。

由于映射可归约是一种简单的归约方法，故不是所有的归约都属于映射可归约，对于难以找到可计算函数的归约问题，可能采用的就不是映射可归约。事实上，下文可判定归约证明中就有不是映射可归约证明的。

图灵可判定归约证明

图灵可归约的证明通常基于构造已经得证的不可判定图灵机进行，例如构造若B成立，则可由B规约$A_{TM}$，因为$A_{TM}$不可判定，所以B不成立。

$HAL{T}_{TM}$不可判定

给出$HAL{T}_{TM}$的定义，并回顾下$A_{TM}$的定义：
H A L T T M = { < M , w > ∣ M 为图灵机，对输入 w 停机 } A T M = { < M , w > ∣ M 为图灵机， M 接受 w } HALT_{TM} = \{<M, w>| M为图灵机，对输入w停机\}\\ A_{TM} = \{<M, w> | M为图灵机，M接受w\} HALTTM?={<M,w>∣M为图灵机，对输入w停机}ATM?={<M,w>∣M为图灵机，M接受w}
证明思路：$A_{TM}$对$M$拒绝和循环的输出都是拒绝，因此首先使用$HAL{T}_{TM}$的判定器判定是否停机，不停机就拒绝；然后再在$w$上模拟$M$。

证明：假设$HAL{T}_{TM}$是可判定的，使用$HAL{T}_{TM}$归约$A_{TM}$，设判定$HAL{T}_{TM}$的图灵机为$R$，构造判定$A_{TM}$的图灵机$S$：
$$\begin{array}{l}S=\text{“对输入}<M,w>:\\ 1.在输入<M,w>上运行R;\\ 2.若R拒绝，则拒绝;\\ 3.若R接受，在w上运行M，直到停机;\\ 4.若M接受，则接受；若M拒绝，则拒绝。\text{”}\end{array}$$
从上面的构造可以看出，若$R$可判定$HAL{T}_{TM}$，则$S$可判定$A_{TM}$，因为$A_{TM}$是不可判定的，故$HAL{T}_{TM}$也应该是不可判定的。

$E_{TM}$不可判定

给出$E_{TM}$的定义：
E T M = { < M > ∣ M 为图灵机， L ( M ) = ? } E_{TM} = \{<M> | M为图灵机，L(M) = \varnothing\} ETM?={<M>∣M为图灵机，L(M)=?}
证明思路：仍然需要构造$A_{TM}$的判定器，但$E_{TM}$与$A_{TM}$的联系性是比较难想的。这个联系等价于找到$?$与$w$的关系，即如果$M$接受/不接受$w$，应该推导出$?$。

可以根据$M$和$w$的描述，尝试构造这样一台新的图灵机$M_1$：
$$\begin{array}{l}{M}_1=\text{“对输入}x:\\ 1.若x\ne w,则拒绝;\\ 2.若x=w,则在w上模拟M，若M接受，则接受。\text{”}\end{array}$$
图灵机$M_1$唯一能够识别的串就是$w$，当且仅当$x=w$时，$L(M_1)\ne ?$。如果$E_{TM}$是可判定的，就可以通过判定$M_1$的语言是否为$?$，得知$M$是否接受$w$。设$E_{TM}$的判定器为$R$，如果$R$接受，则意味着$L(M_1)=?$，即$M$不接受$w$；反之，则意味着$M$接受$w$。

证明：假设$E_{TM}$是可判定的，设其判定器为$R$，构造判定$A_{TM}$的判定器$S$：
$$\begin{array}{l}S=\text{对输入}<M,w>:\\ 1.使用M和w的描述，构造只接受w的图灵机M_1;\\ 2.使用R判定M_1;\\ 3.若R接受，则拒绝；若R拒绝，则接受。\text{”}\end{array}$$
从上面的构造可以看出，若$R$可以判定$E_{TM}$，则$S$可以判定$A_{TM}$，由于$A_{TM}$是不可判定的，故$E_{TM}$也应该是不可判定的。

$REGULA{R}_{TM}$不可判定

给出$REGULA{R}_{TM}$的定义：
R E G U L A R T M = { < M > ∣ M 为图灵机，且 L ( M ) 为正则语言 } REGULAR_{TM} = \{<M>| M为图灵机，且L(M)为正则语言\} REGULARTM?={<M>∣M为图灵机，且L(M)为正则语言}
证明思路：与$E_{TM}$的思路类似，我们需要找到判定正则语言与判定接受$w$之间的联系，即，如果$M$接受$w$，则$L(M)$为正则语言；如果$M$不接受$w$，则$L(M)$为非正则语言。构造图灵机$M_2$来描述这种关系（设字母表为 { 0 , 1 } \{0,1\} {0,1}）：
$$\begin{array}{l}{M}_2=\text{“对输入}x:\\ 1.若x具有形式0^n{1}^n，则接受，此时M_2的语言为非正则;\\ 2.若x具有形式{\Sigma }^{?}，则在w上运行M。若M接受w，则接受。此时M_2的语言是正则语言。\text{”}\end{array}$$
证明：假设$REGULA{R}_{TM}$可判定，且判定器为$R$，构造判定$A_{TM}$的判定器$S$：
$$\begin{array}{l}S=\text{对输入}<M,w>:\\ 1.使用M和w构造上述的图灵机M_2;\\ 2.在输入<M_2>上运行R;\\ 3.若R接受，则接受；若R拒绝，则拒绝。\end{array}$$
从上述构造中可以看出，如果$R$可以判定$REGULA{R}_{TM}$，则$S$可以判定$A_{TM}$，由于$A_{TM}$不可判定，故$REGULA{R}_{TM}$应该是不可判定的。

在$M_2$的构造中，$x$的形式没有固定要求，只要一个是正则一个是非正则就好，因为重点不是$M_2$识别的语言具体是什么，而是能否用判定器$R$判定$M_2$的语言是不是正则语言。

$E{Q}_{TM}$不可判定

给出$E{Q}_{TM}$的定义：
E Q T M = { < M 1 , M 2 > ∣ M 1 , M 2 都是图灵机，且 L ( M 1 ) = L ( M 2 ) } EQ_{TM} = \{<M_1, M_2>|M_1, M_2都是图灵机，且L(M_1) = L(M_2)\} EQTM?={<M1?,M2?>∣M1?,M2?都是图灵机，且L(M1?)=L(M2?)}
证明思路：$E{Q}_{TM}$利用$E_{TM}$来进行构造，同样是要寻找两者之间的联系：令$L(M_1)=?$，若$EQ(M_1,M_2)$，则$M_2$的语言也应该是空的。

证明：假设$E{Q}_{TM}$可判定，设判定器为$R$，构造判定$E_{TM}$的判定器$S$：
$$\begin{array}{l}S=\text{对输入}<M>:\\ 1.在输入<M,M_1>上运行R，M_1为拒绝所有输入的图灵机，即L(M_1)=?\\ 2.如果R接受，则接受；如果R拒绝，则拒绝。\text{”}\end{array}$$
从上述构造中可以看出，如果$R$可以判定$E{Q}_{TM}$，则$S$可以判定$E_{TM}$，因为$E_{TM}$不可判定，故$E{Q}_{TM}$也是不可判定的。

图灵可识别的归约性

映射可归约性对求补运算是敏感的，在可判定章节，我们提到了补图灵可识别的概念，这里对其归约性进行说明。

首先给出图灵可识别的归约定理，形式上非常类似映射可归约一节中可判定性的归约定理：

定理：如果$A{\le }_{m}B$且$B$是图灵可识别的的，则$A$也是图灵可识别的。

只需要将上文中证明的判定器改为识别器，就可以证明该定理。推论同理：

推论：若$A{\le }_{m}B$且$A$不可识别，则$B$也是不可识别的。

推论：$A{\le }_{m}B$与$\overline{A}{\le }_m\overline{B}$具有相同含义。

证明：已知$A{\le }_{m}B$，则有对应关系：
$$?w\in A??f(w)\in B$$
若$?w\in \overline{A}$，使得$f(w)\notin B$，则意味着该$f(w)\in B?w\in A$，导致矛盾。

故$?w\in \overline{A}$，都应有$f(w)\in \overline{B}$。

这个证明记一下，可能会考。

上述定理在证明可识别性归约问题有典型的应用：因为$\overline{A_{TM}}$不是图灵可识别的，因此如果想要证明$B$不是图灵可识别的，可以证明$A_{TM}{\le }_m\overline{B}$，就相当于证明$\overline{A_{TM}}{\le }_{m}B$。

定理：$E{Q}_{TM}$既不是图灵可识别的，也不是补图灵可识别的。

证明：

1. 首先证明$E{Q}_{TM}$不可识别，给出从$A_{TM}$到$\overline{E{Q}_{TM}}$的归约：
   $$\begin{array}{l}F=\text{“对输入}<M,w>,M为图灵机，w为串:\\ 1.构造图灵机M_1,M_2：\\ M_1=\text{“对任何输入}:\\ a.拒绝。\text{”}\\ M_2=\text{“对任何输入}:\\ a.在w上运行M，若M接受，则接受。\text{”}\\ 2.输出<M_1,M_2>。\text{”}\end{array}$$
   由于$M_1$什么也不接受，若$M$接受$w$，则$M_2$接受，两个机器不等价；反之，如果$M$不接受$w$，则两个机器等价。因为$\overline{A_{TM}}$不是图灵可识别的，且$A_{TM}{\le }_m\overline{E{Q}_{TM}}?\overline{A_{TM}}{\le }_{m}E{Q}_{TM}$，故$E{Q}_{TM}$不是可识别的。

2. 同理，只需将$M_1$的描述改为对任何输入都接受，可以得到$A_{TM}$到$E{Q}_{TM}$的归约，从而证明补图灵不可识别。

参考

• 《计算理论导引》第二版，机械工业出版社