文章目录

◆ ◆ ◆◆ ◆ ◆◆ ◆ ◆

这篇文章摘自:复杂性第四章的计算

作者:梅勒妮·米歇尔

编者按:自计算机诞生以来，计算的概念已经经历了很长时间，现在很多科学家都把计算视为自然界的普遍现象。细胞、组织、植物、免疫系统和金融市场显然与计算机的工作方式不同，那么它们所说的计算到底是什么意思呢？他们为什么再说一遍？

◆ ◆ ◆

什么是计算？能算出什么？

香农的信息定义了信息源的可预测性。然而，在现实世界中，信息是用来分析和产生意义的东西。信息被储存起来，并与其他信息相结合，以产生结果或行为。简而言之，信息是用来计算的。

计算的意义在历史上发生了很大的变化。直到20世纪40年代末，计算都是用手做数学运算(小学生称之为“做算术”)。计算机是做数学运算的人。我以前的老师阿特·伯克斯(Art Burks)经常告诉我们，他娶了一个“计算机”——一个在二战期间被征召入伍手动计算弹道的女人。Beukes的妻子遇到他时就是这样一个计算器。

现在计算指的是各种计算机做的事情，似乎自然界的复杂系统也做这个。但是到底是怎么计算的呢？它能做什么？计算机能计算任何东西吗？原则上有限制吗？这些问题直到20世纪中期才得以解决。

◆ ◆ ◆

希尔伯特问题和哥德尔定理

对计算基础及其局限性的研究导致了电子计算机的发明，但其最初的根源是为了解决一组抽象(且深奥)的数学问题。这些问题是德国数学家戴维·希尔伯特在1900年的国际数学家大会上提出的。

希尔伯特，1862-1943(美国物理学会西格尔图像档案，兰德收藏)

(AIP埃米利奥塞格雷视觉档案，兰德收藏)

希尔伯特在演讲中提出了世纪之交需要解决的23个数学问题。其中问题2和问题10后面的影响最大。事实上，它们不仅仅是数学的内部问题；它们是关于数学本身和数学能证明什么的问题。一般来说，这些问题可以分为三个部分:

1.数学完整吗？

也就是说，是否所有的数学命题都可以被有限的一组公理证明或证伪。

比如还记得中学几何学的欧几里德公理吗？还记得这些公理可以用来证明三角形内角之和为180度的定理吗？希尔伯特的问题是:有没有一个公理集合可以证明所有的真命题？

2.数学一致吗？

换句话说，所有可以证明的命题都是真的吗？“真命题”是个专业术语，但我这里用的是直接的意思。如果我们证明一个伪命题，比如1 1=3，数学不一致，那么就会有大麻烦。

3.所有命题都是数学上可确定的吗？

也就是说，所有的命题是否都有一个确定的程序，可以在有限的时间内告诉我们命题是真还是假？这样，你就可以提出一个数学命题，比如“所有大于2的偶数都可以表示为两个素数之和”，然后交给计算机，计算机就会用“显式程序”在有限的时间内得出命题真假的结论。

最后一个问题是所谓的Entscheidungsproblem(“决策问题”)，这个问题可以追溯到17世纪数学家戈特弗里德·莱布尼茨。莱布尼茨建造了自己的计算机器，认为人类会建造一台可以判断所有数学命题真假的机器。

这三个问题30年都没有解决，但希尔伯特自信答案一定是“是”，并断言“没有解决不了的问题。”

然而，他乐观的断言并没有持续多久。可以说非常短暂。因为就在希尔伯特做出上述论断的同一次会议上，一位25岁的数学家宣布了不完全性定理的证明，他的发现震惊了整个数学界。这个年轻人的名字叫库尔特·哥德尔。不完全性定理说，如果上面问题2的答案是“是”(即数学是一致的)，那么问题1(数学是否完全)的答案一定是“否”。

哥德尔，1906-1978

(图片由普林斯顿大学图书馆提供)

哥德尔的不完全性定理从算术开始。他证明了如果算术是一致的，那么一定存在一个无法用算术证明的真命题——即算术是不完全的。如果算术不一致，那么就会出现可以证明的伪命题，这样整个数学就崩溃了。

哥德尔的证明非常复杂。然而，凭直觉，这很容易解释。哥德尔给出了一个数学命题，翻译成白话就是“这个命题是不可证明的。”

仔细想想。这个命题很奇怪，它其实是在说它自己——其实是说它不能被证明。我们称之为命题a，现在假设命题a是可证的。那么它就是假的(因为它说它不能被证明)。这意味着伪命题被证明——从而算术不一致。好吧，我们假设它的命题A是不可证明的。这意味着命题A是真的(因为它断言它是不可证明的)，但接下来还有一个不可证明的真命题——算术不完全。因此，算术要么不一致，要么不完整。

很难想象这个命题是如何转化为数学表达式的，但哥德尔做到了——这就是为什么哥德尔的证明如此复杂精彩，我们在这里就不讨论了。

大多数数学家和哲学家坚信希尔伯特问题是可以正解的，这对他们是一个沉重的打击。正如数学作家安德鲁·霍奇基斯所说:“这是研究中一个惊人的转折点，因为希尔伯特认为他的计划将主宰世界。对于那些认为数学完美无瑕的人来说，这是不可接受的…深圳生活网”

◆ ◆ ◆

图灵机与不可计算性

哥德尔干净利落地解决了希尔伯特的第一个和第二个问题，然后第三个问题被英国数学家艾伦·图灵干掉了。

图灵，1912-1954年

1935年，图灵23岁，随逻辑学家马克斯·纽曼在剑桥攻读研究生。纽曼向图灵介绍了哥德尔刚刚得到的不完全性定理。在了解哥德尔的结果后，图灵找到了解决希尔伯特第三问题的方法，并确定了问题。同样，他的答案是“不”

图灵是怎么证明的？如前所述，判断问题是，有没有“明确的程序”来判断任何命题是否可以被证明？“明确程序”是什么意思？图灵的第一步是定义这个概念。遵循两个世纪前莱布尼茨的思路，图灵通过构想一个强大的算术机器来解释他的定义，这个机器不仅可以进行算术运算，还可以对符号进行运算，从而证明数学命题。通过思考人类是如何计算的，他构造了一个幻像机，现在叫做图灵机。图灵机后来成为电子计算机的蓝图。

节选自湖南科学技术出版社

通往平均霸权的道路

数学之美:平凡而神奇的贝叶斯方法

大师告诉你，学数学有什么用？