Time Hierarchy Theorem

他从开阔的前额看到了智慧，从坚定的目光和微皱的眉宇间看到了勇气，在那露出两排洁白牙齿的厚厚的嘴唇上，他看到了坦诚。

要证明这个定理，实际上就要说清楚一件事：** 存在这样一个语言，把不同时间内可以判定的语言区分开。** 这也是这个定理想表达的内容。

There always exists such a language, who separates the set of languages decided in different time hierarchy.

我们以$DTIME(n^{2})\subset DTIME(n^8)$ 为例，来证明它。

• $DTIME(n^2)\subseteq DTIME(n^8)$ 是显然的。

所以我们要证明：

$$\exists L,L\in DTIME(n^8),L\notin DTIME(n^2)$$

在严格证明之前，我们需要理解编码的普适性（Universal encoding），它要求：

• 每个编码都对应一个对象。
• 每个对象都有无穷多个合法编码。

这是很容易实现的。譬如要编码一个图灵机，我们可以把所有不合法的编码都对应一个默认的图灵机，同样可以允许在合法编码最后添加任意多个 "1"。这样就满足了上述两个条件。

---

下面我们构造这样一个图灵机$D$：

• 对于一个输入$s$，把它看作是输入对$s=\langle M,w\rangle$（根据编码的普适性，这总是可以的）

• 然后模拟$M$ 在输入串$s=\langle M,w\rangle$ 上运行$n^3$ 步。其中$n=|\langle M,w\rangle|$。

• 如果在这$n^3$ 步中，$M$ Accept，则$D$ Reject，输出 0。

  如果$M$ Reject 或者未停机，则$D$ Accept，输出 1。

很显然，$D$ 永远是停机的，因为$n$ 是有限的。那么图灵机$D$ 就 decide 了一个语言:

$$L(D)=\{s\;|\;D(s)=1\}$$

下面我们考虑这个语言。首先$L(D)\in DTIME(n^8)$ 是很显然的。因为考虑图灵机$D$ 的复杂性（下面是一个非常松的估计）：

• 首先需要计算出$n$ 是多少，这只需要$O(nlogn)$ 步即可。其中$logn$ 是要把$n$ 的二进制位存储。
• 然后计算$T(n)=n^3$ 是多少。由于我们假设了$T(n)$ 是 Time-constructible 的，一个重要的要求是，计算$T(n)$ 的时间不能超过$O(T(n))$，故这一步也没有提升复杂性。
• 最后是模拟$M$ 进行$n^3$ 步，实际上 Universal Turing Machine 已经可以做到，模拟$M$ 的一步需要 UTM 进行$n^3$ 步。（一个想法就是需要扫描$\langle M,w\rangle$，然后进行操作）。详情可见：http://morphett.info/turing/turing.html?b4c28c3e136124b95266db4be07de36a

所以计算所需时间是肯定小于$O(n^8)$ 的。

---

下面是重点，我们证明$L(D)\notin DTIME(n^2)$。

反设存在这样一个图灵机$H$，它可以在$O(n^2)$ 时间内 decide $L(D)$，那么我们考虑$H$ 在输入$\langle H,0^l\rangle$ 上会怎样。

令$n=|\langle H,0^l\rangle|=c+l$，其中$c=|\langle M\rangle|$。

因为$H$ decide $L(D)$，故$H$ 应该和$D$ decide 相同的语言，即$H(\langle H,0^l\rangle)=D(\langle H,0^l\rangle)$。

又由于我们构造$D$ 时，要求了，如果$H$ 在$n^3$ 步内停机的话，会有$D(\langle H,0^l\rangle)=\neg H(\langle H,0^l\rangle)$。

因为根据假设，$H$ 在$O(n^2)$ 步内就可以 decide 了，故可以取$l$ 足够大，使得$n^3>H$ decide $L(D)$ 的上限时间$=O(n^2)$，此时$H$ 一定会在$n^3$ 步内停机。故有：

$$H(\langle H,0^l\rangle)=D(\langle H,0^l\rangle)=\neg H(\langle H,0^l\rangle)$$

此时得出矛盾，得证。

---

Remark：注意，一切试图去 decide $L(D)$ 的图灵机都不可能在$O(n^2)$ 内输出正确的结果。

就像下面这个函数：

$UC(s)=$

• 把$s$ 看作是一个图灵机编码，即$s=\langle M\rangle$。
• 然后考虑$M$ 在输入$s=\langle M\rangle$ 上的行为，如果$M$ accept，则$UC(s)=0$。
• 否则若$M$ reject 或者不停机，那么$UC(s)=1$。

$UC$ 就是一个不可计算函数。任何尝试去计算$UC$ 的图灵机，都会存在一个输入，使得图灵机在该输入上死循环不停机，或者输出错误结果。