理论计算机科学基础随堂笔记。第6章-2：图灵归约

使用教材：《计算理论导引》（原书第3版） Michael Sipser 著，机械工业出版社

目录

• 第6章-2 图灵归约
  • 6-2.1 定义
    • 6-2.1.1 谕示图灵机
    • 6-2.1.2 图灵归约
    • 6-2.1.3 谕示图灵机接受的语言
  • 6-2.2 性质
    • 6-2.2.1 比映射归约强
    • 6-2.2.2 封闭性
    • 6-2.2.3 传递性
  • 6-2.3 应用
    • 6-2.3.1 语言类的刻画
    • 6-2.3.2 相对化计算
    • 6-2.3.3 将搜索问题归约到判定问题

第6章-2 图灵归约

映射可归约性不能完全刻画可归约性的概念。直观考虑，$A_{TM}$和$\overline{A_{TM}}$应当可以互相归约，因为它们其中一个的解反过来就是另一个的解。但$\overline{A_{TM}}$不能映射归约到$A_{TM}$上，因为$A_{TM}$是图灵可识别的，但$\overline{A_{TM}}$不是。

下面介绍图灵可识别，它能更深刻地刻画可归约性的概念。

6-2.1 定义

6-2.1.1 谕示图灵机

语言B的一个谕示是一个能够报告某个串w是否属于语言B的外部装置。

一个谕示图灵机是一种修改过的图灵机，除具有图灵机的全部功能外，还有询问一个谕示的额外能力。换句话说，谕示图灵机多了一条查询带，带上写一个字符串w，进入查询状态$q_{query}$，若$y\in B$，则进入状态$q_{yes}$，否则进入状态$q_{no}$。记$M^B$为对语言B有谕示的谕示图灵机。

我们不关心谕示的内部工作机制，使用“谕示”这个术语就意味着一种神奇的能力，意味着将考虑不能由普通算法判定的语言（包括停机问题等不可计算问题）的谕示。

6-2.1.2 图灵归约

如果$M^B$可以判定语言$A$，就称$A$是相对于$B$可判定的，同时称语言$A$图灵可归约到$B$，记作$A\leq_T B$。即

\[A\leq_T B\stackrel{\Delta}{\Leftrightarrow}A=L(M^B)\]

6-2.1.3 谕示图灵机接受的语言

设$A$是一个语言，$C$是一个语言类（即它是某类图灵机所接受的语言），则$C^A$就是由带谕示$A$的同类图灵机所接受的语言。即

\[\begin{aligned} C & =\left\{L\mid L=L(M), M是某类图灵机\right\}\\ C^A & =\left\{L\mid L=L(M^A), M^A是带谕示A的某类图灵机\right\} \end{aligned}\]

例如，考虑这里的$C=\Sigma_1$，则$\Sigma_1^{A_{TM}}$定义为

\[\Sigma_1^{A_{TM}}=\left\{L\mid L=L(M^{A_{TM}}), M相对于谕示A_{TM}图灵可识别L\right\}\]

换句话说，$M^{A_{TM}}$图灵可识别$L$，即输入$x\in L$时$M^{A_{TM}}$会停机接受，$x\notin L$时$M^{A_{TM}}$停机拒绝或不停机。

6-2.2 性质

6-2.2.1 比映射归约强

这个性质是说，存在语言$A,B$，有$A\leq_T B$但$A\nleq_m B$。

在引入部分已经讨论了，$A_{TM}$不能映射归约到$\overline{A_{TM}}$上。但图灵归约可以实现。更一般的，我们考虑从$A$到$\bar A$的归约：

图灵机$M^{A}$定义如下：

$M^{A}$ = “对于输入$x$，

1. 询问谕示，是否有$x\in A$。
2. 如果谕示回答no，则接受，否则拒绝。

这样，只要输入$x\in A$，$M^A$就拒绝，否则$M^A$接受，显然$L(M^A)=\bar A$。

6-2.2.2 封闭性

如果$A\leq_m B$（或$A\leq_T B$）能否有结论：

B可判定/图灵可识别/补图灵可识别$\Rightarrow$A可判定/图灵可识别/补图灵可识别？

下面的表格回答了这个问题，即两种归约对计算问题的封闭性。

	可判定	图灵可识别	补图灵可识别
$\leq_m$	√	√	√
$\leq_T$	√	×	×

图灵可识别是不封闭的，即

\[A\leq_T B, B图灵可识别\nRightarrow A图灵可识别\]

给一个具体的例子。我们首先定义集合的join运算：

\[A\oplus B := \left\{1x\mid x\in A\right\}\cup \left\{0x\mid x\in B\right\}\]

有结论：存在图灵归约$A_{TM}\oplus\overline{A_{TM}}\leq_T A_{TM}$，$A_{TM}$是图灵可识别的，而$A_{TM}\oplus\overline{A_{TM}}$不是图灵可识别的。¹

首先，能给出图灵归约$A_{TM}\oplus\overline{A_{TM}}\leq_T A_{TM}$，因此语言$A_{TM}\oplus\overline{A_{TM}} \in \Delta_2=\Delta_1^{A_{TM}}$。考虑$\forall x\in A_{TM}\oplus\overline{A_{TM}}$，若$x$第一个字母是1，就询问$x$去掉第一个字母后得到的串$w$是否属于$A_{TM}$，若第一个字母是0，就问$w$是否不属于$A_{TM}$，这样谕示图灵机$M^{A_{TM}}$就可以判定该语言。

其次，$A_{TM}\oplus\overline{A_{TM}}\notin \Sigma_1$。否则也有$\overline{A_{TM}}\in \Sigma_1$，$A_{TM}$就成了可判定的了。

---

事实上，有如下结论：

\[\Sigma_2 = \Sigma_1^{A_{TM}}\\\ \\ \Pi_2 = \Pi_1^{A_{TM}}\\\ \\ \Delta_2 = \Delta_1^{A_{TM}}\]

下面的定理1将对上面结论的第一行$\Sigma_2 = \Sigma_1^{A_{TM}}$给一个证明。由定义或者类似的方法可以证明$\Pi_2 = \Pi_1^{A_{TM}}$和$\Delta_2 = \Delta_1^{A_{TM}}$。

定理1

\[\Sigma_2=\Sigma_1^{A_{TM}}=\Sigma_1^{\Sigma_1}\]

证明：首先证明$\Sigma_2=\Sigma_1^{A_{TM}}$，通过集合互相包含的方法来证明集合相等：

① $\Sigma_2\subseteq \Sigma_1^{A_{TM}}$：

$\forall L\in \Sigma_2$，则L具有形式：

\[L=\left\{x\mid \exists y_1,\forall y_2, \langle x,y_1,y_2\rangle \in C\right\}\]

其中C可判定。

定义$L_1$：

\[L_1=\left\{\langle x,y_1\rangle\mid \forall y_2,\langle x,y_1,y_2\rangle \in C\right\}\]

则$L_1\in \Pi_1$。因此$\overline{L_1}\in \Sigma_1$。由$A_{TM}$是$\Sigma_1$完全的性质²，存在映射归约$\overline{L_1}\leq_m A_{TM}\ via\ f$。

据此构造图灵机$M^{A_{TM}}$如下：

$M^{A_{TM}}$ = “对于输入$x$，

1. 枚举$y_1\in\Sigma^ * $。
2. 对每个$y_1$，询问谕示以确定是否有$\langle x,y_1\rangle \in \overline{L_1}\Leftrightarrow f(\langle x,y_1\rangle)\in A_{TM}\Leftrightarrow \big\langle M_1,\langle x,y_1\rangle \big\rangle \in A_{TM}$。
3. 若结果为“否”，则接受。

这样，只要输入$x\in L$，就存在$y_1$，使得$\langle x,y_1\rangle\in L_1(\notin \overline{L_1})$，这样$M^{A_{TM}}$结果就是接受，即$x\in L(M)$。

因此，这里的$L$相对于$A^{TM}$就是可判定的了。又由于$M^{A_{TM}}$接受的语言是图灵可识别的（接受 or 不停机），属于$\Sigma_1$类，因此$\Sigma_2\subseteq \Sigma_1^{A_{TM}}$。

② $\Sigma_1^{A_{TM}}\subseteq\Sigma_2$：

设$L\in \Sigma_1^{A_{TM}}$，则存在一台谕示图灵机$M^{A_{TM}}$，满足$L=L(M^{A_{TM}})$。当$x\in L$时，$M^{A_{TM}}$停机接受；当$x\notin L$时，$M^{A_{TM}}$停机拒绝或不停机。

因为$A_{TM}\in \Sigma_1$，所以$A_{TM}$可以有如下形式的表述：

\[A_{TM}=\left\{\langle M,x\rangle\mid \exists y,\langle M,x,y\rangle \right\}\]

这里可以将$y$取为$M$在$x$上的接受计算历史$\langle C_1,C_2,…,C_n\rangle$，详见5.6 利用计算历史的归约。

把$M^{A_{TM}}$在$x$上查询过的串³按照回答分为两类（实际问的顺序不一定按照下面的顺序）：

回答“是”的：$u_1,u_2,...,u_p$；
回答“否”的：$v_1,v_2,...,v_p$。

根据$A_{TM}$的定义：

\[\exists \langle s_1,s_2,...,s_p\rangle , 使得\langle u_i,s_i\rangle \in D, i=1,2,...,p\\ \forall \langle t_1,t_2,...,t_q\rangle , 都有\langle v_i,t_i\rangle \notin D, i=1,2,...,q\]

于是$x\in L\Leftrightarrow\exists\langle y,u_1,u_2,…,u_p,v_1,v_2,…,v_q,s_1,s_2,…,s_p\rangle,\forall \langle t_1,t_2,…,t_q\rangle$，“$y$是$M^{A_{TM}}$在$x$上的接受计算历史，且查询过的串属于{$u_1,u_2,…,u_p,v_1,v_2,…,v_q$}，当查询过的串属于{$u_1,u_2,…,u_p$}时回答‘是’，当查询过的串属于{$v_1,v_2,…,v_q$}时回答‘否’。这里$\langle u_i,s_i\rangle\in D$，$\langle v_i,t_i\rangle\notin D$。”

由于上面引号里的蓝色内容是可判定的，故$L\in \Sigma_2$。■

6-2.2.3 传递性

\[A\leq_m B, \quad B\leq_m C\Rightarrow A\leq_m C\] \[A\leq_T B, \quad B\leq_T C\Rightarrow A\leq_T C\]

事实上图灵归约和映射归约都是等价关系，兼具自反、对称和传递性。

6-2.3 应用

6-2.3.1 语言类的刻画

前面已经提到了：

\[\Sigma_1 = \Sigma_2^{A_{TM}}\\\ \\ \Pi_1 = \Pi_2^{A_{TM}}\\\ \\ \Delta_1 = \Delta_2^{A_{TM}}\]

6-2.3.2 相对化计算

前面亦已提到。

6-2.3.3 将搜索问题归约到判定问题

举个例子，SAT问题是说，给一个布尔函数式，判断是否有一组赋值能使得该函数输出为1，如果有输出这样一组赋值，如果没有就输出不存在。

好，现在拿到一个布尔函数式$\phi(x_1,x_2,…,x_n)$。我们可以问问神谕：$\phi(x_1,x_2,…,x_n)\in SAT$吗？如果不属于，直接输出不存在。否则对$x_1$赋值为0，问问神谕：$\phi(0,x_2,…,x_n)\in SAT$吗？如果不存在，就把$x_1$赋值为1，否则$x_1$保留为0，然后将$x_2$赋值为0，以此类推。

这样，我们是在搜索一组解，但搜索的过程是通过判定来实现的，形成了一棵搜索树。

寻求有向图的点s到t的路径亦可通过此法。

通常的计算问题可以分成几大类：判定，搜索，计数，优化，验证，产生。后面的章节将会研究计算问题的复杂性理论。