什么是计算,什么可以计算？

本文摘自：《复杂》第四章 计算 作者：梅拉妮·米歇尔

编者按：自从计算机诞生以来，计算的概念已经走过了很长一段时间，现在许多科学家都将计算视为自然界中很普遍的现象。细胞、组织、植物、免疫系统和金融市场显然和计算机的运作方式不一样，那么他们说的计算到底是什么呢？他们又为什么要这样说呢？

◆ ◆ ◆

什么是计算？什么可以计算？

香农的信息定义关注的是消息源的可预测性。不过在现实世界中，信息是用来分析并产生意义的东西，信息被存储，并和其它信息结合，产生结果或行为。总之，信息是用来计算的。

历史上计算的意义变化很大。直到20世纪40年代末，计算都是指的手工进行数学运算（小学生称之为“做算术”）。计算员（Computer）就是做数学运算的人。我以前的老师伯克斯（Art Burks）常和我们说他娶的是“计算机”——指的是二战时被征召入伍手工计算弹道的妇女，伯克斯的夫人在遇到他时正是这样一位计算员。

现在计算指的是各种各样的计算机干的事情，另外自然界的复杂系统似乎也干这个。但是计算到底是什么呢？它又能做些什么呢？计算机什么都能算吗？是不是存在原则上的局限性？这些问题都是在20世纪中叶才得到解决。

◆ ◆ ◆

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

对计算的基础及其局限的研究，导致了电子计算机的发明，但其最初的根源却是为了解决一组抽象（而且深奥）的数学问题。这些问题是德国数学大师希尔伯特（David Hilbert）于1900年在巴黎的国际数学家大会上提出来的。

希尔伯特，1862–1943（美国物理学会西格尔图像档案，兰德收藏）

（AIP Emilio Segre Visual Archives, Lande Collection）

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

1.数学是不是完备的？

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

举个例子，还记得中学几何里学过的欧几里得公理吧？记不记得用这些公理可以证明“三角形内角和为180度”这样的定理？希尔伯特的问题是：是不是有某个公理集可以证明所有真命题？

2.数学是不是一致的？

换句话说，是不是可以证明的都是真命题？“真命题”是专业术语，但我在这里用的是直接意义。假如我们证出了假命题，例如1+1=3，数学就是不一致的，这样就会有大麻烦。

3.是不是所有命题都是数学可判定的？

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

最后这个问题就是所谓的Entscheidungsproblem（“判定问题”），它可以追溯到17世纪的数学家莱布尼茨（Gottfried Leibniz）。莱布尼茨建造了他自己的计算机器，并且认为人类将建造出能判定所有数学命题真假的机器。

这三个问题过了30年都没有解决，不过希尔伯特很有信心，认为答案一定是“是，”并且还断言“不存在不可解的问题。”

然而他的乐观断言并没有维持太久。可以说非常短命。因为就在希尔伯特做出上述断言的同一次会议中，一位25岁的数学家宣布了对不完备性定理的证明，他的发现震惊了整个数学界，这位年轻人名叫哥德尔（Kurt Gödel）。不完备性定理说的是，如果上面的问题2的答案是“是”（即数学是一致的），那么问题1（数学是不是完备的）的答案就必须是“否。”

哥德尔，1906-1978

（照片由普林斯顿大学图书馆提供）

哥德尔的不完备性定理是从算术着手。他证明，如果算术是一致的，那么在算术中必然存在无法被证明的真命题——也就是说，算术是不完备的。而如果算术是不一致的，那么就会存在能被证明的假命题，这样整个数学都会崩塌。

哥德尔的证明很复杂。不过直观上却很容易解释。哥德尔给出了一个数学命题，翻译成白话就是“这个命题是不可证的。”

仔细思考一下。这个命题很奇怪，它居然谈论的是它自身——事实上，它说的是它不可证。我们姑且称它为“命题A。”现在假设命题A可证。那么这样它就为假（因为它说它不可证）。这就意味着证明了假命题——从而算术是不一致的。好了，那我们就假设它命题A不可证。这就意味着命题A为真（因为它断言的就是自己不可证），但这样就存在不可证的真命题——算术是不完备的。因此，算术要么不一致，要么不完备。

难以想象这个命题如何转换成用数学语言表述，但是哥德尔做到了——哥德尔的证明的复杂和精彩之处就在此，在这里我们不去讨论。

绝大多数数学家和哲学家都坚定地认为希尔伯特问题能被正面解决，这对他们是个沉重的打击。就像数学作家霍吉斯（Andrew Hodges）说的：“这是在研究中惊人的转折，因为希尔伯特曾以为他的计划将一统天下。对于那些认为数学完美而且无懈可击的人来说，这让人难以接受……”

◆ ◆ ◆

图灵机和不可计算性

哥德尔干净利落地解决了希尔伯特第一和第二问题，接着第三问题又被英国数学家图灵（Alan Turing）干掉了。

图灵，1912-1954

1935年，图灵23岁，在剑桥跟随逻辑学家纽曼（Max Newman）攻读研究生。纽曼向图灵介绍了哥德尔刚刚得出的不完备性定理。在理解哥德尔的结果之后，图灵发现了该如何解决希尔伯特第三问题，判定问题，同样，他的答案也是“否。”

图灵是怎么证明的呢？前面说过，判定问题问的是，是不是有“明确程序”能判定任意命题是否可证？“明确程序”指的是什么呢？图灵的第一步就是定义这个概念。沿着莱布尼茨在两个世纪以前的思路，图灵通过构想一种强有力的运算机器来阐述他的定义，这个机器不仅能进行算术运算，也能操作符号，这样就能证明数学命题。通过思考人类如何计算，他构造了一种假象的机器，这种机器现在被称为图灵机。图灵机后来成了电子计算机的蓝图。