无穷的灾难

• 所有是谁的所有？
• 所有的有穷
• 结果的无穷？过程的无穷？
• 计算与停机
• 无穷无穷尽也
• 没有终点

作为一个科研工作者，特别是科学工作者，我们总是非常喜欢逻辑。 我小时候认为，人只是自然的一部分，只是无垠宇宙中一粒尘埃。 与人打交道的知识是局促的，世俗的；与自然打交道的知识是永恒的，浪漫的。 我一直很讨厌被人规定要做什么，规定不能做什么。 忌恨于人与人的博弈与妥协；热衷于脱离人情的限制，以纯粹理性的逻辑来理解世界。 可以说这是推动我走向物理研究的主要支柱之一。

但是随着我在数学与物理的汪洋中越行越远，逻辑中的浪漫似乎渐渐的模糊了。 从 Anderson 著名的 More is Different 到哥德尔不完备定理, 再到可计算理论， 借用加来道雄评价爱因斯坦的理想理论的一句话：

当然，这种“大理石的理想”在数学与物理中是有着本质的区别的。 或者可以说物理与数学中浪漫主义的衰退有着截然不同的来源。 甚至在相当一部分的领域中，古典的浪漫主义仍旧占有着非常主要的地位。 在很大程度上，此类破碎感只是一种主观的情绪，而非具体的事实。 包括我在内的很多人将他们联系起来大概是源于科学范式转型期的一种群体迷茫感。 我们确实还是在沿着一贯的路径探索着新的理论。 科学的进步也从未停止。 但是渐渐的突然发现，好像我们很难再认同我们是为了一个理想的目标而前进。 我们只是专注于眼前的道路，但是不管从哪个角度去深入思考我们的研究的非世俗意义，脑海中似乎只会充斥着虚无感。

所有是谁的所有？

在数学中，这种迷茫感很大程度上来源于无穷。 在标准分析的发展中，我们逐渐意识到我们通常表达的无穷其实并不是无穷。 我们说的无穷某种程度上代表了所有的有穷。 这个“所有的有穷”引出了两个“灾难性”的概念。 一个是“所有”，一个是“所有的有穷”。

在“所有”这个词的作用下，我们有了描述抽象的物体，而脱离具体个体的能力。 我们可以说出“所有羊都是白色的”这样的逻辑表达式。 这里我们不需要指定任何一只具体的真实的羊，而是在讨论“羊”这个抽象的概念的性质。 在当代形式逻辑的定义下，“所有”这个词起始于一阶逻辑。 在一阶逻辑中，我们说“所有的 x”的时候规定 x 只能是具体个体的抽象，而不能是对抽象本身的抽象。 如果我们要讨论抽象的抽象，我们必须使用二阶逻辑。 我们可以将这个抽象的层次一直延续下去，直到永远。 这意味着我们不能用一个有限的 n 阶逻辑去讨论所有的抽象概念。

我们对“所有”这个概念的定义如此复杂都源于罗素在20世纪初发现的悖论

如果我们说集合是有明确定义的一些物品的搜集，因为 $x\notin x$ 是一个明确的逻辑表达，那么罗素悖论显然定义了一个集合。 但是

• 如果 $S \in S$, 那么 $S$ 不满足这个集合的条件，也就是说 $S\notin S$；
• 如果 $S \notin S$, 那么 $S$ 满足这个集合的条件，也就是说 $S\in S$；

也就是说 $S$ 即属于自身，也不属于自身，即违背了矛盾律。 当然，其实我们通过公理化集合论有很多种解决这种矛盾的手段，比如我上面说的将逻辑分阶，或者说是类型论的手段。 另一种更数学的解决方法是使用 ZF 公理集，将集合作为一种先验概念。 此时我们可以承认“集合”这个概念是有局限的，并且在数学中我们不需要去讨论那些不能用集合论表示的概念。 当我们说“所有”这个词的时候，我们必须要限制在某个具体的集合中，而非满足某个逻辑表达式的个体。

所有的有穷

在我们解决罗素悖论后自然会考虑，如果我们将抽象的概念分层，我们是否就能用逻辑解决所有能被集合表达的问题了呢？ 令人失望的是即使是最简单的概念，一旦被加上了“所有”这个词，都很容易击溃我们用逻辑去理解它的努力。

我相信，对绝大多数的人来说，数学都是从数数开始的。 我们先学会数自己的手指，用一些符号去标记顺序。 比如我从左手拇指数到小指，将它们依次标记为 $1,2,3,4,5$. 为了让大家能够以更抽象的方式去理解这个问题，让我们姑且用字母去替代数字。 即我们将左手拇指到小指依次标记为 $a,b,c,d,e$。 在记住了如何按次序标记物体后，我们可以学习用同样的方法去标记苹果，香蕉，乃至一切独立的物体。

当我们熟悉了数数之后，我们渐渐的学会了计数的能力。 如果我们把一族物体放成一排，从左到右依次标记，我们会意识到最后的那个标记好像代表了这一族物体的某种性质。 我们用这个最后的标记，比如 $e$ 作为这一族物体的标记。 这就是这组物体的数量。 为了以示区分，我们用 $N(e)$ 来代表数量。 也就是我们可以声称“我左手手指的数量是 $N(e)$”。

想让一族物体的基数被良定义有一个重要的前提，即这个标记与数数的顺序无关。 我们数一排苹果，它的数量与我是从左向右还是从右向左数是无关的。 不过这种恒常性与我在此希望讨论的问题无甚关系，暂且不深入。 我这里希望强调的是当我们讨论“有穷”与“无穷”的时候，我们讨论的其实是序数问题，而非基数问题。 基数是一个更加复杂的问题 （$\aleph_1 = 2^{\aleph_0}$?），某种程度上说我们对它还知之甚少。

众所周知，现代人类有一套极其强大的计数系统，即进位系统。 假设我们允许用任意的符号去标记物体，我们用十进制系统可以很容易的为每一个物体分配一个标记。 我们逐一为物体分配标记，而进位系统可以轻松的保证这些标记“永远”不会重复也不会用尽。 可以想象，只要一族物体是有限的，我们从某个个体开始数起，或早或晚每一个物体都可以被分配到一个标记。 用另一种方法来描述：“从某一个个体开始数，直到在任意一步停下来，所有被标记的物体的集合是有限的”。 在这个描述下，“有限”与“可数”被当作是等价的概念了。 这便是著名的皮亚诺公理 （Peano Axioms）

需要注意的是，我这里给出的并不是标准的皮亚诺公理。 皮亚诺公理定义的是“自然数”，或者说“计数数”。 但是在数学中，“数”是一个极度抽象的概念，如上列出的皮亚诺公理可以被理解为原始皮亚诺公理的一种具体的表示。 在 ZF 公理系中，这套表示是用空集与并集的概念构造的，而我这里选择的是计算理论的“字符”。

可以看到，在归纳公理中出现了一句“包含了所有的计数符号”。 而根据我们之前的讨论，从起始符开始，直到分配到某一个具体的计数符号为止，所有被标记的物体的集合是有穷的。 也就是说，每一个计数符号都代表了一个有穷的集合。 让我们用同样的数数方法去数这个“包含了所有的计数符号的集合”：

无穷公理意味着，在计数符号的集合中，我们并没有停止计数的条件。 这意味着，“基数”这个“最后一个标记”在这个集合上是不存在的。 换言之，用计数符号去标定“所有计数符号的集合”是不可行的。 也就是说，计数符号无法被用于表达所有计数符号的集合。

为了理解这件事确实不是自然的，让我们看看在有限的集合中是怎样的。 考虑计数符号的前 5 项的集合： $\qty{a,b,c,d,e}$，我们可以把它的“数量”，即基数标记为 $N(e)$。 显然 $N(e)$ 与 $e$ 是对应的，而 $e$ 是集合 $\qty{a,b,c,d,e}$ 中的一个元素。 同样的，不管我们取计数符号的前几项，它总是可以用自身的元素标记自身的性质。 但是这件事情在我们说出“所有”这个词之后就失效了。 将“所有”这个词作用在“有穷”上，我们突然就创造了一个非有穷的抽象物体。 很大程度上，有穷的事物是符合人类的经验的，而无穷突然就变成超验的了。 其中最著名的例子便是希尔伯特旅馆。 为了简单起见，我们临时将计数符号换回阿拉伯数字。

这个悖论有几个不同的版本，从一个新客人到可数无穷个巴士，每一辆拉来可数无穷个新客人，我们都可以给他们安排房间。 这个悖论意味着，似乎对于无穷多个空位，即便每一个空位都被占用了，这不等于找不到空位。 这显然违背我们日常的经验。 在计算理论或者组合数学中，有一个非常重要的工具：

也就是说，如果我们在 $n$ 个笼子中放入 $n$ 个对象，然后再向他们中放入一个新的对象，那不可避免的至少有一个笼子中会同时出现两个对象。 这个原理对任意的 $n$ 都是正确的，但是当我们考虑所有的 $n$ 时，它突然就失效了！ 希尔伯特旅馆告诉我们，对于所有的 $n$ 的集合，我们可以在放入一个新的对象的前提下保证每个房间都只有一个人。

结果的无穷？过程的无穷？

符合经验的事物，它们的总和为什么突然就不符合经验了呢？ 如果仔细观测希尔伯特旅馆中的描述与我最后的解释，我们可以看到一个很有意思的事情。 希尔伯特旅馆中，旅馆经理“安排”客人的方法是，对于每一个客人，先判断他当前的状态，然后根据他当前的状态告诉他之后去哪里住。 但是我们要如何“安排”这些客人呢？

最简单的安排方案就是旅馆经理一个一个的告诉客人它们应该去的房间。 他可以先去敲 $1$ 号房间的门，请该客人去 $2$ 号房间门口等待，然后叫 $1$ 号新客人入住 $1$ 号房间。 然后再去敲 $2$ 号房间的门，请该客人去 $4$ 号房间门口等待，再让门口等待的客人入住 $2$ 号房间。 如此反复，却没有终止的时刻。

我们发现，让经理一个人去安排客人实在是太低效了。 酒店有那么多门童，完全可以利用起来，完全不需要经理自己去安排。 我们让一个门童去敲奇数房间的门通知客人，另一个门童去敲偶数房间的门，再安排一个门童在门口安排新来的客人。 但是我们发现，这个过程还是太漫长，还是会永远的进行下去。 那么我们继续增加门童的数量，调来 $2m$ 个门童。 让 $m$ 个门童去敲 $kn$ 号门，另外 $m$ 个门童去安排第 $kn$ 个新客人，其中每个门童分别负责 $[1,m]$ 中的一个 $k$。 我们进行 $2m$ 线并行的操作，比旅馆经理一个人去工作快了 $2m$ 倍。 但是我们发现，不管我调来多少门童，不管 $m$ 有多大，这个工作还是会持续到永远。 为了在有限时间内安排好所有的客人，我们需要召集来可数无穷多个门童，每个人分别负责一个房间，然后通知完房间内的客人后每个人再分别通知一个新客人。 或者说等价的，我们假设每一个客人都是会算数的，我们向所有人进行广播，告诉大家如何确认自己应该去的房间。 让这可数无穷个智慧的个体去安排房间。

我们可以看到，希尔伯特旅馆的安排意味着，为了完成这个安排，我们需要同时进行无穷多个任务。 而这无穷多个任务需要无穷多个可以将抽象的安排翻译为具体的房间号的个体去完成。 换言之，我们无法用有限的资源去完成不可用计数符号标记的任务。 但是这个任务却是可以由有穷个字符所明确定义的。

计算与停机

想想一下，如果我们让一个有着无限内存的电脑去完成这个任务：

请 1 号房间的客人搬去 2 号房间，请 1 号新客人搬入 1 号房间，请 2 号房间的客人搬去 4 号房间，请 2 号新客人搬入 2 号房间 ...

可以想象，这个过程会永远的持续下去，电脑会一直输出正确的结果，但是永远不会停止。 我们可以这样理解这个问题：虽然人类可以想象无穷，但是由于现实的计算资源总是有穷的，希尔伯特旅馆的安排永远无法被执行完。 在意识到这个问题后，我们自然会觉得，这个任务无法被执行完是因为我们在试图用有穷的资源去标定无穷的物体。 那么是不是我们再退一步，我们不去考虑所有有穷的集合，而是去考虑所有有穷的任务，我们是不是就全部可以处理了呢？

1936 年，图灵提出了图灵机的思想。 在此之后，人类终于把“处理有穷的任务”这件事形式化了。 这里我并不想进入过多的细节，且介绍图灵机的文章汗牛充栋，也无需我多言。 其形式化的定义非常的复杂，也非常的拗口。 但是图灵机基本定义了如下的模型：

图灵原理声明，如果一个问题是可以被计算的，那么它一定也可以被图灵机所处理。 如果所有的图灵机都无法处理某个问题，那么这个问题是永远无法被计算的。 这历史性的将“人类可以处理的任务”形式化了。

既然图灵机将我们的目光进一步的限制在了有穷的任务上，那么人类是不是就能解决如此局限的集合中的所有问题了呢？ 答案是否定的。 首先，我们可以理解，不管现代计算机如何发达，它还是很容易会陷入死机的状态。 我们也可以用一行简单的代码： while(True){ } 让一个程序永不停歇的运行下去。 简单的说，总是有一些图灵机在某些，甚至任意的输入下会永远的运行下去。 我们说这样的状态是不停机的。 反之，如果这个图灵机能够输出正确结果，或者发现自己的方案无法解决输入的问题，它会停机，并显示结果。 那么，我们自然会想，为什么不把不停机的输入直接当作无法解决的问题呢？ 这样不就只有能解决和不能解决两种情况了吗？

图灵告诉我们，判断图灵机是否会停机这件事本身就做不到。 也就是说，向一个图灵机输入一个任务，如果它不停机，程序就报错，这个任务本身就是无法处理的。 也就是说不可计算问题是必然存在的。 注意，我们这里已经将条件限制在了所有有穷的任务中。

我们神奇的发现，即便我们做了如此强的假设，即便我们已经将我们的期望限制到了有穷的任务，我们似乎又回到了罗素悖论：

停机问题的证明利用了图灵机的有穷性：因为图灵机是有穷的，每一台图灵机都可以被唯一的标记。 而输入也是有穷的，每一条输入也可以被唯一的标记。 我们可以选择同样的标记符号，使得每一台图灵机都有与其对应的唯一的一条输入。 假设我们构造出了一台可以解决停机问题的图灵机 $M_s$，那么它必然有相对应的唯一一条输入 $I_s$。 此时我们构造另一台图灵机 $M_P$, 它接受一个输入 $I_i$，然后找到该输入对应的唯一的图灵机 $M_i$ 并模拟 $M_s$ 输入 $I_i$ 的行为。 如果 $M_i$ 解决了 $I_i$, 则进入死循环，而如果 $M_i$ 报错， $M_P$ 认为问题被解决了。 如果我们将图灵机看作一个函数的话，一个更清晰的写法是

def M_P(I_i):
    if M_s(M_i,I_i):
        while(True){}
    else:
        return

那么如果我们输入 M_P(I_P) 结果会是什么呢？

1. 如果 $M_P$ 不停机，那说明要么 $M_s$ 不停机，要么 $M_s$ 的结果是确定的。
   1. 如果 $M_s$ 不停机，说明它无法解决它自己是否能停机的问题；
   2. 如果 $M_s$ 停机，那么说明将 $I_P$ 输入 $M_P$ 是停机的；
   3. 但是事实是 M_P(I_P) 不停机；
2. 如果 $M_P$ 停机， 那说明
   1. $M_s$ 认为 M_P(I_P) 是不停机的；
   2. 但是事实是 M_P(I_P) 停机；

无穷无穷尽也

如果我们不局限于停机问题，不可计算问题的存在有另一种证明的方法：

用计算理论的语言来说就是“存在图灵机不可判定语言”。 当我们去考虑图灵机的数量是，很容易会感到迷惑。 因为我们说图灵机不可判定的时候，我们说的是对所有的图灵机，该语言都不可被判定。 但是图灵机是可数无穷多的，也就是这个“所有”包含了所有的有穷。 即使是这么强大的资源，依然无法解决所有的有穷问题的集合。

实际上这等价于康托定理的对角线论证法

这里的“势”是一个基数的概念，也就是集合里元素的数量。 在希尔伯特旅馆中我们看到，两组可数无穷的客人可以被安排到一组可数无穷个房间中。 对于这样“可以被安排”的状态，我们说两组可数无穷的客人的集合的势不大于一组可数无穷的房间。 一个更形象的说法是，一个可数无穷的集合可以覆盖两个可数无穷的集合。 在希尔伯特旅馆中，我们甚至可以为可数无穷多的巴士，每辆巴士上可数无穷多的客人安排房间。 这样看下来，可数无穷个房间好像足以安排下任意多的客人。 但是图灵机的例子告诉我们，可数无穷多的资源也是有极限的。

考虑任意的集合 $A$, 以及它的幂集 $2^A$, 即其所有子集的集合。 假设我们有可以用集合 $A$ 中的元素唯一标记的一些资源。 而来了 $2^A$ 集合中的元素才能唯一标记的一些顾客。 对于任意的一种资源的安排方式 $f: A\to 2^A$，考虑集合 $B = \qty{x\in A: x\notin f(x)}$. 我们便构造出了一种罗素悖论：

这意味着将集合扩展这种事情可以无尽的进行下去。 无穷之上还有更多的无穷，无穷无穷尽也

没有终点

在前面的讨论中，我们可以看到，从罗素悖论开始，我们不断的在缩小着我们可以用逻辑描述的抽象物体的范围。 但是在无穷公理的作用下，不管我们向何处去，我们永远也避不开罗素悖论。 在不断理解这些理论的过程中，我们只能不断感叹人类逻辑能力的弱小，或者感叹人类抽象能力的强大。 在一层一层的缩小我们逻辑讨论的范围的过程中，我们可以清晰的看到人类逻辑能力与抽象能力的差距有多么巨大。

在我讨论量子信息的时候说过，我们的量子信息基本是建立在有限维空间上的。 当我们把空间的维度推到无穷，各种各样难以想象的困难将向我们铺面而来。 而我们在经典物理理论中，总是用实数去描述空间与时间。 然而这意味着在这样的连续空间中构造出来的量子理论，我们甚至无法找到一个可数无穷的基底去描述它。

我们试图用离散的，有限的语言去描述我们的世界。 但是当我们去思考“宇宙有没有尽头，宇宙尽头外面是什么”的时候，我们还是不可避免的将无穷囊括进我们的讨论范围。 无穷到底是对科学中浪漫主义的毁灭？还是另一种美学的新生？