逻辑中的意外发现

John Baez

2016 年 4 月 4 日

逻辑的法则中存在一个内在的复杂度屏障：粗略地说，虽然很多事物都比它复杂，但我们无法证明任何 特定的 事物比它复杂。而且这个屏障出乎意料地低！有多低？请阅读本文。

然后看看当我们将这个想法与著名的“突击测验悖论”（也称为“意外绞刑悖论”）结合起来时会发生什么。

从数学上讲，这些思想被称为 Chaitin's incompleteness theorem 和 Kritchman–Raz 对 Gödel's second incompleteness theorem 的证明。但不要被吓倒：我将解释你需要知道的一切！

之后，我将解释另一个惊喜：存在一台计算机，可以在某种算术模型中计算任何不可计算的函数……。

Chaitin's incompleteness theorem

我们能否从一粒小小的种子开始，孕育出整个宇宙及其看似所有的复杂性？ 你仅用少量信息能做多少事情？

人们就此展开了竞赛。 Dan Piponi 指出了这个 2009 年创建的 动画视频，它使用了一个小于 4 KB 的程序，该程序在 Windows XP 机器上运行：

一个美丽的异星世界被压缩成了区区 4 KB 的信息！正如我的程序员朋友 Bruce Smith 指出的那样：

公平地说，应该包括一些操作系统、图形驱动程序和硬件的复杂性，但这比你想象的要少得多，如果你想象为了紧凑性而不是为了速度而纯粹地重写它，并且只包括这种程序产生输出所需的内容。

尽管如此，这仍然非常惊人。

请注意，人们不是一夜之间就弄清楚如何从少量信息中产生如此精美的图像！Iñigo Quílez 是制作此视频的人之一，他解释了一些 技巧。 它们很深刻！ 它们在 demoscene 中发展了数十年——一种计算机艺术亚文化，人们在其中制作 demos: 非交互式视听计算机演示文稿，实时运行。

根据 Wikipedia 上关于 demoscene 的文章：

最近的计算机硬件进步包括更快的处理器、更多的内存、更快的视频图形处理器和硬件 3D 加速。 随着过去许多挑战的消除，制作 demos 的重点已从尽可能多地从计算机中榨取性能转移到制作时尚、美观、设计良好的实时艺术品。

然而，古老的传统仍然存在。 Demo parties 举办竞赛，在程序大小或平台（不同的系列称为 [compos](https://math.ucr.edu/home/baez/http:/en.wikipedia.org/wiki/Compo_%28demoscene%29））方面存在各种限制。 在现代计算机上，可执行文件的大小可能限制为 64 KB 或 4 KB。 大小受限的程序通常称为 intros。 在其他 compos 中，平台选择受到限制； 只允许使用旧计算机，如 8 位 Commodore 64、16 位 Amiga 或 Atari ST，或者移动设备，如手持电话或 PDA。 这种限制为程序员、音乐家和图形艺术家带来了挑战，并带回了使设备的功能超出其原始设计意图的旧动机。

仅用少量信息还能做什么？Bruce Smith 列出了另外几个：

所以，令人惊讶的是，非常复杂的事物可以被压缩成相当少的信息。你禁不住会想：事物能有多复杂？

答案是：任意复杂！至少如果我们谈论位串的 Kolmogorov complexity：即打印出它的最短计算机程序的长度。许多长位串无法压缩。你无法使用短程序打印出它们中的大多数，因为没有足够的短程序可供使用。

当然，我们需要预先确定一种计算机语言，以便明确定义。 我们需要确保程序是用二进制编写的，这样比较才是公平的。

所以，事物可以是任意复杂的。 但这里有一个更有趣的问题：我们能 证明 某个东西有多复杂？

答案是我所知道的最令人震惊的事实之一。 它被称为 Chaitin's incompleteness theorem。 它大致是说：

存在一个数字 L，使得我们无法证明任何特定位串的 Kolmogorov complexity 大于 L。

确保你理解这一点。 对于任何数字，我们都可以证明存在无限多个 Kolmogorov complexity 大于该数字的位串。 但是我们无法指出任何 特定的 位串并证明其 Kolmogorov complexity 大于 L！

Allen Knutson 写道：

这是一个令人难以置信的令人不安的定理，就像开车到宇宙的边缘并找到一堵墙。

我称 L 为“复杂度屏障”。 所以一个问题是，L 有多大？

L 不仅取决于我们使用的编程语言，还取决于我们用来证明事物的数学系统。 通过以奇怪的方式调整这些，我们可以使 L 变得任意大或任意小。 但是，如果我们做出“合理”的选择呢？

Chaitin 声称，对于某种版本的编程语言 LISP，以及任何可以编码在 N 位长的 LISP 程序中的数学公理系统，复杂度屏障为 L≤N+2359 位！ 很难，甚至可能无法找到对某种编程语言和数学系统有效的 最小 L，因此这是一个上限。 详情请参见：

有趣的是，在向一位技术娴熟的程序员解释了 Chaitin 定理的证明后，他会 猜测 L 的值是多少。 所以，我请我的朋友 Bruce Smith 猜测一些其他合理的编程语言和数学系统的 L 值。 他估计它是 几千字节！ 这比 Chaitin 的值大，但大致一致。

我想看到一个几千字节长的程序，它产生一个视频，显示一个大爆炸，恒星和星系的形成，然后是行星，包括一个生命进化的行星，然后是智能生命，然后是计算机的发展……最后是有人编写相同的程序。

我无法证明这是可能的……但 你无法证明它不是！

让我们看看为什么。 让我们看看 Chaitin's incompleteness theorem 的证明。

Chaitin's incompleteness theorem——证明

首先，我们需要为我们的数学系统选择一些公理，以便我们知道“可证明”是什么意思。 我们需要一个足够强大的系统来证明大量关于算术的基本事实，但又足够简单，以便计算机程序可以检查该系统中证明的有效性。

有很多这样的系统。 三个著名的系统是 Peano arithmetic、Robinson arithmetic（功能较弱）和 Zermelo-Fraenkel set theory（功能更强大）。

当你有这样一个数学系统时，Gödel's first incompleteness theorem 就会发挥作用：如果系统是一致的，它就不可能是完整的。 换句话说，它会留下一些未解决的问题。 这就是为什么我们不应该完全震惊，虽然一堆位串的复杂性大于 L，但我们无法 证明 这一点。

Gödel's second incompleteness theorem 也会生效：如果系统可以证明它是一致的，那么它就不是！（如果它不一致，它可以证明 任何事情，所以你不应该相信它。）所以，在某种意义上，我们永远无法完全确定我们的数学系统是一致的。 但让我们假设它是。

鉴于此，Chaitin's theorem 说：

存在一个常数 L，使得没有任何位串的 Kolmogorov complexity 可证明地超过 L。

我们如何获得一个可以完成这项工作的数字？ 任何具有 U+log2(L)+K<L 的数字 L 都可以。 这里：

以二进制形式写出的 L 的长度约为 log2(L)。 因此，这个更大的程序的长度为 U+log2(L)+K 并且为了使 Chaitin's incompleteness theorem 的证明有效，我们需要它小于 L。 显然，我们可以通过使 L 足够大来实现这一点，因为 log2L 的增长速度慢于 L。

鉴于我告诉你的所有内容，Chaitin 定理的证明几乎不言自明！ 你运行我刚才描述的这个更大的程序。 如果存在一个位串，其 Kolmogorov complexity 可证明地大于 L，则该程序将打印出一个。 但这是一个矛盾，因为这个程序的长度小于 L。

所以，我们只需要选择一种计算机语言和一个合适的数学系统，并估计 U 和 K（不太重要，因为它小得多）。 那么 L 将比 U+K 略大一些。

我选择了 C 语言和 Peano arithmetic，并询问 Bruce 他是否可以粗略地猜测一下我们得到的 L 答案是什么。 他回答说：

我认为这不能用 C 来完成，因为除非你指定一个特定的有限机器大小，否则 C 语义没有明确定义。 （因为 C 程序可以执行诸如将指针转换为整数并返回、告诉你任何数据类型的大小以及将任何指定数据类型的数据转换为字节并返回的操作。）在 N 位的有限机器上，所有程序要么在小于大约 2N 的时间内完成，要么永远运行。

但是，如果你采用“没有大小特定操作的 C”，或者更高级的语言（如 Python），或者就此而言，采用不同类型的低级语言（如 Turing machine），那么这就不是问题了——你可以定义一个精确的语义，允许它运行程序任意长时间并在内存中分配任意数量的对象，这些对象包含彼此的指针。 （为了坚持问题的精神，对于你选择的任何语言，你都希望禁止使用任何大型外部信息批处理，如“标准库”，除了你认为它是本机语言一部分的任何基本内容。 这对于这个问题来说不是一个严重的障碍。）

程序“U”（我宁愿将程序本身称为“U”，而不是将其长度称为“U”）需要做的主要事情是：

  • 识别语法正确的语句或证明；
  • 检查声称的证明的有效性；
  • 识别某些语句为说或暗示“n 的 Kolmogorov complexity 大于 i”，对于某些 n 和 i。 （不必识别所有此类语句，只需每个 n 和 i 至少识别一个即可，因此它可以只识别一个由某些模板组成的语句，其中特定值的 n 和 i 插入到特定位置。）

假设 U 以一种实用的证明语言表达它想要检查的证明（这将更像像 Coq 这样的实用定理证明器使用的语言，而不是传统逻辑学家会认为的“直接 Peano arithmetic”，但根据这个问题的精神，它不会过于强大），我估计最复杂的部分是检查证明有效性，但是仍然可以用至多几十条语法规则来表达，每条规则可以用几行代码来表达。 （像 Coq 这样的系统的作者，其中包括实际执行该操作的代码，会更了解，只要他们记住他们系统中绝大多数实际代码不是这个问题所需要的。）

这让我想即使没有尝试压缩它很多，在一种合理的语言中，我们可以用几百行代码编写 U，或者（经过一些简单的压缩）几千字节。 （如果我们努力以巧妙的方式压缩整个程序，可能会少得多。）

所以 L 也将是“几千”（字节或数字），或者更少，而不是你永远无法数到的数字。

Kritchman–Raz 对 Gödel's second incompleteness theorem 的证明

2010 年，Shira Kritchman 和 Ran Raz 使用 Chaitin's incompleteness theorem 以一种意想不到的新方式证明了 Gödel's incompleteness theorem。

我想用一种非常草率的方式来解释他们的论点，以便每个人都能理解它。 逻辑很酷，但大多数人从未接触到酷的部分，因为他们无法克服相当枯燥的技术细节。

你听说过 突击测验悖论，对吧？ 老师说有一天他会进行一次测验，这将是一个惊喜。 所以孩子们认为“好吧，它不可能是最后一天——我们会知道它要来了。” 然后他们认为“好吧，所以它也不可能是倒数第二天！——我们会知道它要来了。” 等等……他们说服自己这根本不可能发生。

但是然后老师在第二天就进行了测验，他们完全感到惊讶。

人们仍然争论不休如何解决这个悖论。 但无论如何，Kritchman 和 Raz 使用了这个悖论的一个 严格的 版本，再加上 Chaitin's incompleteness theorem 来演示 Gödel's second incompleteness theorem——它 非常 粗略地表示：

如果数学可以证明自身是一致的，那么它就不是。

如果你是一名逻辑学家，我敢打赌这种草率的陈述真的让你很恼火。 如果是这样，我很抱歉：我想 以一种非常草率的方式 总结 Kritchman 和 Raz 的论点。 你可以很容易地添加细则以使此摘要严谨——或者，如果你愿意，请阅读 他们的论文。

好的，我们开始吧：

Chaitin's theorem 已经令人震惊，它说存在某个长度 L，你无法证明任何特定的位串需要一个比 L 更长的程序才能打印出来。 至少，如果我们的数学系统是一致的，情况就是这样。 如果它不一致，你可以证明任何事情！

另一方面，存在一些长度 ≤L 的有限数量的程序。 所以，如果你列出一个比这更多的数字列表，比如 1,2,…,N，那么 必须至少有一个 需要一个比 L 更长的程序才能打印出来。

好的：必须至少有一个。 有多少？ 假设 只有一个。 那么我们可以遍历所有长度 ≤L 的程序，找到那些打印出我们列表中的所有其他数字的程序……因此，通过一个消除过程，找到罪魁祸首。

但这意味着我们已经证明这个罪魁祸首是一个只能通过长度 >L 的程序计算的数字。 但 Chaitin 定理说这是不可能的！ 至少，如果数学是一致的，就不是。

所以不可能只有一个。 至少，如果数学是一致的，就不是。

好的：假设 只有两个。 好吧，我们可以使用相同的技巧并找出它们是谁！ 所以也不可能 只有两个。 至少，如果数学是一致的，就不是。

我们可以继续玩这个游戏，直到我们排除所有可能性……然后我们真的陷入了困境。 我们得到了一个矛盾。 至少，如果数学是一致的。

所以如果我们能证明数学是一致的，我们就会知道它不是！

参考资料

本文最初出现在我的博客上的三篇文章中。 我在这里对它们进行了润色，但是那里有很多有趣的评论，你可能想发表自己的评论或提出问题：

正如我提到的，Chaitin 在这里证明了他的 incompleteness theorem 的一个版本：

但是，如果不回到这本较早的书，这本书很难阅读：

Kritchman 和 Raz 在这里证明了他们的结果：

关于 Chaitin's incompleteness theorem 的意义已经有很多讨论。 这是一个聪明的论点，表明其中一些说法被夸大了：

要了解有关 Kolmogorov complexity 和相关思想的更多信息，请尝试：

不可计算函数的可计算性

这是另一个令人惊讶的结果：

让我尝试在不假设你是数理逻辑专家的情况下解释它。 这可能很难，但我会尝试。 我们需要从一些背景知识开始。

首先，你需要知道存在许多不同的算术模型。 如果你写下自然数的通常公理，即 Peano axioms，那么你可以四处寻找遵守这些公理的不同结构。 这些被称为 Peano arithmetic 的“模型”。

其中之一是 你 认为自然数是什么。 对你来说，自然数只是 0、1、2、3，...，以及通常的加法和乘法方式。 这通常被称为 Peano arithmetic 的“标准模型”。 数字 0、1、2、3、... 被称为“标准”自然数。

但是也有 nonstandard models of arithmetic。 这些模型除了标准数字之外还包含额外的数字！ 这些被称为“非标准”自然数。

这需要一段时间才能适应。 需要经历几个理解层次。

首先，你应该将这些额外的“非标准”自然数视为大于所有标准自然数。 所以，想象一下在标准自然数之后添加了一大堆额外的数字，并且巧妙地定义了加法和乘法运算，使得所有通常的公理仍然成立。

你不能只添加有限数量的额外数字并使其工作。 但是可以有可数个或不可数个。 有无数种不同的方法可以做到这一点。 它们都很难描述。

为了掌握它们，意识到这一点会有所帮助。 假设你有一个算术语句 S，该语句既不能从 Peano axioms 中证明也不能证伪。 那么 S 将在某些 Peano arithmetic 模型中成立，而它的否定 not(S) 将在某些其他模型中成立。

例如，Gödel 语句 G 说“这个语句不能从 Peano axioms 中证明”。 如果 Peano arithmetic 是一致的，那么 G 和 not(G) 都不能在 Peano arithmetic 中证明。 所以 G 在某些模型中成立，而 not(G) 在其他模型中成立。

因此，你可以直观地将不同的模型视为“可能的世界”。 如果你有一个不可判定的语句，这意味着你不能使用 Peano axioms 证明或证伪的语句，那么它在某些世界中成立，而它的否定在其他世界中成立。

就 Gödel 语句 G 而言，大多数数学家认为 G 是“正确的”。 为什么要用引号？ 真理是逻辑中一个棘手的概念——对于算术中的一个句子来说，什么是“真”，没有精确的定义。 我们所能精确定义的只是：

  1. 一个句子是否可以从某些公理中证明 和
  2. 一个句子是否在某些模型中成立。

尽管如此，数学家是人，所以他们对什么是真理有自己的信念。 许多数学家认为 G 是真的：事实上，在流行的解释中，人们经常听到 G 是“真的，但不能从 Peano axioms 中证明”。 所以，这些数学家倾向于说任何 G 不成立的模型都是非标准的。

无论如何，Joel David Hamkins 的结果是什么？ 是这样的：

存在一个 Turing machine T 具有以下属性。 对于从自然数到自然数的任何函数 f，存在一个 Peano arithmetic 模型，使得 在这个模型中，如果我们给 T 任何标准自然数 n 作为输入，它会停止并输出 f(n)。

所以，假设 f 是你最喜欢的不可计算函数。 那么存在一个算术模型，使得 在这个模型中，Turing machine 计算 f，至少当你将标准数字作为输入馈送给机器时。

所以，非常非常 粗略地说，存在一个可能的世界，其中你的不可计算函数变得可计算！

但是你必须非常小心地解释这个结果。

诀窍是什么？ 证明很漂亮，但要改进 Hamkins 的博客文章 需要做很多工作，所以请阅读它。 我只想说，他广泛使用了 Rosser sentences，它说：

对于理论 T 中这个句子的任何证明，都存在一个更小的证明，证明这个句子的否定。

Rosser sentences 已经令人震惊，但 Hamkins 使用了这些句子及其否定的 无限序列，以取决于函数 f 的方式选择，以巧妙地制作一个算术模型，在该模型中，Turing machine 在标准输入上计算该函数。

但是真正发生了什么？ 如何使用非标准模型使不可计算函数对于标准自然数变为可计算？ 非标准模型不应该在这个问题上与标准模型一致吗？ 毕竟，唯一的区别是它们在所有标准数字之后添加了额外的非标准数字！ 这怎么能让 Turing machine 成功地在 标准 自然数上计算 f？

我不能 100% 确定，但我想我知道答案。 我希望一些逻辑学家纠正我，如果我错了。

你必须非常仔细地阅读结果：

存在一个 Turing machine T 具有以下属性。 对于从自然数到自然数的任何函数 f，存在一个 Peano arithmetic 模型，使得 在这个模型中，如果我们给 T 任何标准自然数 n 作为输入，它会停止并计算 f(n)。

当我们说 Turing machine 停止时，我们的意思是它在 N 步之后停止，对于某些自然数 N。 但是这可能不是一个标准自然数！ 它是我们正在谈论的模型中的自然数。

所以，Turing machine 停止了……但也许只是在非标准数量的步骤之后。

简而言之：你可以计算不可计算的，但前提是你愿意等待足够长的时间。 你可能需要等待一个非标准的时间量。

就像那句古老的海军谚语一样：

the-difficult-we-do-immediately-the-impossible-takes-a-little-longer

但是如果你注意到 一台 Turing machine 在不同的模型中计算从自然数到自然数的 不同函数，这个技巧就变得更加明显了。 这甚至比计算一个不可计算函数还要奇怪。

在一种模型中构建一台计算 n+1 的机器，并在另一种模型中构建一台计算 n+2 的机器的唯一方法是构建一台机器，该机器在任何一种模型中都不会在标准时间内停止。 它只会在 非标准 时间量之后停止。 在一种模型中，它停止并输出 n+1。 在另一种模型中，它停止并输出 n+2。

一个可怕的可能性

为了更深入地挖掘——这就是变得有点可怕的地方——我们必须承认标准模型是一个有点难以捉摸的东西。 当我说这句话时，我当然没有定义它：

对你来说，自然数只是 0、1、2、3，...，以及通常的加法和乘法方式。 这通常被称为 Peano arithmetic 的“标准模型”。 数字 0、1、2、3、... 被称为“标准”自然数。

关键是这里的“0、1、2、3、...”是模糊的。 如果你已经知道什么是标准自然数，它才有意义。 但是如果你还不知道，那些三个点不会告诉你！

你可能会说标准自然数是 1 + ··· + 1 的形式，其中我们将 1 加到自身一些有限次数。 但是这里的“有限次数”是什么意思？ 这意味着一个标准自然数！ 所以这是循环的。

因此，可以想象，“标准”自然数概念和 Peano arithmetic 的“标准”模型概念比大多数数学家认为的更主观。 也许我的一些“标准”自然数对你来说是非标准的！

我认为大多数数学家会拒绝这种可能性……但并非所有。 Edward Nelson 在他精彩的书 Internal Set Theory 中正面解决了这个问题。 他写道：

也许可以说，“有限”并不意味着我们一直认为的意思。 我们一直认为的意思是什么？ 我曾经认为我知道我一直认为的意思，但我不再这么认为了。

如果我们走这条路，Hamkins 的结果就具有不同的意义。 它表明，“自然数”概念中的任何主观性也可能影响 Turing machine 停止的含义，以及 Turing machine 在停止时计算的函数。

© 2016 John Baez baez@math.removethis.ucr.andthis.edu

home