元数学：计算机、悖论与数学基础 (8-5)

对这些深奥哲学问题加以关注的那一代数学家，基本上随着第二次世界大战而消失了。然后，我出现在了这个舞台上。20 世纪 50 年代末，我还是个年轻人，在《科学美国人（Scientific American）》上读到一篇关于哥德尔和不完备性的文章。哥德尔的结果令我着迷，但我无法真正理解；我觉得其中有猫腻。至于图灵的方法，我很欣赏，因为它更为深入，但我仍然不满意。这时，我对随机性产生了一个有趣的想法。小时候，我还读过很多关于另一个著名智力问题的书，不是数学基础，而是物理学基础——关于相对论和宇宙学，甚至更常见的，是量子力学。我了解到，当事物非常小的时候，物理世界之行为是完全疯狂的。事实上，事物是随机的，本质上是不可预测的。我在阅读这一切时，开始怀疑纯数学中是否也存在随机性。我开始怀疑，也许这就是不完备性的真正原因。

初等数论就是一个很好的例子，其中有一些非常棘手的问题。考虑一下质数。如果你对质数的详细结构感兴趣，那么单个质数之表现是非常难以预测的。确实存在统计规律。有一种叫做素数定理的东西，可以相当准确地对素数之总体平均分布加以预测。但至于单个素数的详细分布，看起来就非常随机了。

根据香农的“保密系统传播理论

(Communication Theory of

Secrecy Systems)”——这篇论文由于五角大楼的原因被封存了多年——解决这一基本不可判定性的唯一途径乃经验事实，即加密系统大多是从一些偶然事件中选择出来的，这些偶然事件虽然尽可能多，但最终都是有限的，而噪声则可以有无限多的值（values）。正因如此，昔日漫无目的

(purpose-free）的数论[15]如今已变成了对最高可能素数（highest possible primenumbers）的追逐，而这些素数——作为军事工业秘密信息之加密，对于尚未破解它们的敌人来说，必然是噪音。图灵是著名的计算机理论家，也是世界大战期间不为人知的密码学家，他提出，自然法则可以用密码系统代替，证据问题可以用截获的信息代替，物理常数可以用日常的密钥元素代替——也就是说，整个自然科学可以用密码分析代替。[16] 混乱与战略之间的差别已经变得如此微小。

于是我开始思考，也许数学中所固有的随机性，为所有这些不完备性提供了更深层次的原因。20 世纪 60 年代中期，我和苏联的科尔莫戈罗夫（A. N. Kolmogorov）共同提出了一些新观点，我称之为算法信息论（algorithmic information theory）。这个名字听起来很厉害，但基本思想很简单： 它只是一种对计算复杂性加以测量的方法。

我最早是从冯-诺依曼那里，听说到计算复杂性这一概念的。图灵将计算机视为一个数学概念——一台完美的计算机，一台永远不会犯错的计算机，一台拥有对工作加以完成所需的时间和空间的计算机。图灵提出这个想法后，数学家的下一个逻辑步骤，就是对计算之进行所需的时间加以研究——这是对计算复杂性加以衡量的一个标准。1950 年左右，冯-诺依曼强调了计算之时间复杂性的重要性，现在这已经成为一个发展成熟的领域。

我的想法不是看时间，尽管从实用的角度来看，时间非常重要。我的想法是，对计算机程序之 大小/规模（size）[2]加以研究，对为了让计算机完成某项任务而必须提供给它的信息量加以研究。为什么这很有趣？因为程序之大小，其复杂性同物理学中的熵（Entropy）概念有关。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。