计算机是不是一门科学？

看到这个题目，相信每个读者都快速的在心里给了一个答案，抑或闪念一想，这个还有存在争议么？大家不妨花几分钟时间看完下面我讲的，同时也开启我们的计算机相关知识之旅。

八十年代末，Adobe的创始人约翰·沃诺克（John Warnock）被问及计算机科学是否是科学时断然说道，计算机当然不是科学，只是一门精彩纷呈且硕果累累的工程学科。那什么才算是科学呢？他认为，所谓科学就是提出假设，然后在现实世界中创建模型，通过各种实验得到真理。并反问：如果一定要说它是科学，那么计算机科学到底在追求什么样的真理呢？

作为标准电子文档格式PDF的鼻祖，沃诺克领导开发出了一个大大方便了人类学习的一个重要软件产品。在我眼里，Adobe是可以排在前十名的应用软件产品，沃诺克也是令人尊敬的IT大师。但我不完全认同他对计算机科学的认识，我认为计算机相关的各种研究形成了计算机科学，它们具备科学的重要特性。计算机科学里包含了大量对未知的探索研究，包含了对假设的验证工作。

计算机之所以有资格被称为科学的一个重要原因是它有一个扎实的理论基础。计算机理论主要有三个方面组成：可计算性理论、复杂性理论和计算机算法设计与分析。这让当代计算机所有应用领域都有了坚实的地基。

在其发展过程中，有两个人做出了巨大的贡献：一个是大家熟知的图灵（Alan Turing），计算机界的图灵奖等同于诺贝尔奖，可见其地位了。而另一位是大家不太熟悉，目前执教于加拿大多伦多大学的史提芬·古克（Stephen A. Cook），也是图灵奖的获得者。（以后我会介绍一些这两人的故事。）

图灵的工作提出并回答了可计算性的问题，他把世界上的问题分成了两类，一类是计算机可以解决的，也就是可计算的；一类是计算机不可解决的，也就是不可计算的。许多人以为计算机可以解决一切问题，其实不然。世界上有大量问题是计算机无法解决的。图灵在1936年证明了第一个不可计算的问题（文章发表于1937年）：停机问题。停机问题是个判定问题，对任何程序和给定的输入，这个程序是否会最终停止运行。图灵证明了能够判定这个问题的程序是不存在的，也就是说停机问题是不可计算的。

古克的研究则进一步探讨了了计算复杂性的问题，他的工作帮助我们回答了在实际应用中非常重要的问题：在可计算问题中，什么是容易解决的问题，什么是不容易解决的问题。古克用来度量难易的标准是找到最优答案计算机程序所需要花费的时间。例如在编写中国象棋程序时，计算机需要找出下一步棋如何走，可选答案很多，最优答案就是能够保证计算机最终获胜的一步。

大家公认的容易计算问题是找到最优答案的程序仅需要问题规模的多项式倍数的时间，比如我们可以很容易编制一个n个数的排序程序，仅需要n**2的步骤就可以将任意排列的n个数，转换成从小到大的序列。所以排序问题就是个简单问题。

如果找到最优答案需要问题规模的指数倍数的时间，那这个问题就被认为是复杂问题，因为随着问题规模的扩大，在可接受时间里计算机是算不出最优答案的。在现实生活中这类问题比比皆是，我们的解决方法往往是放弃找出最佳答案，而是通过编写一个启发式算法（heuristic algorithm），帮助我们找到一个接近最优的答案，而这个牺牲换来的是可接受的计算时间。如人类开发的下围棋的程序都属于启发式方法。

1985年我在杜克大学上计算机算法课时第一次系统了解了古克提出的P， NP， 和NP-Complete 的概念，感觉真是无比美妙，可以说第一次看到了计算机之美。他把问题的核心聚焦在两类问题的关系上：

–   P类问题：可以在确定（Deterministic）计算模式下，在问题规模的多项式（Polynomial）时间范围内找到问题的最优答案。

–   NP类问题：可以在不确定（Non-deterministic）计算模式下，在问题规模的多项式（ Polynomial）时间范围内找到问题的最优答案。

不确定计算模式的计算能力大大高于确定式计算模式，所以很明显，P是NP的子集。但NP是否大于P？换句话说，是否有一个问题属于NP，但不属于P，至今没有可证明的答案，虽然绝大多数人都认为NP大于P。如果我们说哥德巴赫猜想是数学的皇冠的话，毫无疑问，P和NP的关系问题则是计算机科学的皇冠。 解决这个问题的关键是NP中的一些特殊问题，所谓NP完全（NP- Complete）问题。只要你能证明任何一个NP完全问题可以在确定模式下在问题规模的多项式时间（Polynomial）范围内解决，你已经成功证明P=NP。如果你能证明任何一个NP完全问题至少需要问题规模的指数时间范围内解决，你成功证明了P≠NP。 目前我们已经找到了成千上万的NP完全问题。

P和NP关系问题被列为克莱基金千年问题之一（http://www.claymath.org/millennium-problems/p-vs-np-problem），解决者将获得1百万美金的奖励。同时我相信解决者也一定是下一届图灵奖（计算机的诺贝尔奖）获得者。

绝大多数计算机工作者不会直接介入到可计算性及复杂度的理论研究中去，但大部分程序员都会直接或间接做一些计算机算法的设计和分析。当问到计算机编程最困难的部分是什么时，比尔·盖茨说：“最困难部分是确定采用什么算法。”

计算机理论让计算机站在了一个坚实的基础之上，从而让计算机成为一门科学。

写完给周边的朋友一读，发现能快速读懂的少之又少。非计算机专业或者数学专业的读者理解起来确实不容易，在我长期执教研究生时也发现，这是难教难读的概念。连例子都找不到简单的。不管怎样，大家有个基本印象，计算机是门科学就好，也不枉费我费力码这些字了。