我们为什么要学习计算理论

在所有我看过的计算理论、可计算性、计算复杂度的教材中，Sipser的这本Introduction to the Theory of Computation是最适合入门的。把计算理论这么个艰深的学问讲解得清晰简洁，直观易懂。而且涵盖了计算理论的各个经典内容。作为一本introduction，真是再好不过了。

计算理论这门学问，顾名思义，就是把“计算”(computation)这个抽象的现象作为我们的研究对象，用数学工具来分析和刻画，并为此而建立的理论体系。

全书分为三部分：自动机；可计算性；复杂度。这刚好是计算的三个不同的方面：计算的模型；计算的界限；计算的代价。自动机理论抽象的描述了什么叫“问题”，什么叫“解”，计算的机制可以有什么样的形式。可计算性关注的是计算的“行不行”的一面。而复杂度关注的是“好不好”的一面、也即问题的“难”和“易”。

什么是计算机？什么可以被计算？什么样的问题是难的、什么样的问题是容易的？这些计算机科学最自然最根本的问题，是计算理论这门学问的主题，也是这本书的主题。

这本书最美妙之处，并不在于它描述的那些艰深的问题和结果，而是它全面展示了计算理论中那些最引人入胜的深刻想法(idea)：抽象问题(problems)的形式语言(formal languages)描述，确定性(deterministic)和非确定性(nondeterministic)的引入，对角化(diagonalization)和停机(halting)问题，归约(reduction)的思想，完全性(completeness)，relativization，alternation。

这些都是计算理论中最具创造性的划时代的思想。这些不仅仅是单纯的研究结果，这些idea的出现更是影响了人类今天对计算这个现象的根本认识。

唯一的小缺憾就是，应该在最后一章advanced topics里面，去掉parallel computation，加上communication complexity和著名的PCP (probabilistically checkable proofs)。

很高兴能有这么一本书，收集了这些璀璨珍珠，清楚的呈现给我们。


然而，尽管我对这本书和这门学问都很推崇，我对于学习计算理论的必要性却并不坚定。我自己喜欢这些，可我该如何向别人解释学习它是必要的？

Sipser在前言中也试图说明这个问题:"After all, isn't theory arcane, boring, and worst of all, irrelevant?"
他很认真的试图从几个方面说服学生，计算理论是“有用”的，但我总觉得这些说服很徒劳：书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。

看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。

我能想到的理由就只剩两个：
（一）这些是计算机科学的根本，没有它们计算机科学不能算作是个正经学问，因此，一个自称计算机科学专业的人，应当知道这些。
（二）这些是美好的，值得在短暂的人生中去经历去见识。

我觉得这已是足够的理由了。