洪加威走向世界（下）

洪加威走向世界（下）：为了说明洪加威这篇论文究竟有什么重大意义，我们还要从图灵论题谈起。千百年来，数学家们都确信这样一个事实，凡是正确的数学命题，就一定能找到证明的方法。然而，德国数学家哥德尔在1931 年发表了一篇爆炸性的论文，它证明了有些正确的数学命题是不可以被证明的。这个结论把一个重要的数学难题摆在了人们的面前：怎样判断一类数学问题是机械可解的，或者说能通过有限的固定步骤得到解决？正当许多大数学家一筹莫展之时，英国一位24 岁的数学家图灵异想天开地搬出了一种“理想计算机”，并且说，凡我这台计算机能算出的，就是可计算的，凡我这台计算机算不出的，就是不可计算的。这就是赫赫有名的“图灵机”。那么是不是一切判断能否计算问题非要在图灵机上定义，用别的计算模型就不能定义呢？接着，图灵提出了这样一个论题：只要在一个模型下可以计算，那末在别的“合理”的模型下也可以计算，你能算的我也能算，你不能算的我也无可奈何。这便是日后被称为计算机科学基石的图灵论题。

然而，图灵只考虑任何数学问题在理论上是否可计算，却没有研究实际当中能否计算的问题。换句话说，即使现代最快的计算机，也仍得考虑时间的因素。举个例子来说，写出26 个英文字母的全部排列，即使一架机器每秒能写一亿个排列，也需要好几亿年才能完成。由此可见，计算问题光考虑能否计算还不行，还得讲点“效率”，这便是当今计算理论界最热门的复杂性问题。

洪加威刚刚跨入这个领域时，正值理论界群星荟萃，百家争鸣的年月。许多有名望的学者都在不同侧面、具体问题上探索着复杂性理论。他没有把精力耗费在别人的成果上做些添枝加叶的工作，而是以高屋建瓴之势，洞察到了复杂性理论关键问题的所在。他把图灵论题推进了一大步，提出了这个轰动理论界的相似性原理。这个原理指出：不但各合理模型能否计算的问题是一样的，而且计算模型所用到的三种资源：并行时间，串行时间及存储空间在本质上一样多。它表明，不仅计算的可能性是客观实在，而且计算的复杂性也是一种客观实在。

“会当凌绝顶，一览众山小”。作为一个出色的科学家，不仅需要有滴水穿石般积累起来的扎实功底，更需要具有那种能透过具体问题，观其大略、扭转乾坤的气魄。相似性原理不仅统一了所有的计算模型，而且统一了所有的计算类型。因而它已成为现代复杂性理论中的重要的基础工作之一。加拿大多伦多大学计算机科学系主任鲍罗廷写给我国有关负责人的信中说：“洪加威的论文是质量很高的研究篇章。我认识到，这些论文对我的思路和我的同事柯克教授和拉道夫教授的思路都产生了影响……洪加威已成为对我们系做出巨大贡献的人。”