存在一台通用图灵机$\mathcal U$ 满足

定理的证明将在专题中完成.

实际上, 这一部分并不是计算复杂性的核心内容, 因为我们很少关注不可计算的问题. 但是学习这一部分有助于理解图灵机的工作原理, 以及熟悉我们经常在计算复杂性\密码学\数学中使用的一个重要技巧: 归约 (reduction).

定义函数$\mathsf{UC}:\{0,1\}^\ast\to\{0,1\}$为
$$
\mathsf{UC}(\alpha)=\left\{\begin{align}&0,\quad M_\alpha(\alpha)=1\\&1, \quad\text{otherwise}\end{align}\right.
$$
这个问题用语言描述出来也不算复杂, 即对于输入$\alpha$, 如果它表示的图灵机$M_\alpha$接收到这个输入时, 在有限步骤内停机并输出$1$时, 则$\mathsf{UC}(\alpha)=0$. 否则, 即$M_\alpha(\alpha)=0$或者甚至不停机的时候, $\mathsf{UC}(\alpha)=1$. 现在我们来证明他的不可计算性.

假设存在一台图灵机$M_\beta$能够计算$\mathsf{UC}$, 那么根据$\mathsf{UC}$的定义有
$$
\mathsf{UC}(\beta)=1\iff M_\beta(\beta)\neq 1
$$
而根据$M_\beta$能够计算$\mathsf{UC}$, 有$M_\beta(\beta)=\mathsf{UC}(\beta)$, 这显然是矛盾的. 因此我们的假设不成立, 也就没有图灵机能够计算$\mathsf{UC}$. 这个证明的方法叫做对角线方法, 如果想知道为什么这个方法叫对角线方法, 可以参考原教材.

图灵停机问题$\mathsf{HALT}$就是要我们判定一个图灵在给定输入下是否能在有限步骤内停机. 其形式化描述如下
$$
\mathsf{HALT}(x,\alpha)=1\iff M_\alpha(x) \text{ halts in finite steps }
$$
我们将通过归约的方法来证明这个问题不能被一台图灵机解决. 我们的思路是用一台图灵机$\mathsf{UC}$问题转换为$\mathsf{HALT}$问题, 那么如果$\mathsf{HALT}$问题可以被一台图灵机解决, 则$\mathsf{UC}$问题也可以被一台图灵机先转化为$\mathsf{HALT}$问题再解决, 这就违背了$\mathsf{UC}$问题不可解的前提, 也就是说我们的假设不成立, $\mathsf{HALT}$问题不能被一台图灵机解决.

假设有一台图灵机$M_\mathsf{HALT}$能够解决$\mathsf{HALT}$, 那么我们尝试就用他来结局$\mathsf{UC}$. 构造图灵机$M_\mathsf{UC}$用于计算$\mathsf{UC}$.

$M_\mathsf{UC}(\alpha)$的计算如下:

$M_\mathsf{UC}$首先调用$M_\mathsf{HALT}(\alpha, \alpha)$, 如果他输出0, 则$M_\mathsf{UC}(\alpha)=1$. 否则, $M_\mathsf{UC}$使用通用图灵机$\mathcal U$来模拟计算$b=M_\alpha(\alpha)$并输出$\bar b$.

这里需要稍微说一下为什么要这么归约. 其实之所以我们不能计算$\mathsf{UC}$就是因为我们处理不了不停机的情况, 那么现在已经给出了能够处理不停机的情况的$M_\mathsf{HALT}$, 我们直接调用它就可以了, 至于其他的情况, 我们可以使用通用图灵机来模拟计算即可.

显然, 上述构造的$M_\mathsf{UC}$能够在有限步骤内计算$\mathsf{UC}$. 根据我们之前的解释, 能够在有限步骤内求解$\mathsf{UC}$的图灵机不存在.

图灵停机问题也是一样, 也许你面前的图灵机陷入了一个非常大的循环, 比如需要$10^{99}$步骤才能完成一个循环, 这个时候你根本无法判定. 即使你的寿命足够长, 判定了这个结果, 那么对于一个长达$10^{999999999999}$步的循环呢? 其实我们也没有办法解决这样的问题.

根据大量合理的计算模型构造, 最后都被证明计算能力和图灵机的计算能力等价, 我们有如下结论

丘奇-图灵论题

任何物理上可以实现的计算设施, 其计算都可以被一台图灵机模拟.

也即是说, 我们造不出来比图灵机更强的计算机. 这个论题虽然没有被证明, 但是也没有被证伪, 是计算理论的一条基本公理(或基本假设).

“语言$L$被图灵机$M$判定”, 就是说这台图灵机在接受到任何串$x$的输入时都能在有限步骤内停机, 且$M(x)=1\iff x\in L$. 换句话说, 图灵机$M$总是能在有限时间内给我们一个明确的答案$x\in L$是否成立. 实际上这个一个非常准确的术语, 因为”判定”就是”判断”, 那么必须真($x\in L$)假($x\notin L$)命题都能判断.

而”语言$L$被图灵机$M$识别”则是说, 图灵机$M$在接受到任意$x\in L\iff$M在有限步骤内停机且$M(x)=1$. 对于那些$x\notin L$的串, $M$要么拒绝它(即在有限步骤内输出$0$), 要么不会停机. 同样, “识别”这个术语也是非常精确的, 即说任何$x\in L$的串都能被$M$接受.

这是我们最先接触到的一类问题, 虽然我们不去过多研究他们.

复杂度类$\mathbf{R}$
$$
\mathbf{R}=\{L|L \text{ is turing computable}\}
$$

它表示那些能被一台图灵机判定的语言的集合. 类似地,

复杂度类$\mathbf{RE}$
$$
\mathbf{RE}=\{L|\exists M\in\mathbb M, \forall x\in L: M(x) \text{ halts in finite steps}\}
$$

表示能被一台图灵机识别的语言的集合.

由于一个语言$L$能被某台图灵机$M$判定蕴含$L$能被$M$识别, 因此我们有$\mathbf{R}\subseteq \mathbf {RE}$. 有关$\mathbf R$更多的研究, 请参阅可算理论有关的书籍和论文.

也许你曾经没有注意到, 有些问题真的很难, 因为试卷上让你求解问题真的都很简单—––我们这样说绝对没有针对你的意思, 因为我们所说困难, 不是你一个人做不出来, 而是也许所有人都做不出来. 现在, 让我们思考一下下面的问题.

在任意6个人中, 至少有3个人相互之间认识, 或者相互之间不认识.

上述命题是可以被证明的, 只是他的证明还是相对比较麻烦, 如果你没有学过这个命题, 但是有良好的数学基础, 应该能够在半个小时内证明他. 但是, 5个人可以吗? 7个人可以吗? 或者我们换一种问法: 至少需要多少个人, 才能保证其中至少3个人相互之间认识或者3个人相互之间不认识. 这个问题可以被推广, 就是判定给定$\langle t,x,y\rangle$个人, 判定, 是否$t$是满足命题”任意$t$个人中, 至少$x$个人相互之间认识, 或者$y$相互之间不认识”的最小正整数. 如果我们将人看作点, 将认识看作红边, 将不认识看作蓝边, 我们可以将问题叙述如下

求问$t$是否是满足如下命题的最小正整数: 在任意$t$个点且边被染成红色或蓝色的完全图$K_t$中, 至少存在一个红色的$x$个点的完全图$K_x$或蓝色的有$y$个点的完全图$K_y$.

你可以试试当$x,y$很大时解决这个问题有多难. 如果我们将满足命题的三元组$\langle t,x,y\rangle$看作是一个语言, 那么我们记$t=R(x,y)$. 这个问题难到, 人们到目前为止还不知道$R(5,5)$是多少.

我们以上介绍的问题中, 这些满足条件且$x=y$的数就是Ramsey数(可翻译为拉姆齐数). 这个问题可以扩展为染成$n$个颜色的版本, 使得问题更加困难. 实际上你可以发现, 当输入的规模很小的时候, 解决这个问题已经足够困难, 因此我们对问题的复杂度做划分是有意义的.

当然, 没人能说这个问题一定需要多少的步骤才能被解决, 也许有一个非常精巧的办法来解决他——这意味着这是一个相当简单的问题——这种可能是存在的. 但是, 好在我们对问题复杂度进行划分的时候, 考虑的是上界, 也就是说解决一个问题的更优算法可能被发现, 但是他不影响我们已有的对他的复杂度的断定. 例如, 复杂度类$A$是包含在复杂度类$B$中的, 我们已知有个算法使得问题$L$一定在$B$中, 但是我们某一天发现了一个算法, 使得$L$在$A$中, 那么”$L$在$B
$中”仍然是正确的.

$\mathbf{DTIME}(\cdot)$
$$
\mathbf{DTIME}(t(|x|))=\{L|\exists c\in \mathbb N,\exists M\in \mathbb M, \forall x\in\{0,1\}^\ast: x\in L\iff M(x) =1 \text{ and } M \text{ halts in } t(|x|) \text{ steps.}\}
$$

也许符号看起来有些复杂, 但是你要适应并学会翻译这种语言, 在这里, 我们用自然语言将它陈述一次. “$\forall x\in\{0,1\}^\ast: x\in L\iff M(x) =1$”很容易理解, 我们已经见过很多次了, 其实它就是说, $M$能够判定语言$L$. 前面加上”$\exists M\in \mathbb M$”, 就是说存在一台图灵机能够判定$L$. 而”$\exists c\in \mathbb N\cdots\text{ and } M \text{ halts in } t(|x|) \text{ steps.}$”则是对$M$的运行时间做了限定, 要求它必须在$t(|x|)$的某个常数倍内完成, 而”$\exists c\in \mathbb N$”写在最前边则是要求我们最先确定$c$, 一旦$c$被确定, 就不能随着$x$变化而变化, 对于任何长度的$x$, $c$都必须是同一个值.

$\mathbf P$
$$
\mathbf P = \bigcup_{i\in \mathbb N}\mathbf{DTIME}(n^i)
$$
其中$n$是输入的长度

用自然语言来说, $\mathbf P$问题就是那些能够在输入长度的多项式步骤内被一台图灵机解决的问题. 如果单从自然语言来理解, 我们会想, 我们可以构造任意大的多项式, 这样不就可以让所有在有限步骤内可解的问题都是在输入的多项式时间内可解了吗? 是的, 但是要注意的是量词出现的顺序. 我们将定义展开来解释

$\mathbf P$
$$
\mathbf P =\{L| \exists M\in\mathbb M,\exists C,c\in \mathbb N,\forall x\in L: M(x)=1\iff x\in L\wedge (M \text{ halts in } Cn^c \text{ steps})\}
$$

这个多项式的系数次数是出现在$x$之前的, 因此我们的要求是对于所有的$x$, 要有同样一个多项式来约束图灵机执行的步骤数. 实际上这就相当于是如果你宣称一个问题是$\mathbf{P}$问题, 那么你就要经得起如下考验: 首先由你给出一个多项式和一台图灵机, 然后你的对手会给出一个输入规模, 在这个输入规模下的任何输入都能使得该图灵机在这个多项式时间内正确判定该问题. 在这个考验中, 你必须要总是胜利.

$\mathbf{EXP}$
$$
\mathbf{EXP}=\bigcup_{i\in\mathbb N}\mathbf{DTIME}(2^{n^i})
$$

类似地, 还可以定义双指数时间

$\mathbf{2EXP}$
$$
\mathbf{2EXP}=\bigcup_{i\in \mathbb N}\mathbf{DTIME}(2^{2^{n^i}})
$$

实际上还可以定义$\mathbf{3EXP},\mathbf{4EXP}\cdots$ 如果定义$E_0(i)=i, E_n(i)=2^{E_{n-1}(i)}$, 那么有
$$
\mathbf{nEXP}=\bigcup_{i\in\mathbb N}\mathbf{DTIME}(2^{E_n(i)})
$$
需要这多时间的问题人类能解吗? 耍滑的回答是能, 因为$\mathbf{P}$问题也是它的子集, 至少我们能解$\mathbf P$问题….但是目前为止, 我们知道肯定有一些问题, 在$\mathbf{EXP}/\mathbf P$内, 这个结论我们稍后再证明, 我们先介绍一个假设, 说明这些问题真的很难.