你 16 岁时梦想做什么？我想开车环游世界。但美国数学家雷·索洛莫诺夫在那个年纪有更远大的目标。他想找到一种方法来解决所有可以想见的科学问题。
这不仅仅是异想天开，这位少年有一个开创性的想法，将建立一个全新的研究领域。在接下来的几年里，索洛莫诺夫提出了一个概念，该概念使系统地搜索数据中的模式成为可能，从而揭示我们世界背后的隐藏过程。
今天，这可能让人想起人工智能的工作方式。但是索洛莫诺夫在 1942 年就提出了他的第一个想法——远在人工智能算法出现之前。索洛莫诺夫的方法基于奥卡姆剃刀原理，根据该原理，对现象最简单的解释通常是正确的。（物理学家也采用同样的逻辑；他们寻求最简单的公式来尽可能多地描述物理过程。）
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关当今塑造我们世界的发现和想法的影响深远的故事的未来。
索洛莫诺夫正在寻找一套规则或算法，以揭示数据中的隐藏关系。他希望，通过这种方式，世界上的一切都可以得到简单的解释。例如，如果您记录抛出的棒球的轨迹，您可以找到任意数量的数学公式（有些非常复杂）来再现轨迹的路线。要从所有这些可能性中推导出正确的规律，您应该寻找最简单的描述。答案很可能对应于牛顿运动定律，该定律描述了两种力的相互作用：人抛球的力和将球拉到地面的重力。
索洛莫诺夫正在寻找一个规则，该规则将选择所有可能描述中最简单的描述。这样的规则可以转化为计算机程序。任何数据都可以传递给这个程序，经过一定的时间后，就可以获得对这些值起源的最简单的解释。这将是一台名副其实的奇迹机器。
如何定义“简单”
首先：索洛莫诺夫的最简单描述查找器不存在——而且永远不会存在。然而，凭借他的想法，当时 16 岁的他站在了一个全新研究领域的前沿，该领域涉及机会和复杂性的真正本质。正如自然科学中经常发生的那样，另外两个人在大约同一时间产生了非常相似的想法。
这些人之一是苏联数学家安德烈·柯尔莫哥洛夫，他主要关注概率和随机数。特别是，他对如何判断现象的描述是简单还是复杂感兴趣。
假设我向您展示数字 25,041,903。乍一看，它似乎很随机。有多种方法可以解释我是如何获得这个值的。例如，我可能使用了随机数生成器，并按顺序获得了数字 2、5、0、4、1、9、0 和 3。这似乎不是很令人满意——它背后没有任何有助于您记住该值的推理。但我也可以说这个数字等于三个素数 3 x 61 x 136,841 的乘积。或者我可以告诉您，数字序列从 pi 的第 40,122,575 位小数位开始，或者我选择这个数字是因为柯尔莫哥洛夫出生于 1903 年 4 月 25 日。这些解释中哪一个听起来最简单？不同的人可能会有不同的回答。
柯尔莫哥洛夫成功开发了一种客观方法来确定物体的复杂性。数字的柯尔莫哥洛夫复杂性对应于计算该数字的最短计算机程序的长度。程序越短，数字越简单。
因此，柯尔莫哥洛夫复杂性取决于所使用的编程语言。某个程序在 Python 中可能比在 C++ 中更短，反之亦然。每个计算机程序都可以用机器代码表示，机器代码又由 0 和 1 的序列组成。计算机计算所需结果的最短 0 和 1 序列的长度对应于柯尔莫哥洛夫复杂性。
因此，如果您想确定 25,041,903 的柯尔莫哥洛夫复杂性，您可以将各种解释（它是数字枚举或素数分解的结果、pi 中的位置或柯尔莫哥洛夫生日的日期）转换为计算机程序，并计算相应机器代码中所需的字符。
而我之前的例子可能排除了 25,041,903 的更简单的解释。柯尔莫哥洛夫开发了一种系统的方法来识别最短的程序。为此，您给计算机一个数字，例如 25,041,903。然后，计算机逐个运行所有可能的算法——从最小的开始，用 0 或 1 编码。计算机这样做，直到制定的程序产生所需的结果。例如，第一个返回 25,041,903 值的程序是最短的。它的字符长度对应于 25,041,903 的柯尔莫哥洛夫复杂性。
一个讨厌的悖论摧毁了梦想
乍一看，索洛莫诺夫的梦想现在似乎已经实现了。借助柯尔莫哥洛夫复杂性，似乎可以揭示任何数据中的任何模式。
但是一个悖论给工作带来了麻烦。哲学家伯特兰·罗素在 1908 年将相关问题归因于图书管理员 G. G. 贝里——远在索洛莫诺夫和柯尔莫哥洛夫发表他们的想法之前。贝里思想实验的一个例子如下：假设你有一本只有 20 个单词的字典，你尝试使用这些单词来描述不同的数字——非常类似于柯尔莫哥洛夫在计算机程序中的想法。您可以开始使用这 20 个单词逐步定义数字。组合这 20 个单词的方式只有有限种，因此您只能描述有限数量的数字。然而，由于数字是无限的，其中一些数字将无法进行这样的定义；您最终会得到一个无法用 20 个或更少的单词描述的数字。但是，如果您使用这 20 个单词中的一些来制定描述“无法用 20 个或更少的单词描述的最小数字”呢？
这个定义仅包含 12 个单词，从而产生了矛盾。哪里出错了？事实证明，您无法计算定义一个数字需要多少个单词。乍一看，这似乎是一个廉价的借口，但事实上，贝里悖论和柯尔莫哥洛夫复杂性与数学最违反直觉的特征之一有关：有些真理无法证明。或者换句话说：数学是不完备的。
假设真的有一个计算机程序 K 可以计算与每个输入相关的柯尔莫哥洛夫复杂性。这个程序由一百万个字符组成。它不必快速或高效；它只需要工作。
现在测试该程序，并为其提供所有可能的输入，直到您最终找到一个复杂度为 200 万的大数 x。然后以类似于贝里悖论的方式进行。您编写一个新的计算机程序 P，该程序执行以下任务：它系统地遍历所有字符串，并使用程序 K 计算字符串的柯尔莫哥洛夫复杂性，直到找到一个复杂度为 200 万的字符串。
新程序 P 直接依赖于 K，因此不会包含比 K 多太多的字符。（在任何情况下，它都由少于 200 万个字符组成。）但这意味着已经找到一个字符少于 200 万的计算机程序，该程序计算出的数字的复杂性为 200 万——这是一个矛盾。
如果一个逻辑论证产生矛盾，则至少有一个假设必须是错误的。在这种情况下，我们假设存在一个程序 K，该程序计算每个输入的柯尔莫哥洛夫复杂性。因此，只有一个可能的结论：这样的 K 不可能存在。不可能找到对于每个可以想象的输入都生成此输入的最短程序。
尽管如此，一个圆满的结局是可能的
因此，16 岁的索洛莫诺夫的梦想没有实现。但是，即使柯尔莫哥洛夫复杂性无法针对每个输入进行计算，这个想法在许多应用中仍然证明是有用的。大多数特殊情况不需要精确的柯尔莫哥洛夫复杂性——近似值就足够了。专家通常使用压缩程序来实现这一点。在需要柯尔莫哥洛夫复杂性的情况下，“您可以将数据输入到压缩程序中，例如使用 gzip 或将图像另存为 .gif 文件，并将其用作粗略的近似值”，德克萨斯大学奥斯汀分校的计算机科学家斯科特·阿伦森告诉Plus。
例如，如果您想找出两个数字序列 x 和 y（例如，它们可以对应于测量数据）是否相关，您可以首先分别压缩 x 和 y，然后将两个序列附加在一起并压缩 xy。如果 xy 的压缩率仅略高于 x 或 y 的单独压缩率，那么数字序列之间一定存在相关性——并且您获得了隐藏模式的线索。
柯尔莫哥洛夫复杂性也可用于确定特定数字序列的随机性。例如，三个八位数字 25,041,903、47,395,929 和 10,101,010 可能是由随机数生成器生成的——即使它们并非都显得同样随机。通过偶然性生成这三个数字中每一个数字的概率是相同的：在 00000000 到 99,999,999 的数字范围内，您遇到其中一个值的概率为 1/108。但 10,101,010 有明显的模式，25,041,903 也是如此，它对应于出生日期。通过计算数字的柯尔莫哥洛夫复杂性，可以评估它们是否遵循某种模式——以及随机数生成器是否可靠地工作。
不幸的是，柯尔莫哥洛夫复杂性没有回答“生命、宇宙和万物”的问题。如果我们相信科幻小说作家道格拉斯·亚当斯，那么这个问题的答案是 42。但奇怪的是，数字 42 并不是特别复杂——可以使用柯尔莫哥洛夫复杂性来计算它。
本文最初发表于《明镜在线》杂志，经许可转载。