可归约性

可规约性： 一个基本方法，可用来证明问题是计算上不可解的。规约是将一个问题转化为另一个问题的方法，使得可以用第二个问题的解来解第一个问题。

如从波士顿到巴黎履行问题可规约到买这两个城市之间的飞机票问题。这个问题又可规约到挣得买飞机票钱的问题。数学问题中也有可规约性。例如测量一个矩形面积问题可规约到测量它的高和宽问题。解线性方程组问题可规约到求矩阵的逆问题。

6.1 语言理论中的不可判定问题

$HALT_{TM}=\{<M, \omega>|M是一个图灵机，且对输入\omega 停机 \}$

定理6.1 $HALT_{TM}$ 是不可判定的。

证明为得到矛盾，假设TM T判定 $HALT_{TM}$ ，由之可以构造TM S来判定 $A_{TM}$ ，其构造如下：

S = 在输入 $<M, \omega>$ 上，此处 $<M, \omega>$ 是TM M和串 $\omega$ 的编码：

在输入 $<M, \omega>$ 上运行TM R。
如果R拒绝，则拒绝。
如果R接受，则在 $\omega$ 上模拟M，直到它停机。
如果M已经接受，则接受；如果M已经拒绝，则拒绝。”

显然，如果R判定 $HALT_{TM}$ ，则S判定 $A_{TM}$ 。因为 $A_{TM}$ 是不可判定的，故 $HALT_{TM}$ 也是不可判定的。

定理6.2 $E_{TM}$ 是不可判定的。

$E_{TM}=\{M是一个TM，且L(M)=\Phi \}$

另一个与图灵机有关的计算问题也很有意思，该问题是：给定一个图灵机和一个可由某个更简单的计算模型识别的语言，检查图灵机是否识别此语言。例如，令 $REGULAR_{TM}$ 时间差一个给定的图灵机是否有一个与之等价的有穷自动机问题，则这个问题与检查一个给定的图灵机是否识别一个正则语言问题相同。设

$REGULAR_{TM}=\{<M>|M是一个TM，且L(M)是一个正则语言\}$

定理6.3 $REGULAR_{TM}$ 是不可判定的。

可类似的证明，检查一个图灵机的语言是不是下列语言都是不可判定的：上下文无关语言、可判定语言甚至有限语言。事实上，关于这个问题有一个更一般性的结果，称为赖斯定理。它指出：检查关于语言的任何一个性质是否可由图灵机识别都是不可判定的。

利用计算历史的规约

定义6.5 设M是一个图灵机， $\omega$ 是一个串。M在 $\omega$ 上的一个接受计算历史是一个格局序列 $C_1, C_2, \dots, C_l$ ，其中 $C_1$ 是M在 $\omega$ 上的起始格局， $C_l$ 是M的接受格局，且每个 $C_i$ 都是 $C_{i-1}$ 的合法结果，即符合M的规则。类似地，M在 $\omega$ 上拒绝格局...