# 柯尔莫哥洛夫复杂度 ![](https://piccdn3.umiwi.com/img/201808/06/201808062254595417109266.jpg) 请不要被今天的标题所吓倒！我们要说一个数学定理，但是这个定理是你能够理解的！ 数学就在你身边，而且很可能就在你意想不到的地方。咱们从电影开始说。 ## 1.俗套、不俗和看不懂的电影 最近姜文出了个新电影叫《邪不压正》，我没看过但是我看到很多人评论这个电影。这些评论的主题大约可以总结为 —— 姜文到底想说什么？ 我们知道电影讲故事都是有固定套路的。一般的电影都是讲英雄故事，你看完电影之后很容易归纳一个“中心思想”：本片描写了主人公不畏艰难、积极进取，几经挫折终于战胜了敌人，同时也战胜了自己，最终抱得美人归…… 而有的导演不爱这么拍。可能有的电影里根本就没有主人公，描写几个看上去非常独立的事件，每个事件的人物之间好像没什么联系。但是你把全片看完之后，发现这几个故事有同一个主题。比如影片讲了四个爱情故事，而这个主题是“爱情很无奈”。那你的影评就可以这么写：先用一句纳兰词开头：“人生若只如初见，何事秋风悲画扇……” 但还有的导演觉得这么拍还是太俗。不俗的拍法是这样的。影片描写一连串的事件，看上去有一个或者几个主人公，其中每个事件你都能看明白是什么意思，事件之间似乎也都有因果联系 —— 但是整个影片看完，你发现你无法理解导演到底想要说什么。是说正义必将战胜邪恶吗？好像不是这个意思。是在讽刺谁吗？也看不太出来。……这些事件好像根本就没有主题！ 姜文的《邪不压正》，大约就有点这个意思。这种电影能激发人们写影评的热情，但我们这里可不打算解读姜文。我要讲一个数学定理。我关心的问题是，你最少写需要多长的影评，才能让人充分领会《邪不压正》这部电影呢？ 这个问题和“信息论”和“可计算性”有关，就如同我们专栏前面讲过的哥德尔不完备性定理一样有意思。咱们先从简单的开始说。 ## 2.什么叫“复杂” 请尝试用最简单的语言，概括下面这三个字符串 —— **1. 001001001001001001001001001001** **2. 1,1,2,3,5,8,13,21,34,55,89,144,233** **3. asiwf082kf8fefljwnfimdnflc** 你一眼就能看出来前两个。第一个字符串就是“把001重复说10遍”，第二个字符串是“斐波那契数列的前12项” —— 我们专栏专门用斐波那契数列作为文章的难度系数，像这期节目的难度系数大约是8。 对前面这两个字符串，我们都能找到比字符串本身更简单的说法去描述它们。就算把它们的长度再增加多少倍，我们这两句话还是可以充分概括。那么我们大概可以说，这两个字符串的“复杂度”，比较低。 但是第三个字符串就不一样了，你根本就没办法用更简单的说法概括。事实上这个字符串是我自己随便打出来的 —— 可是你又不能用“随便打出来的字符串”去概括它，因为随便打出来的字符串可以千变万化，我们要概括的是*这个*字符串。 描述第三个字符串的唯一办法，就是老老实实地把它念一遍。 说到这里，你可能已经想到香农的“信息熵”这个概念了。我们记得，香农定义信息的方法是看它“克服了多少不确定性”。香农的视角是基于概率论的，只看单个字符出现的概率，不关心整个字符串有什么“意思”。 今天我们要说的这个理论，则是从另一个角度审视字符串的信息，它来自前苏联科学家安德烈·尼古拉耶维奇·柯尔莫哥洛夫。柯尔莫哥洛夫的视角是你能用多短的语句去描写这个字符串 —— 正如我们前面说的这三个例子。 柯尔莫哥洛夫让你想象你是在用一段计算机算法来生成这些字符串。如果你学过编程，你可以轻易地用程序生成任意长度的上面那第一和第二个字符串 —— 你用很短的程序就能生成很长的字符串。可是对第三个字符串，你就只好老老实实地使用 **打印 ‘asiwf082kf8fefljwnfimdnflc'** 这个算法。 那么柯尔莫哥洛夫说，前两个字符串的“算法含量”比较低，而第三个字符串的“算法含量”比较高。 据此我们可以定义一个新概念，叫做“柯尔莫哥洛夫复杂度（Kolmogorov complexity）”： —— 所谓“柯尔莫哥洛夫复杂度”，就是能生成这段字符串的最短算法的长度。 前两个字符串的“柯尔莫哥洛夫复杂度”比较低，而第三个字符串的“柯尔莫哥洛夫复杂度”比较高。 “复杂”是个非常……复杂的话题。科学家至今也没找到一个公认的“复杂”的定义，但是柯尔莫哥洛夫复杂度可以作为一个参考标准。 说到这里你大概猜到我为什么要先说电影了。抛开人物、台词和道具的具体细节不谈，我们大约可以说，俗套电影的柯尔莫哥洛夫复杂度比较低，而不俗的电影的柯尔莫哥洛夫复杂度比较高。这里的“低”和“高”体现在你能用多短的影评来概括这个电影。 好，《邪不压正》这个片的柯尔莫哥洛夫复杂度似乎很高。当然复杂度高不等于好看，其实我更喜欢看《我不是药神》。 那么现在问题来了。你能不能开发一个人工智能算法，自动判断每个电影的柯尔莫哥洛夫复杂度呢？试想如果有这么一个算法，我们选片的时候不就多了一个维度吗？比如有的电影虽然观众好感评分比较低，但是复杂度高，那也许是曲高和寡，聪明人会觉得还是值得一看的。再比如有些文章虽然写的很长，但是复杂度低，那也能吸引到某些读者。 **有没有这样的算法呢？** ## 3.定理 答案是没有。这就是我们今天要说的数学定理，这个定理说 —— 柯尔莫哥洛夫复杂度是不可计算的。 也就是说，你永远都找不到一个算法，来自动计算每个字符串的柯尔莫哥洛夫复杂度。这个定理的证明有一点点烧脑，我们这里就不讲了。但是如果你自己感兴趣，稍微上网搜索一下、再稍微花点时间思考，你就能理解它的证明。 我们还是重点说说这个定理的意义。纽约大学布鲁克林分校的计算机科学教授诺森·扬诺夫斯基（Noson S. Yanofsky）最近在一篇文章 [1] 中说，这个关于柯尔莫哥洛夫复杂度的定理是数理逻辑中最深刻的定理之一。 扬诺夫斯基认为，这个定理等于是说，不管你对一系列事件的规律怎么总结，你提出了一个多么深刻的解释 —— 你永远都不知道还有没有更好的总结和更深的解释。 以我之见，说白了就是，不管那些影评人已经下了多大功夫，他们都无法确定姜文是不是还有更深的意思……就连姜文本人也不知道这部电影到底能“深”到什么程度。 说到这里你可能听出了一点讽刺意味。不就是一个电影吗？也许根本就没什么“深刻”含义，这帮影评人纯属故弄玄虚。其实我赞同这个立场。 但我想说的是，关于柯尔莫哥洛夫复杂度的数学定理就好像哥德尔不完备性定理一样，给人类带来一个永久的希望。 **这个希望就是我们永远都有可能从生活中发掘新的意义！你想想啊，人类的大历史也好，我们个人的小日子也好，生活本质上就是一连串的事件，而所谓事件无非就是连续发生的信息。这些事件可能是有联系的，就好像我们今天前面两个字符串一样；也可能是没联系的，就好像我随机手打的第三个字符串一样。也许有些事情有意义，有些事情没意义。也许整个人生都根本就没有意义。** 可是作为一个人，我们总要寻找一些意义。“一切都是随机发生的”这句话可无法指导你过上更好的生活。你总要相信努力奋斗能带来幸福 —— 或者至少能增大幸福的概率 —— 才行。我们总要给自己讲个故事。 正如历史学家不能简单罗列史实，他总要尝试给历史一个解释。 可是编剧的故事越讲越俗，历史学家的解释也都不新鲜了，那将来有没有可能有一个时刻，我们坐在一起感慨，说“行了，所有可能的意义我们都已经见识过了，这个世界再也没有更深刻的意义了”呢？ 会不会有那么一个“观止”的时刻呢？ 我们今天说的这个定理就是说，不会的。你永远都不知道还有没有一个更深刻的意义。 ## | 由此得到 我们得到了一个标准和一个希望。 “柯尔莫哥洛夫复杂度”是衡量一段字符串 —— 或者一部电影、一篇文章、一生的经历 —— 的复杂度的标准。如果你能用很简单的语言概括这个东西，那么这个东西的复杂度就不高。 而找到对这个东西的概括，你也找到了这个东西的意义。 而说明“柯尔莫哥洛夫复杂度”不可计算的数学定理，则给了我们永远追求更深刻意义的希望。 关于“柯尔莫哥洛夫复杂度”我们今天就讲这么多。而你和我都无法知道，这个理论还有没有更深刻的意思！ ![](https://piccdn3.umiwi.com/img/201808/06/201808061900444593873578.jpg)