AIT 中的几个有趣问题：从一些不可计算数到算法演化的动力学

先定义这么一些东西：

当前语言由 n 个字符构成。
定义 T(L) 为所有长度不超过 L 且能停机的图灵机构成的集合。
定义 S(t) 为图灵机 t 到停机所要执行的步骤数，如果不停机则该值为正无穷。
定义 S(L) 为 $S(L) = \max \{ S(t) | t \in T(L) \}$ ，即表示 T(L) 中所有图灵机要执行的步骤数的最大值。

由此可知，T(L) 中图灵机的数量有不等式： $|T(L)| \leq \sum_{i=1}^L n^i = \frac{n \left( n^L - 1 \right)}{n - 1}$ 。

另一方面，函数 S(t) 与 S(L) 都是不可计算的，这点很容易证明：

假定 S(t) 是可计算的，那么我们可以构造如下程序：

paradox := (t) =>
    i := 0
    while i <= S(t)
        i ++
    return

很显然，paradox(paradox) 是一个矛盾，因为对于程序 paradox 的任意输入程序 t，它都会在执行 $S(t) + 1$ 步后停机，因此 paradox(paradox) 会在执行 $S(paradox) + 1$ 步后停止。但 $S(paradox)$ 本就是程序 paradox 执行步骤，从而构成矛盾 $S(paradox) = S(paradox) + 1$ 。

同理，构造如下程序：

canStop := (t) =>
    l := S(t.length)
    for i := 0; i < l; i ++
        stop := doStep(t)
        if stop
            return true
    return false

这就构成了一个停机判定函数，因为对于任意输入的程序 t，都可以通过 t 自身的长度 l 来利用程序 S 获得长度不超过 l 的可停机图灵机的最大执行步骤 S(l)，那么如果在 S(l) 步内都没停机的话，就肯定不会停机了。

但我们知道，停机判定函数是不可计算的，因此 S(L) 必然也是不可计算的，从而上述程序无法在图灵机体系内被表达出来。

非但如此，我们由此也可以证明， $S(L)$ 的上界，也是不可计算的，这点很显然。

但，我们可以构造一个有意思的程序：

canStopInStep := (t, s) =>
    for i := 0; i < s; i ++
        stop := doStep(t)
        if stop
            return true
    return false

这个程序的作用，是判断程序 t 在 s 步内是否会停机，但即便在 s 步内不会停机，我们也不能说 t 就不会停机。我们将这个程序记为符号 $S(t,s)$ ，因此停机判定函数可以形式地记为 $S(t, \infty)$ 。

下面来看另一个问题，就是我们能否确定 $S(L)$ 的下界？虽然它本身及它的上界都是不可计算的，但我们能否推算出它的下界呢？

可以构造如下程序：

loop := (s) =>
    i := 0
    while i <= s
        i ++
    return

这个程序的作用很明显，就是在执行 s + 1 步后停机。下面，我们如果通过图灵机之外的手段计算出了长度不超过 L 的可停机图灵机的最大执行次数 $s = S(L)$ 的话，将其输入到程序 loop 中，自然会在执行 $S(L) + 1$ 步后停机了，那么此时这个程序自己长多少呢？

loop(s) 的长度为 $l = c + \log_n s$ ，其中 n 是程序所选语言的字母表中用于表示数字的符号数，c 是与 s 无关而只与所选语言相关的常数。从而如果 $l \le L$ ，则会出现矛盾，因为此时这个程序本身需要执行的步骤数应该不大于 L，但这个步骤数为 L + 1，从而是矛盾的，由此可知，唯一的可能就是 $c + \log_n s > L$ 。

事实上，我们可以将上述程序中的外源常数 s 替换为能生成 s 的最短程序，那么此时就有不等式：

$\begin{cases} c + K(S(L)) > L\\ K(s) \le \log_n s \end{cases}$

其中第二个不等式是由于数字 s 至少可以表达为在 loop 程序中直接写 s，而这么做的长度为 $\log_n s$ 。

我们不妨将 K 氏复杂度写为 $K(S(L)) = \log_n (S(L) - \delta(L))$ ，且 $\delta(L) \ge 0$ ，从而可得：

$S(L) > n^{L - c} + \delta(L) \ge n^{L - c}$

由此我们可以得到 S(L) 的下界——当然，实际上的 S(L) 可以比这个下界大很多。

现在我们换一个角度来看这个问题，有没有可能把这个下界进一步往上推？比如下面这段程序：

loop := () =>
    s := generate()
    i := 0
    while i <= s
        i ++
    return

其中程序 generate 可以生成自然数。而这段那程序的执行步骤数为 s = generate() + 1。假定这段程序的长度是 L，那么存在只与语言相关的常数 c，使得 generate 程序的长度为 L - c，从而我们有不等式 $S(L) \ge s$ 。

也就是说，对于长度不超过 L 的图灵机能生成的最大自然数 $N(L)$ 与长度不超过 L 的可停机图灵机的最大执行步骤数 $S(L)$ 之间存在如下关系：

$S(L) \ge N(L - c)$

长度为 L 的图灵机能生成的最大自然数，最少也是直接用所有 L 位都来表达数字所得的自然数，所以有：

$S(L) \ge N(L - c) \ge n^{L - c}$

因此， $N(L - c)$ 是比 $n^{L - c}$ 更大的下界。

那，这个数可以有多大呢？这取决于语言中允许的数学运算算符有哪些，当然更重要的是我们如何写生成程序（循环和递归可以产生很大的数，只要写得好）。

比如说，加法运算中，生成结果的算式的总长度总是大于最终结果的；而在乘法运算中，算式长度等于结果加上乘法数量；幂次运算可以大幅减少算式长度，如果只是高阶幂次的话，就可以用少量算式得到更大的数值。比如下面这种情况：

$a \land_1 b = \underbrace{a \times a ... \times a}_b\\ a \land_{n+1} b = \underbrace{a \land_n a ... \land_n a}_b$

这里的运算是从右往左。

如果一门语言支持上述这种三目运算 $f(a,b,c) = a \land_c b$ ，则如下程序可以输出极大值：

generate := () =>
    return f(N, N, N)

当然，这还不是能构造的最大输出结果，随着 L 的增加，可以有更复杂的形式，输出更大的结果。

回到之前的结果，最大执行步骤数比程序能表达的最大自然数还要大，这点也从侧面说明了这个最大执行步骤数是不可计算的。

而这点从另一面反应出，当 L 趋向无穷时，T(L) 中的图灵机会以图灵机无法计算的方式更快地趋向无穷。换言之，我们无法使用任何图灵机来给出一个完备的计算，其中包含所有 L 趋向无穷时能停机的图灵机。

也就是说：

如果用 $T(L;f(L))$ 来表示所有长度不超过 L、计算次数不超过 f(L) 步便停机的图灵机的集合，则当 L 趋向无穷时，这个集合无法通过图灵机来获得。

故而，所有基于 $T(L;f(L))$ 集的计算，要么是不完备的（即不可能遍历这个集合的所有元素），要么是图灵机无法实现的。

接下来，再看一个问题：长度不超过 L 的图灵机，执行 T 步时正好停机的图灵机的数量记为 $Q(L,T)$ ，则 Q 是否是可计算的？

若 $Q(L, T)$ 可计算，则我们可以构造如下一段程序：

Qs := (T, s) =>
    i := 0
    while (i < T)
        s += s
    return s
q := Q(Qs.length + c, T)
for s := anyStringWithLength(log(q + 1, n))
    temp := T => Qs(T, s)

这段程序很有意思，其中 c 是一个常数，它存在一个特殊的不等式（其中 L = Qs.length）：

$L + c > L + \log_n \log_n [Q(L + c, T)] + \log_n T + e$

其中 e 是一个只与语言本身有关的常数。这里不等式左侧源自 Q 的定义所要求的“长度不超过 L”，而右侧是程序 temp 的长度，其中第二项源自输入的参数 s。

如果该不等式满足，则可以构造出这么一个矛盾：此时 for 循环中的每个 temp 函数都是长度不超过 L + c 且都执行 T 步就会停机的程序，而这样的程序总共至少有 q + 1 个，其中 q 是目标 Q 程序计算出来的这样的程序的数量上限，因此就存在矛盾。

也就是说，只要能找到 c 让上述不等式成立，则 $Q(L, T)$ 就必然是不可计算的因为能构造出矛盾。

而我们又知道， $Q(L, T)$ 存在一个天然上限，那就是 L 个字符能构成的所有可能图灵机的总量 $n^L$ ，因此我们有：

$\log_n \log_n Q(L + c, T) < \log_n \log_n n^{L + c} = \log_n (L + c)\\ \therefore \log_n [T(L + c)] < c - e$

由于 L 和 e 在这里都是确定的常数，而当 c = 0 时该不等式不成立，同时右侧的增涨速度在 c 大于 1 后必然大于左侧，所以只要 c 足够大右侧必然会超过左侧使得不等式成立，所以总能找到 c 使得这个不等式成立。

因此，这就证明了， $Q(L, T)$ 是不可计算的。

这点其实也很自然，因为 $Q(\infty, \infty)$ 可以给出 Chaitin 常数，而后者是不可计算的。

而且，非但 $Q(L, T)$ 是不可计算的，它的任何小于自然上界的上界函数也是不可计算的。

虽然 $Q(L, T)$ 是不可计算的，但我们依然可以设法找出它的下界。

把上面那段程序略作修改：

Qs := (L, T, s) =>
    i := 0
    while (i < T)
        s += s
    return s

对于这个函数，我们可以输入任意足够大的 L 与任意 T，而 s 是任意字符串，满足下面的关系即可（取 $q = len(Qs)$ ）：

$len(s) = L - \log_n L - \log_n T - q$

接着，如果我们将 L 和 s 这两个输入参数作为程序中的常数，而 T 作为输入用来给出输出，那么这样的程序满足长度为 L 与执行步骤为 T 这两个要求，而这样的程序本身随着输入 s 的不同而不同，所以总共有 $\frac{n^{L - q}}{LT}$ 个。

因此，我们有：

$\begin{cases} Q(L, T) > \sum_{l = L_0 + 1}^L \frac{n^{l - q}}{l T}\\ L_0 - \log_n (L_0 T) - q = 0 \end{cases}$

事实上，这个结果可以进一步提升为（从而从可计算变成了不可计算）：

$\begin{cases} Q(L, T) > \sum_{l = 1}^L sig(l, T) n^{l - q - K(l) - K(T)}\\ sig(l, T) = \begin{cases} 1 \ \ \ \ \ \ \ l - q - K(l) - K(T) > 0\\ 0 \ \ \ \ \ \ \ l - q - K(l) - K(T) \le 0 \end{cases} \end{cases}$

这里函数 $K(x)$ 表示要生成数值 x 所需的最短程序的长度，包括直接外部输入 x 这一方式在内，从而它和 x 的 K 氏复杂度其实是一回事，只不过专注于输出 x 为自然数的情况。

接着，由于 Chaitin 不完备定理：

存在一个足够大的自然数 n，使得我们无法在一个足够强的形式系统中构造性地证明“存在 s 使得 K(s) > n 成立”这条命题。

我们可以得到一条等价的不完备定理：

存在足够小的自然数 q，使得我们无法在一个足够强的形式系统中构造性地证明“当 L 足够大时，存在 T 使得 $0 < Q(L,T) < q$ 成立”这条命题。

这个证明很简单。假定这条命题可证，则我们实际上便证明了某个 T 使得 Q 的下界小于足够小的 q。而，我们知道 $K(T) \ge \log_n T$ ，因此有：

$Q(L, T) > \sum_{l = L_0 + 1}^L \frac{n^{l - q}}{l T}\phantom{wwwwwwwwwwwwwwi}\\ = \sum_{l = L_0 + 1}^L n^{l - q - \log_n (lT)}\phantom{wwwwww}\\ \ge \sum_{l = L_0 + 1}^L \left( n^{l - \log_n l} \times n^{-K(T) - q} \right)\\ = n^{-K(T) - q} \sum_{l = L_0 + 1}^L n^{l - \log_n l}\phantom{wwa}\\ \ge (L - L_0) n^{-K(T) - q}\phantom{wwwwwa}$

由 Chaitin 不完备定理可知，我们无法证明对一个足够大的 m，能找到某个 T 满足 $K(T) > m$ ，这就是说，我们无法证明对于一个足够小的 M，某个 T 使得 $n^{-K(T)} < M$ 成立。由于 L 和 q 都是有限的，而对于任意有限的 T，对应的 $L_0$ 也都必然是一个有限值，且只要 L 足够大则 $L - L_0$ 必然大于 0，所以这就等于说，我们无法证明对于一个足够小的 m，能找到某个 T 使得 Q 小于 m ——否则我们实际上就能证明 Q 的上述下界小于 m，从而证明 Chaintin 不完备定理已经证明了的我们不能构造性地证明的 $K(T) > m$ 了。

更进一步，这条不完备性定理其实是说，当 L 足够大时，对于任意 T 我们只能证明 T(L,T) 要么是 0 要么不是，但无法证明它小于某个大于 0 的值。

我们还可以进一步得到如下这条不完备定理：

在一个足够强的形式系统中，我们无法构造性地证明存在一个极限执行次数 T，使得所有执行次数超过 T 的图灵机的数量少于足够小的自然数 q 的。

这是因为，如果这个定理不成立，则我们可以证明执行次数超过 T 的图灵机的数量足够少，假定这个足够少的数量是 M，即 $\sum_{t > T} Q(L, t) < M$ 。

那么，由于 Q 至少不小于 0，这就表示 $Q(L, T + 1) < M$ 。而我们知道，对于足够小的 m 我们无法构造性地证明存在 T 使这个不等式成立，从而证明了不存在这样一个 T，容许我们构造性地证明执行次数超过 T 的图灵机的数量是足够少的。

这里岔开一下，说一下 Chaitin 不完备定理。

对于任意给定自然数 n，事实上我们可以证明必然存在某个字符串 s 使 $K(S) > n$ ，因为如果不存在这样的 s，那就表示我们可以用最多 $\frac{d}{d - 1}\left( d^n - 1 \right)$ 个字符串（这里 d 表示字符集字符数）来生成所有可能出现的无穷多的字符串，这显然是不合理的。

但 Chaintin 不完备定理则告诉我们另一件事：当 n 足够大时（且 n 只与所选语言有关，是一个语言的常数），我们无法在一个足够强的形式系统中形式化地找出这样一个 s 来满足上面这个不等式。

换言之，对于足够大的 n（且 n 是只与语言有关的常数），所有我们可以构造出来的字符串 s 都无法满足 $K(s) > n$ 。

这里的关键就是“构造性”这个限定，即我们可以证明 s 的存在，但永远找不到这样一个 s。

让我们来看一下这个颇神奇的类似 Berry 悖论的 Chaitin 不完备性的证明过程。

我们可以通过哥德尔编码在自然数与形式证明过程之间建立对应，同时我们又总可以验证给定的形式证明过程是否证明了上述不等式。现，假定程序 process(i) 将自然数 i 映射为形式证明过程 p，available(p,n) 验证形式证明过程 p 是否是关于上述不等式的有效验证过程，proof(p,n) 则判断形式证明过程 p 是否证明了某个字符串 s 的 K 氏复杂度大于自然数 n，最后程序 string(p) 则是将证明过程 p 中证明的字符串 s 提取出来。

接着，我们可以构造如下程序：

find := n =>
    i := 0
    while
        i++
        p := process(i)
        if available(p,n) and proof(p,n)
            return string(p)

显然，find 程序的作用，就是遍历所有可能自然数，找出其中关于上述不等式的形式证明，并且当该形式证明证明该不等式成立时，返回这个形式证明过程中用到的字符串 s。

也就是说，这个程序的作用，就是遍历所有形式证明，然后返回被证明 K 氏复杂度大于 n 的字符串 s。

接着，这个程序多长？其中输入参数 n 之外的部分的长度假定为 P，而输入参数 n 的长度为 $\log_d n$ ，因此这个程序的总长度为 $P + \log_d n$ 。

有趣的地方来了——它本身也可以返回字符串 s，且该字符串被证明 K(s) > n，但生成 s 的这段程序本身的长度为 $P + \log_d n$ ，且根据 K 氏复杂度的定义我们有 $K(s) < P + \log_d n$ ，而很显然，总存在 n 使得 $P + \log_d n < n$ ，这里就出现了矛盾。

因此，这就表示说，要么不存在这样的证明也即该命题不可证，要么这个证明过程中没有构造性地给出字符串 s。前者表示 if 判断的第二个条件永远无法满足，所以程序不停机，故而无输出；后者则表示形式证明 p 虽然证明了 s 的存在，但并没有构造出这样的 s，所以 string(p) 无输出。

当然，还有另一种可能，就是 available(p,n) 永远不返回 true，即我们要么永远无法判断一个证明过程是否是关于上述不等式的，要么就是不存在这样的证明。或者就是这个程序并不存在。

事实上，由此就可以证明，不存在证明某个 s 满足上述不等式的证明，因为只要存在这样的证明，就可以被上面构造的悖论函数枚举出来，从而构造出悖论。

现在回到函数 $Q(L,T)$ 上来。

对于前面提到的下界函数 $Q(L, T) > \frac{1}{T n^q} \sum_{l = L_0 + 1}^L \frac{n^l}{l}$ ，显然当 $T \ge n^{L - q}$ 时该下界为 0，但在这个极限 T 之前，当 L 足够大且 n 至少为 2 的情况下，则有：

$Q(L,T) > \left( L - \frac{1}{L} - q - \log_n T \right) + \frac{n^{L - q}}{L T}$

这个下界很有意思，因为这就表示，当 L 趋向无穷时，执行不超过任意有限 T 步便可停机的图灵机的总数，占所有可停机图灵机的比重会趋向于 0。

也就是说，从全局看，执行有限步就停机的图灵机永远是稀疏的。

使用 $Q(L, T)$ 函数我们可以估算 Chaitin 常数的下限（ $N = \frac{n (n^L - 1)}{n - 1}$ 为长度不超过 L 的图灵机的总数）：

$C(L) = \frac{1}{N} \sum_{T=1}^\infty Q(L, T) > \frac{1}{N} \sum_{T=1}^{T_M} \left[ \left( L - \frac{1}{L} - q - \log_n T \right) + \frac{n^{L - q}}{L T} \right]\\ = \frac{T_M}{N} \left( L - \frac{1}{L} - q \right) - \frac{1}{N} \sum_{T=1}^{T_M} \log_n T + \frac{n^{L - q}}{L N} \sum_{T=1}^{T_M} \frac{1}{T}\ \ \ \ \ \ \\ \ge \frac{T_M}{N} \left( L - \frac{1}{L} - q \right) - \frac{\log_n (T_M !)}{N} + \frac{n^{L - q} \log_n T_M}{L N}\ \ \ \ \ \ \$

而由于 $T_M = n^{L - q}$ ，再利用斯特灵公式可得：

$C(L) > \frac{n^{L - q} (n - 1)}{n (n^L - 1)} \left[ 1 + \frac{1}{\ln n} - \frac{q + 1}{L} - \frac{L - q + \log_n (2 \pi)}{2 n^{L - q}} \right]$

也就是说，在长度不超过 L 的所有图灵机中，随便一个图灵机会停机的概率（L 阶 Chaitin 常数）下限可以通过语言相关的常数 n 和 q 决定，也由此可以得出 Chaitin 常数的下限为：

$C_{\min} = \frac{n - 1}{n^{q + 1}} \left( 1 + \frac{1}{\ln n} \right)$

当然，这个值非常非常小，比如以 ASCII 码来编写的话，n = 128，q 则差不多为 40，所以这个值小得可以忽略，从而从侧面作证了可停机图灵机有多稀疏。

有人估算 Chaitin 常数差不多是 0.007875，比这里计算的下限大了很多，由此可见这里计算的 Q 的下限果然比实际的 Q 小了很多。

我们可以取 $C(L,T)$ 为所有长度不超过 L、执行步骤不超过 T 便能停机的图灵机在所有长度不超过 L 的图灵机中的比例，则有如下下界（取 $M(T) = \min (T, n^{L - q})$ ）：

$C(L,T) = \frac{1}{N} \sum_{t=1}^{M(T)} Q(L, t)\phantom{wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww}\\ \ge \frac{M(T)}{N} \left( L - \frac{1}{L} - q \right) - \frac{\log_n [M(T) !]}{N} + \frac{n^{L - q}\log_n M(T)}{L N}\phantom{wwwwwwwwwwwwi}\\ \approx \left[ L - q - \frac{1}{L} + \frac{1}{\ln n} - \log_n M(T) \right] \frac{M(T)}{N} + \frac{n^{L - q} \log_n M(T)}{L N} - \frac{\log_n [2 \pi M(T)]}{2 N}$

当 L 很大时，这个下限可以写为：

$C(L, T) \approx \left( L - \log_n T \right) \frac{T}{n^L} + \frac{\log_n T}{L}$

这就表示，当 L 足够大时，不那么大的 T 所对应的执行次数不超过它便停机的图灵机的数量的占比，几乎为 0。

或者，更进一步说，就是在“所有图灵机”这个集合中，对于任意有限次执行后便能停机的图灵机数量的占比，几乎为 0。

而，由于 Q 本质上是不可计算的，Q 的上限也是不可计算的，所以我们无法通过任何遍历可枚举语言告诉图灵机随着 L 的增长，T 的上限应该怎么取，才能使得不大于 T(L) 的可停机图灵机的总数能不“几乎为零”。

还有一些很有趣的问题，涉及到一些很有趣的 AIT 函数。

比如，令 $k(s)$ 代表字符串 s 是否可压缩的函数，即：

$k(s) = \begin{cases} 1\ \ \ \ \ \ \ \ K(s) < |s|\\ 0\ \ \ \ \ \ \ \ K(s) \ge |s| \end{cases}$

以及，将字符串根据其哥德尔数进行排序，函数 $c(n)$ 代表不大于 n 的自然数通过哥德尔解码所得的字符串中能被压缩的字符串的数量，而用 $C(l)$ 代表长度不超过 l 的所有字符串中能被压缩的字符串的数量。

这两个函数是否可计算呢？

让我们先来看“压缩判定函数” $k(s)$ 。我们可以构造如下程序：

find := () =>
    i := 0
    while
        i ++
        s := string(i)
        if !k(s) and s.length > c
            return s

其中参数 c 是程序 find 的长度。因此，如果压缩判定函数存在且可计算，则上述程序会找出第一个被判定为不可压缩且长度大于这段程序长度的字符串，并返回——这样就构成了矛盾，这个程序可以生成该字符串，而生成的条件是这个字符串不可压缩且长度大于这段程序，因此这段生成该字符串的程序本身就是这段程序的一个压缩，从而构成矛盾。

这就是说，我们非但无法通用地计算一个字符串的不可压缩长度，而且甚至无法通用地判断该字符串是否可压缩。

因此，也就很容易证明， $c(n)$ 也是不可计算的，因为如果它是可计算的，我们便可以利用哥德尔编解码与 $c(n)$ 函数来构造出压缩判定函数 $k(s)$ ，而后者已经被证明是不可计算的了，所以 $c(n)$ 也只能是不可计算的。

下面就是那个有趣的问题：长度不超过 L 的字符串中，可压缩的字符串的数量 $C(L)$ 是多少？

我们可以先来算一下它的上限——当然，它当然不会大于 $\sum_{i=1}^L n^i = \frac{n (n^L - 1)}{n - 1}$ ，这是长度不超过 L 的所有字符串的数量。

在最好情况下，我们可以这么来想：每个长度不足 L 的字符串，都是更长字符串的不可压缩表示。我们甚至认为如果一个字符串 A 可以用另一个字符串 B 生成（即 B 作为程序运行，生成结果为 A），那么 B 的不可压缩表示也可以是 A 的表示，即此时允许两个字符串有一个共同的不可压缩表示。

在这个情况下，那么最优情况下，长度为 L 的所有字符串中，可以被压缩的字符串的数量上限为 $\frac{n^L - n}{n - 1}$ 。因此，长度不超过 L 的所有字符串中，可以被压缩的字符串的一个很自然的上限就是：

$C_{\max}(L) = \sum_{i=1}^L \frac{n^i - n}{n - 1} = \frac{n (n^L - 1)}{(n - 1)^2} - \frac{L n }{n - 1}$

如果考虑到程序表达一个字符串至少需要一个函数前缀与后缀，将这两个的总长度记为 q，则有：

$C_{\max}(L) = \frac{n (n^{L - q} - 1)}{(n - 1)^2} - \frac{(L - q) n }{n - 1}$

所以，当 L 很大时，长度不超过 L 的字符串可以被压缩的概率上限约为：

$P_{\max}(L \gg 1) \approx \frac{1}{(n - 1) n^q}$

实际情况中，压缩概率当然是远小于这个上限的。

这个值还有很多别的估算方法。

比如说，上面所计算的，是每个长度不足 L 的字符串都可以对应到图灵机，从而生成一个长度为 L 的字符串，且该字符串还可以被作为图灵机继续生成字符串。

但图灵机生成的结果依然是图灵机的概率，是很低的，更不说生成图灵机的图灵机了。所以，我们可以近似地用 Chaitin 常数来对上限进行下调：

$C_{\max} (L) = \frac{n C}{n + C} \left[ \frac{n^{L - q} - 1}{n - 1} - \frac{1 - (-C)^{L - q}}{1 + C} \right]\phantom{wwwww}\\ \approx \frac{n C}{n - 1} \left( n^{L - q - 1} - 1 + C - n^{L - q - 2} C \right)\\ \approx \frac{C (n - C)}{n - 1} n^{L - q - 1}\phantom{wwwwwwwwwwwi}$

这里第二步的近似是因为 C 已知非常小，第三步的近似是考虑 L 很大的情况。

相应的，此时压缩概率为：

$P_{\max} (L) = \frac{(n - 1) C}{(n + C) (n^L - 1)} \left[ \frac{n^{L - q} - 1}{n - 1} - \frac{1 - (-C)^{L - q}}{1 + C} \right]\\ \approx \frac{C}{n^L - 1} \left( n^{L - q - 1} - 1 + C - n^{L - q - 2} C \right)\\ \approx \frac{C (n - C)}{n^{q + 2}}\phantom{wwwwwwwwwwwwwwwwi}$

由此我们可以看到，任意一段字符串可以被压缩的概率的上限，比这段字符串对应的图灵机可以停机的概率小很多。

下面取一个有趣的比值——

将上面计算的长度不超过 L、执行次数不超过 T 即停机的图灵机数量的数量比例下限 $C(L,T)$ ，与这里求的压缩概率上限 $P(L)$ 的比 $X(L,T) = \frac{C(L,T)}{P(L)}$ ，其在 L 趋向无穷大、n 也远大于 1 时的下限为：

$X(L,T) > \left[ L - q - \log_n M(T) \right] \frac{n^{q + 1} M(T)}{C n^L} + \frac{n \log_n M(T)}{C L}$

接着，我们取 $T = n^{f(L)}$ ，则有：

$P(L,T) > \frac{n}{C} \left\{ \left[ L - q - f(L) \right] n^{f(L) - L + q} + \frac{f(L)}{L} \right\}$

这便是说，该下限严重依赖于 T 随 L 增大的方式，尤其与“长度不大于 L 的图灵机能表达的最大自然数”这一一个不可计算数密切相关，因为这里我们取的是它的下限 $n^{L - q}$ 来作下限计算的。

这也就从侧面说明了，对于这类涉及到 L 趋向无穷时、长度不超过 L 的图灵机所构成的集合这一对象的计算，其结果在很大程度上都与相关量在 L 趋向无穷时的行为相关。

当然，上面的结果其实只是在重复这么一个事实：在所有可以写出的图灵机中，能停机的图灵机是非常稀少的，能被压缩的更加稀少，且绝大多数可停机图灵机都会需要在执行不可计算多步后才能停机。

我们真正感兴趣的，是所有图灵机这个集合本身所具有的一些特殊结构，尤其是在图灵机本身足够大的情况下，是否存在一些特殊的结构——当然，这些结构显然都是不可计算的。

所以，这一目标类似于在使用没有调焦的显微镜查看被一团迷雾包裹的培养皿，并试图画出其中细菌组成的纹路结构。

尤其是，上面构造的许多悖论式的程序来论证某些数是不可能通过图灵机计算得到的，这些悖论式结构本身有种“车轱辘话”的感觉，我们如果采用多值逻辑，或者引入别的数学结构，很可能会得到不同的东西。

下面我们来尝试构造一下遍历可枚举语言中更有趣的一些结构。

这里，我们将图灵机及输入参数合在一起构成一个字符串，比如如下这样：

((a, b) => {
    dosomething....
    return result;
})(123, 456);

这样，当选择要一种遍历可枚举语言或者说一种通用图灵机后，就可以将其中的所有程序与字符串等同。我们称字符串 A “描述”了图灵机 T，如果字符串 A 可以对应到上述程序加输入参数的形式。如果 A 描述了 T，则反过来称 T “实现”了 A。

进一步，如果 T 最终可以以接受状态停机，则称 T 是一台“良性图灵机”，对应的 A 称为“良性字符串”。

作为字符串，可以自然构造任意两个有限长字符串 A 和 B 之间的“距离”：

定义操作 $O(s)$ 为对字符串 s 进行下列四个操作中的任意一种：

在任意位置增加一个任意字符，记为 $add(s,n,x)$ ，即在 s 的 n 位插入 x；
删除任意位置上的一个字符，记为 $sub(s,n)$ ，即将 s 的第 n 位删除；
改变任意位置上的一个字符为一个不同的字符，记为 $mod(s,n,x)$ ；
调换任意位置上相邻两个字符的顺序，记为 $rep(s,n)$ 。

因此，如果 $B = O^n(A)$ 即对字符串 A 进行 n 次 O 操作后得到字符串 B，则这样 n 个操作构成了一条从 A 到 B 的“路径”，该路径长度为 n。

于是，我们定义定义：从 A 到 B 的所有路径的最短长度，为 A 到 B 的距离，记为 $<A,B>$ 。

容易证明，上述定义的距离是对称的，任意两个不同有限长字符串之间如上定义的距离总是一个自然数，且满足三角不等式。

然后，上述字符操作总是可以通过图灵机实现的，因此每条从 A 到 B 的路径 P 都对应一组图灵机，之所以是一组而非一个，是因为即便是确定的操作也可以有大量不同的写法，所以一条路径对应的往往不是一台而是一组图灵机，记为 $T_P$ 。

所以，从 A 到 B 的所有路径构成的集合 $P(A,B)$ 对应的就是一大组彼此不同的图灵机，记为 $T_P(A,B)$ 。

接着，如果字符串都可以当作图灵机（及输入参数），所以如果字符串 A 是良性的，那么它自然会生成一个字符串，我们可以记 $A_0 = A$ 、 $A_1 = A_0()$ ，并且可以递归地定义 $A_{n+1} = A_n()$ ，只要 $A_n$ 是良性的。但需要注意，如果存在两个不同的自然数 i < j 使得 $A_j = A_i$ 成立，那么我们可以认为这个递归链条到 j-1 结束，并没有新的 $A_j$ 被生成。

特别，如果 $A_n() = B$ ，则记为 $A \Rightarrow^n B$ ，即表示 A 可以“直接生成” B。

很显然，对任意 B，这样的 A 都只是少数。

因此，与之前定义的字符操作是对称的、完全的（即对任意两个字符串总有字符操作可以从一个变成另一个）不同，这里定义的生成关系是单向的、不完全的。

因此可以构造一个集合：

$S(s) = \left\{ t | \exists n \in \mathbb{N} : t \Rightarrow^n s \right\}$

它包含了所有能生成目标字符串 s 的良性字符串。

由于字符串本身也可以作为参数输入到图灵机中，因此就存在这样的情况：

字符串 A 通过字符操作得到了良性字符串 C，C 又生成了目标字符串 B。

或者，良性字符串 A 生成了字符串 C，而后字符串 C 通过字符操作得到良性字符串 D，D 最终又生成了目标字符串 B。

又或者，字符串 A 通过字符操作得到良性字符串 C，C 生成了字符串 D，D又经过字符操作得到了良心字符串E，最终 E 生成了 B。

等等等等。

而每一步种这样的操作，本质上都可以用图灵机来表达，而每个这样的图灵机都对应一个字符串，而由于字操作可以有可数无穷种（对任意初始字符串与目标字符串），由此可见， $G(s)$ 本身必然是一个可数无穷集。

为了表达这个集合，我们先来定义以下两个程序的“并”：

$(A \oplus B)(s) = A(B(s))$

或者简单记为 $A \oplus B$ 。

显然，四类字符操作程序的有限次并必然是 $T_P(A,B)$ 的元素，但反过来不一定成立，因为可以有更丰富但作用相同的写法。

而对程序进行“拆分”则是一件很复杂的事。

如果程序中存在一部分内容满足：

这部分程序内容会且只会被执行一次；
它能生成一组中间结果，会被后续程序内容使用；
它生成的中间结果依赖于部分或全部输入参数；
它生成的其它中间结果在此后都不再被使用；
它需要用到的程序内变量在程序的其它部分不被使用。

这样，我们便可以认为这个程序 T 是可以被拆分的，即存在两个程序 A 与 B 使 $T = A \oplus B$ 。

不考虑输入参数的长度的情况下，若 $T = A \oplus B$ 则 $|T| = |A| + |B| - c$ ，其中 c 是一个只与语言相关的常数，表示定义一个程序所要的字符数。

下面，我们考虑一类特殊的良性程序（即良性图灵机），它们需要输入参数，但其输出结果却又与输入参数无关，这样的程序被称为“常映射程序”，其全体构成的集合记为 $\Phi$ 。良性程序的全体构成的集合记为 $\Omega$ ，所以 $\Sigma = \Omega \cap \bar \Phi$ 就表示所有非常非恒等映射的良性程序，它们总能运行结束并输出结果，且输出与输入相关但不同。

需要注意的是，那些不需要输入就能输出的程序，并不是常映射程序。

如果一个程序 T 可以将输入参数 A 经过有限次操作后输出字符串 B，则记为 $A \Rightarrow_T B$ 。因此，存在一类特殊的程序： $\left\{ T | s \Rightarrow_T s \right\}$ ，它们构成了字符串 s 的一个不变映射集，记为 $\Lambda(s)$ 。

现在，我们构造这样一个集合：

$G(A,B) = \left\{ T | A \Rightarrow_T B \land T \in \Sigma \land T \notin \Lambda(A) \land T \notin \Lambda(B) \right\}$

它代表所有可以从字符串 A 生成目标字符串 B 的非常映射良性程序的总和。显然， $T_P(A,B) \cap \Sigma \subset G(A,B)$ 。

特别地，我们将从空字符串 $\phi$ 生成目标字符串 s 的情况记为 $G(s) = G(\phi, s)$ ，很显然 $S(s) \cap \Sigma \subset G(s)$ 。

假定 $T \in G(A,B)$ ，则显然代表 T 与输入参数 A 的字符串 X 是可以直接生成目标字符串 B 的，从而 $X \in G(B)$ 。

我们将 $G(A,B)$ 称为从 A 到 B 的生成集。

由于程序可以并，所以我们可以构造在程序并这一映射关系下的两个生成集的“并”：

$G(A,B) \oplus G(B,C) = \left\{ T \oplus R | T \in G(A,B) \land R \in G(B,C) \right\}$

又由于有程序可以拆分而有的程序不可以，所以对于 $G(A,B)$ 而言，存在如下关系：

$\begin{cases} \tilde G(A,B) = \bigcup_{C \neq A , B} G(A,C) \oplus G(C,B)\\ \hat G(A,B) = \left\{ T | T \in G(A,B) \land T \notin \tilde G(A,B) \right\} \end{cases}\\ \therefore \hat G(A,B) \neq \phi\phantom{wwwwwwwwwwwwwwwwwwwi}$

因此我们可以构造如下的一类集合：

$\begin{cases} G_{n+1}(A,B) = \bigcup_{C \neq A , B} G_n(A,C) \oplus \hat G(C,B)\\ G_0(A,B) = \hat G(A,B) \end{cases}$

$G_n(A,B)$ 中的元素可以通过 n + 1 个程序的并来构造出来，特别的， $G_0(A,B)$ 中的元素无法被拆分。

从而有：

$G(A,B) = \bigcup_{n \ge 0} G_n (A,B)$

现在，我们完成了对集合 $G(A,B)$ 的分解，根据从 A 生成 B 的图灵机可以被拆分的情况进行划分。同时，我们也证明了 $G(A,B)$ 中的元素总能对应到一个直接生成目标字符串 B 的图灵机。

而，由于总能找到从任意字符串 A 生成任意字符串 B 的非常非不变映射程序，所以 $G_n$ 本身可以有可数无穷个。

只不过，由于很显然的原因， $G(A,B)$ 中元素的数量是可数无穷，非但如此，任意 $G_n$ 中的元素数量也是可数无穷， $G_n$ 本身的数量也是可数无穷。

因此，要衡量一个字符串在所有可能的图灵机（或者只考虑非常映射良性图灵机也可以）中被生成的方式总数，直接对 $G(A,B)$ 计数显然是没意义的。

我们要构造一个更合理的表征生成目标字符串的“难易程度”的函数。

我们定义 $|T|_A$ 为程序 T 不算输入参数 A 时的字符数即减去 A 本身长度后的程序长度； $\left< T \right>_A$ 为程序以 A 为输入参数时执行完所需的步数。

定义两个从初始字符串（以下称为初态）A 到目标字符串（以下称为末态）B 的特殊函数：

$\begin{cases} W_\omega (A, B) = \sum_{T \in G(A, B)} \omega^{- |T|_A}\\ \Sigma_\omega (A, B) = \sum_{T \in G(A, B)} \omega^{- \left< T \right>_A} \end{cases}$

其中， $\omega$ 是一个模不小于 1 的参数。

这两个函数分别统计了所有从 A 生成 B 的程序的贡献，分别以程序自身的长度及程序执行所需时间为权重，从而代表了从空间与时间角度来看的从 A 生成 B 的“难易程度”。它们分别被称为“生成权重”与“衍生权重”。

由于对于程序并来说，我们有如下关系：

$\begin{cases} |T \oplus R|_A = |T|_{R(A)} + |R|_A - c\\ \left< T \oplus R \right>_A = \left< T \right>_{R(A)} + \left< R \right>_A \end{cases}$

所以有：

$\begin{cases} W_\omega (A, B) = \omega^c \sum_{C \neq A, B} W_\omega (A, C) W_\omega (C, B) + \sum_{T \in G_0(A, B)} \omega^{- |T|_A}\\ \Sigma_\omega (A, B) = \sum_{C \neq A, B} \Sigma_\omega (A, C) \Sigma_\omega (C, B) + \sum_{T \in G_0(A, B)} \omega^{- \left< R \right>_A} \end{cases}$

这两个函数当然是很难直接计算的——事实上，可以说是不可能直接计算。

但我们还是可以来计算以下 W 的上限，因为即便把常态映射与不变映射都考虑进去，它也存在一个很自然的上限：

$W_{\omega > n} (s) < \sum_{l = K(s)}^\infty n^l \omega^{-l} = \left( \frac{n}{\omega} \right)^{K(s)} \frac{\omega}{\omega - n}$

当 $\omega \ge n$ 时，这个求和的上限发散，虽然我们也不能由此说 W 本身是发散的，但至少能确定当 $\omega = 1$ 时肯定是发散的。

因此，当 $\omega$ 足够大的时候，这两个权重中最主要的是来自 $G_0$ 部分的贡献，也就是从初态到末态的不可拆分程序的贡献，甚至可以说，是最短不可拆分程序与最快不可拆分程序的贡献。

但，如果取 $\omega$ 是一个不大的值，那这两个权重就不单单只是最短不可拆分、最快不可拆分程序的贡献，也不单单是不可拆分程序的贡献，所有 $G_{n>0}$ 中的元素都会有贡献，此时结果为何就很难说了。

另外，如果仿造量子场论中路径积分的做法，取 $\omega$ 为复数比如 $e^{-i E \hbar}$ ，那么此时函数长度或执行次数的一点点小变化就可以得到截然不同的模为 1 的复数，此时认为除了最小值之外的贡献全部抵消，那么我们便也只需要考虑最短不可拆分程序与最快不可拆分程序的贡献。

尤其，如果我们考虑从空字符串到目标字符串 s 的最短不可拆分程序，它往往就是 s 的不可压缩表示，那么我们可以说，s 的生成权重就是 $\omega^{-K(s)}$ 。

而，当我们考虑的是“所有能生成目标字符串 s 的程序的总数”的时候，我们其实考虑的是 $W_1 (\phi, s)$ ，注意这里 $\omega = 1$ ，所以只考虑不可压缩表示的贡献，显然与实际情况差了很远。

下面，我们考虑这么一个“权重占比”函数：

$\Delta_\omega (s) = \frac{W_\omega (s)}{\sum_t W_\omega (t)}$

显然，无论对什么 s，其分母都是一个公共的常数。于是有：

$\ln \Delta_\omega (s) = \ln W_\omega (s) - C$

通过前面计算得到的上限（虽然是远小于该上限的）可得（注意该上限要求 $\omega > n$ ）：

$\ln \Delta_\omega (s) < - K(s) \ln \left( \frac{\omega}{n} \right) + \ln \left( \frac{\omega}{\omega - n} \right) - C$

同时，很显然如果 $\omega$ 非常大，或者它是一个模为 1 的复数时，所以有：

$\ln \Delta_\omega (s) \approx - K(s) \ln \omega - C$

但是当 $\omega$ 不大时，则有：

$\ln \Delta_\omega (s) \gg - K(s) \ln \omega - C$

尤其当 $\omega \approx 1$ 时， $\ln \Delta_\omega (s)$ 与 K(s) 将不再有明显关联。

也就是说，当我们考虑 $\omega > n$ 的情况时，权重占比的上下限都随 K(s) 的增加而增加，且下限下降的速度大于上限下降的速度；而当我们考虑的是“所有能生成目标字符串 s 的程序的总数，在所有可停止程序中的占比”时，它与 K(s) 没有明显关联，因为此时上下限都不再与 K(s) 相关。

同样的，如果我们不用生成权重而是用衍生权重来计算的话，则会发现：

$\Delta_\omega (s) = \frac{\Sigma_\omega (s)}{\sum_t \Sigma_\omega (t)} \Rightarrow\\ \begin{cases} \ln \Delta_\omega (s) \approx - T(s) \ln \omega - C \phantom{www} \omega \ll 1\\ \ln \Delta_\omega (s) \gg - T(s) \ln \omega - C \phantom{wwa} \mathrm{otherwise} \end{cases}$

其中 T(s) 是生成 s 的所有程序中执行步骤最少的步骤数。

这里，将“常态映射”与“不变映射”扣除的作用，是为了将一大类“无用”的等价类给去除。常态映射是所有程序在任意一个环节都可能遇到的，它们不提供任何有价值的信息而只增加程序数。不变映射也是如此这类不提供新信息的东西。虽然这样的无用程序段的构造方式可以有很多，但我们只选择去除这两类，因为这样已经够用了。

当然，有意义的是考虑 $\omega$ 足够大的情况，因为如果真的计算 $\omega = 1$ 的情况，那我们将遇到各种无穷大，此时求比例没多大意义——相反，只有考虑某些确定的 L 趋向无穷的方式的时候，才能得到有意义的占比。这就好比，泛泛而谈地问“0/0”是多少是没意义的。而这就表示， $\omega = 1$ 的情况下（事实上只要 $\omega$ 不比 n 大多少，甚至比 n 小）我们只能讨论特定的 L 及相关量趋向无穷的情况下的相关占比。

而，在前面的内容中我们已经看到，相关量随 L 增长到无穷的方式的不同，会带来不同的结果——事实上，随着 L 趋向无穷，整个图灵机集合的结构可以变得异常丰富而复杂，且都是不可计算的，所以在图灵机层面我们已经拿这些“远端”的丰富结构无可奈何了。

在上面的计算中，明显存在一个有趣的对应关系：

两个权重函数在形式上，与统计力学中的配分函数，及量子场论中的配分函数，非常类似。

事实上，我们构造的“常映射程序”可以看作量子场论中的基态背景，“不变映射函数”则是量子场论的路径积分展开中最常见的“单圈真空量子涨落”， $W_\omega (A,B)$ 是从初态 A 到末态 B 的传播子， $W_\omega (\phi, s)$ 是 s 态的波函数， $\omega$ 就是 $e^{-i E \hbar}$ ，而长度 $|T|$ 与执行步骤 $\left< T \right>$ 的作用就是作用量，去除不提供有效信息而只增加程序数量的做法，则等价于将场论中的冗余自由度给去除。

最大的区别就是，这里处理的是离散的字符空间，而在量子场论中处理的是连续的时空中的量子场。

更进一步，我们还可以构造如下动力学：

取图灵机的寄存器状态为 $\phi_i$ ，读写头位置为 $x^\mu$ ，给定位置上的带内容为映射 $\Psi(x^\mu)$ ，且满足：

$(\phi'_i, \Psi'(x^\mu), x'^\mu) = \Psi(x^\mu) (\phi_i, \Psi(x^\mu), x^\mu)$

进一步，可以做连续化：

$\frac{d}{d \tau}(\phi_i, \Psi, x^\mu) = \Psi(x^\mu) (\phi_i, \Psi, x^\mu)$

这样图灵机就可以看作是一种时空-规范场，其中寄存器状态为代表粒子的规范矢量，带状态为时空度规与规范场强，粒子运动就是读写头运动，时空度规与规范场强作用在粒子上，根据粒子的内禀状态，告诉粒子受力情况也就是下面应该运动到哪里，同时修改粒子的内禀状态，并修改时空与规范场的状态——可以看作是粒子对时空与规范场的反作用。

当然，这样的类比只是一种有趣的脑洞，实际上两者的差异非常大。除了提到过的离散与连续的区别，更主要的是，图灵机的状态变更连续化之后是一阶的，而时空与规范场的动力学是二阶的。

最后，我们也许可以考虑这么一个问题：如果在四值逻辑（真、假、不可判定、矛盾）与超现实数（从而可以考虑可数无穷长的图灵机，Oracle 以各阶无穷的形式出现）的话，图灵机的可计算性会如何。

这个问题会很烧脑哦。

本文遵守创作共享CC BY-NC-SA 4.0协议

通过本协议，您可以分享并修改本文内容，只要你遵守以下授权条款规定：姓名标示 、非商业性、相同方式分享。
具体内容请查阅上述协议声明。
纸媒与网络平台如需转载必须与本人联系确认。