导语

如何判断一段话信息量是大是小？在香农那里，可以用“克服了多少不确定性”来描述。而在柯尔莫哥洛夫那里，要看“用多长的代码能生成这句话”。

编译：集智俱乐部翻译组

来源：Nautilus

原题：Kolmogorov Complexity and Our Search for Meaning

当你遇到那个特别的人时，这只是一次偶然的邂逅还是隐藏着更深层次的原因？

当你昨晚做了一个奇怪的梦时，这只是意味着大脑突触间随机运转还是揭示了潜意识深处的更深刻的原理？（也许这个梦正试图告诉你一些关于未来的事情；也许并不是。）

当一个近亲患上了一种致命的癌症时，这仅仅是DNA随机突变的结果还是具有更深刻的原因？

我们一生都在思考周围发生的事件的模式。我们会问自己，它们是否只是随机的，或者它们是否有某种独特的真实而深刻的原因。作为一名数学家，我经常求助于数字和定理来深入了解这些问题。

碰巧的是，我从数学逻辑的一个最深奥的定理中了解到一些关于在生活模式中寻找意义的东西。简单地说，这个定理表明，即使在原则上，我们也无法知道对某种模式的解释是否是最深刻或最有趣的解释。就像在生活中一样，在数学中寻找意义是没有界限的。

Hartverdrahtet 节选| 2012年德国Revision Demoparty活动获奖作品。这个震撼的分形宇宙，是由一段不到4k字节的程序生成的，这比一个Word空文档还小。

Kolmogorov复杂度理论

首先，作为开场白，我们考虑以下三个字符串：

100100100100100100100100100100100100100100100100100100100100100100100
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
38386274868783254735796801834682918987459817087106701409581980418

如何描述这些字符串呢？我们可以将它们写下来（像上文一样）以进行简单描述，不过前两个字符串的描述较短：第一个字符串可以看作“100”的简单重复；第二个字符串只是对前几个素数的排列。

而第三个字符串呢？我们也可以通过输出字符串来进行描述。只是这里有更好更简短的描述方法吗？

随机性令人不安，因此我们寻找一种模式来消除一些混乱。

20世纪60年代初，美国少年格里戈里·蔡廷(Gregory Chaitin)、世界著名的俄罗斯数学家安德烈·科尔莫哥洛夫(Andrey Kolmogorov)和计算机科学先驱雷·索罗门诺夫(Ray Solomonoff)分别独立制定了一种测量字符串复杂度的方法。

他们的观点被称为Kolmogorov复杂度理论（Kolmogorov Complexity Theory）或算法信息论（Algorithmic Information Theory）。他们假定字符串与生成字符串的最短计算机程序的长度一样复杂。也就是说，取一个字符串，然后寻找一个产生这个字符串的简短的计算机程序。

程序是字符串的一种描述类型。如果其中最短的程序非常短，那么字符串有一个简单的模式，不是很复杂。我们说字符串“几乎没有算法内容”。相反，如果需要一个长程序来生成字符串，那么字符串就很复杂，而且“有更多的算法内容”。

对于任何字符串，必须找到产生该字符串的最短程序，该程序的长度称为字符串的Kolmogorov复杂度（the Kolmogorov complexity of the string）。

我们再考虑一下上面三个字符串。前两个字符串都可以用相对较短的计算机程序来描述，即：

输出30次“100”
输出前25个素数

因为第一个字符串的程序较第二个更短，所以第一个字符串的Kolmogorov复杂度小于第二个字符串的Kolmogorov复杂度。

而第三个字符串呢？这个字符串并没有明显的规律可循；然而，我们也可以通过下面这个相对愚蠢的程序输出这个序列，即

输出

“38386274868783254735796801834682918987459817087106701409581980418”

但这个程序并不令人满意，即使它可以输出第三个字符串。

最短程序

也许存在一个较短的程序，其中蕴含着这个字符串的一些规律。这里，当生成字符串的最短程序只是“输出字符串”时，我们说这个字符串非常复杂并且不存在已知规律。不存在任何规律的字符串称为随机字符串。

然而，虽然目前我们并没有发现任何规律，但规律仍然有可能存在。在数学中，就像在生活中一样，我们面临着许多看似随机的模式。

这时，我们可能会尝试使用现代计算机的强大功能来找到一些模式并得到最短的程序。

如果有一台计算机可以简单计算任何字符串的Kolmogorov复杂度，那岂不是很好？此计算机将字符串作为输入，并输出可生成该字符串的最短程序的长度。当然，有了人工智能、深度学习、大数据、量子计算等各种新颖的计算机工具，创造出这样一台计算机是很容易的。

Mandelbrot 集的分形图局部。这张图片中每个像素用24位色表示，需要162万个字节才能存储。但普通计算机程序就可以使用Mandelbrot集的定义和图像四角坐标，来重现这162万字节所表示的图像。所以编码这个图片的Kolmogorov复杂度元小于162万字节。| wikipedia

唉，可是这样的计算机是不可能存在的！尽管现代计算机功能强大，这项任务还是无法完成。这是数学逻辑中最深刻的定理之一的内容。

该定理表明我们无法计算一个字符串的Kolmogorov复杂度，没有任何机械设备能够确定产生给定字符串的最小程序的大小。

这并不是说我们目前的计算机技术水平不足以完成手头的任务，也不是说我们不够聪明，无法编写算法。相反，事实证明，描述和计算的概念表明，没有这样的计算机能够为每一个字符串执行这样的任务。

虽然计算机可能会在字符串中找到某些模式，但它找不到最佳模式；我们可能会找到一些输出特定模式的短程序，但仍可能存在更短的程序。对此我们永远无法确定。

证明不可计算性

关于一个字符串的Kolmogorov复杂度的不可计算性的证明是需要一些技巧的。不过这是一个通过反证法的证明，并且我们可以通过下面两个小悖论来体会一下它是如何进行的。

有趣数字悖论围绕着所有自然数都是有趣的而展开。例如，1是第一个数字，所以它很有趣；2是第一个偶数；3是第一个奇素数；4也很有意思，因为4 = 2×2且4 = 2 + 2。于是，我们可以继续以这种方式找到许多数字有趣的属性。而有时，我们可能会找到一些似乎无趣的数字。我们可以将这个数字称为第一个无趣的数字。但这本身又是一个有趣的性质。因此，无趣的数字实际上也很有意思！这便导出了矛盾。

我们根本不知道我们发现的模式是否是最好的。

Kolmogorov证明中的思想也与培里(Berry)悖论中的思想类似，后者关于描述大量数字。一般地，使用的单词越多，你可以描述的数字越大。例如，你可以用三个字描述“一万亿”；而你可以用五个字描述“一万亿万亿”，显然这个数字要大得多。现在我们考虑以下短语描述的数字：

“少于15个字无法描述的最小数字。”

“The smallest number that cannot be described in less than 15 words.”

即描述这个数字需要用15、16甚至更多的字，而不能仅用12、13或14个字来描述。然而，这里存在一个问题：上述短语中仅用14个字（英文原文对应12个单词）描述了这个数字。我们对该数的描述正好也违反了该数的描述。这显然是一个矛盾。

无论在有趣数字悖论还是在培里悖论中，我们都假设存在一种确定的描述方式，于是导致了上述矛盾。类似地，关于Kolmogorov复杂度不可计算的证明也源于这样一个事实，如果我们假设其存在，那么我们也会发现矛盾。

复杂的现实世界

当然，Kolmogorov复杂度不可计算的事实是纯数学的结果，我们不应该将这个原始的领域与更复杂、更混乱的现实世界混为一谈。然而，在考虑现实世界时，的确会存在一些与Kolmogorov复杂度理论相关的共同主题。

同一个圆上的两段弧，哪个更复杂？

很多时候，我们会发现一些看起来完全混乱的事情。这种随机性如此令人不安，因此我们试图寻找一种能够消除一些混乱的模式规律。

如果我们确实找到了一种模式，但是我们仍不清楚它是否是能够解释我们所看到的事情的最佳模式。我们可能会问自己是否还存在更深层次的模式从而可以提供更好的解释。

Kolmogorov复杂度理论就告诉我们，在最深的层面上，并没有确定的方法来确定最佳模式。也就是说，我们根本不知道我们发现的模式或者规律是否是最好的。

但是，这同时也意味着我们的探索始终会很有趣。毕竟，有趣的事情往往都需要更多的思考；而显而易见且完全理解的事实不需要进一步的思考。例如，6乘7等于42是完全可理解的也是无趣的。当我们不确定某种想法时我们需要不断地进一步思考，于是寻找更好的模式或者规律总是很有趣的。

我们想知道周围的世界有一些意义，目的和价值。

现实世界中显然包含着更多的复杂性。尽管在字符串以及计算机程序中通常没有错误，然而在现实世界中我们可以并且确实会犯错。

事实上，我们可以很容易地看到某个程序是否输出一个字符串，虽然我们可能无法确定输出特定字符串的最佳程序，但我们可以确定程序是否输出了所需的字符串。相比之下，现实世界要复杂得多。

我们可以认为我们认识一个模式，但事实上，我们错了。

寻找规律和意义

现在，我们对寻找意义的理解开始融合在一起。我们讨厌随意性而喜欢规律。

我们天生就倾向去发现一些模式或规律去解释一些事情，但我们永远无法确定我们找到的规律是否正确。即使我们能够以某种方式确信我们没有犯错，我们正展现出类似计算机的完美，但其中仍有可能存在更深层次的真理。

当然，这种不安有助于激发我们对文学、戏剧和电影的热爱。当我们阅读小说或观看戏剧时，作者或导演会向我们呈现一系列具有共同主题、模式或寓意的事件。现实世界中，难以理解又毫无意义的混乱将我们包裹，而文学、戏剧和电影给我们提供了一个愉快地逃离混乱的机会。真正优秀的文学作品走得更远，它们给世人留下了多种解读的可能性。我们将能够直面Kolmogorov复杂度的不可计算的事实。

并且，这种不安也决定了我们如何对待自己的生活。当我们经历生活中看似随机的事件时，我们也正在寻找一些规律和结构。生活充满了“跌宕起伏”。有时会坠入爱河，与孩子们一起欢笑，在完成艰难工作后感到成就的乐趣；有时又会为破碎的关系、努力工作后的失败结局而痛苦，或者经历亲人去世的悲剧。

我们试图理解这一切。我们厌恶完全随机性的感觉，厌恶我们只是遵循混乱的、习惯性的物理学法则的观点。我们想知道身边的世界存在一些意义，目的和价值。我们想要一个神奇的生活故事，所以我们给自己讲故事。

然而有时这些故事完全是假的。有时我们欺骗自己和周围的人，而有时我们确定的规律又是对的。但即使故事是对的，也不一定是最好的。我们永远无法知道是否有更深层次的更准确故事。

随着年龄的增长和厌倦的折磨，我们对宇宙有了一些以前从未见过的洞见。我们找到了更好的规律。也许我们可以更清楚地认识世界，也许我们并不能。这些我们永远也不会知道，但我们知道人们的探索永无止境。