1701065586
复杂 [:1701064735]
1701065587
第4章 计算
1701065588
1701065589
Quo facto， [49] quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas.Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere：Calculemus！（如果产生了争议，哲学家们用不着像会计师一样相互争执，他们只需要掏出纸和笔，然后说：来，演算一下。）
1701065590
1701065591
——莱布尼茨（转译自罗素译文）
1701065592
1701065593
在普通人眼里，计算就是计算机做的事情，电子表格、文档处理、电子邮件，诸如此类。计算机在人们脑海里就是台式电脑或笔记本，里面有电子电路，一般都带有显示器和鼠标，以前还流行用真空管。对于我们自己的大脑，我们也模糊地觉得有点像计算机，有逻辑演算、记忆存储和输入输出。
1701065594
1701065595
不过如果你读复杂系统方面的学术文献，你会发现计算这个词的用法蛮奇怪：“细胞和组织中的计算” [50] ；“免疫系统的计算” [51] ；“市场的分布式计算的本质和局限” [52] ；“植物中的涌现计算”。 [53] 这样的例子数不胜数。
1701065596
1701065597
自从计算机诞生以来，计算的概念已经走过了很长一段时间，现在许多科学家都将计算视为自然界中很普遍的现象。细胞、组织、植物、免疫系统和金融市场显然和计算机的运作方式不一样，那么他们说的计算到底是什么呢？他们又为什么要这样说呢？
1701065598
1701065599
在第12章我们会讨论这些问题，在此之前我们先了解一下计算思想的历史以及科学家用来理解自然界复杂系统的计算概念的基础。
1701065600
1701065601
复杂 [:1701064736]
1701065602
什么是计算？什么可以计算
1701065603
1701065604
香农的信息定义关注的是消息源的可预测性。不过在现实世界中，信息是用来分析并产生意义的东西，信息被存储，并和其他信息结合，产生结果或行为。总之，信息是用来计算的。
1701065605
1701065606
历史上计算的意义变化很大。直到20世纪40年代末，计算都是指手工进行数学运算（小学生称之为“做算术”）。计算员（Computer）就是做数学运算的人。我以前的老师伯克斯（Art Burks）常和我们说他娶的是“计算机”——指的是第二次世界大战时被征召入伍手工计算弹道的妇女，伯克斯的夫人在遇到他时正是这样一位计算员。
1701065607
1701065608
现在计算指的是各式各样的计算机干的事情，另外自然界的复杂系统似乎也干这个。但是计算到底是什么呢？它又能做些什么呢？计算机什么都能算吗？是不是存在原则上的局限性？这些问题都是在20世纪中叶才得到解决。
1701065609
1701065610
复杂 [:1701064737]
1701065611
希尔伯特问题和哥德尔定理
1701065612
1701065613
对计算的基础及其局限的研究，导致了电子计算机的发明，但其最初的根源却是为了解决一组抽象（而且深奥）的数学问题。这些问题是德国数学大师希尔伯特（David Hilbert，图4.1）于1900年在巴黎的国际数学家大会上提出来的。
1701065614
1701065615
希尔伯特在演讲中提出了世纪之交面临的23个亟待解决的数学问题。其中第2个和第10个问题在后来影响最大。实际上，它们不仅仅是数学内部的问题，它们还是关于数学本身以及数学能证明什么的问题。总的来说，这些问题可以分为三个部分：
1701065616
1701065617
1.数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或证否。
1701065618
1701065619
1701065620
1701065621
1701065622
▲图4.1 希尔伯特（1862—1943）（美国物理学会西格尔图像档案，兰德收藏）
1701065623
1701065624
举个例子，还记得中学几何里学过的欧几里得公理吧？记不记得用这些公理可以证明“三角形内角和为180度”这样的定理？希尔伯特的问题是：是不是有某个公理集可以证明所有真命题？
1701065625
1701065626
2.数学是不是一致的？换句话说，是不是可以证明的都是真命题？“真命题”是专业术语，但我在这里用的是直接意义。假如我们证出了假命题，例如1+1=3，数学就是不一致的，这样就会有大麻烦。
1701065627
1701065628
3.是不是所有命题都是数学可判定的？也就是说，是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假？这样你就可以提出一个数学命题，比如“所有比2大的偶数都可以表示为两个素数之和”，然后将它交给计算机，计算机就会用“明确程序”在有限时间内得出命题是“真”还是“假”的结论。
1701065629
1701065630
最后这个问题就是所谓的Entscheidungsproblem（“判定问题”），它可以追溯到17世纪的数学家莱布尼茨（Gottfried Leibniz）。莱布尼茨建造了他自己的计算机器，并且认为人类将建造出能判定所有数学命题真假的机器。
1701065631
1701065632
这三个问题过了30年都没有解决，不过希尔伯特很有信心，认为答案一定是“是”，并且还断言“不存在不可解的问题”。 [54]
1701065633
1701065634
然而他的乐观断言并没有维持太久，可以说非常短命。因为就在希尔伯特做出上述断言的同一次会议中，一位25岁的数学家宣布了对不完备性定理的证明，他的发现震惊了整个数学界，这位年轻人名叫哥德尔（Kurt G del，图4.2）。不完备性定理说的是，如果上面的问题2的答案是“是”（即数学是一致的），那么问题1（数学是不是完备的）的答案就必须是“否”。
1701065635