数学与计算机科学

张泽玲

计算机中的“计算”二字，已经显而易见地表示出了数学与计算机科学的关系。但计算机中的数学理论，并不只是加减乘除这些算术这么简单。比如，计算机的模型基础就是名为“图灵机”的自动机。计算机科学理论中另外一种有趣的自动机模型，则是跟自然界很多生物行为现象相关的元胞自动机。

严格来说，元胞自动机是一种时空离散的局部动力学模型，它是一种通用性的建模方法，在社会和自然科学的各个领域几乎都会见到它。元胞自动机会按照一定的规则进行演化，比如从一个简单的起点出发，利用一组规则，就能生成一套复杂无尽的花紋;在生物世界中，当设定好初始状态和进化规则后，单细胞生物便会依据规则在离散的时间步上进行演化。

图灵机

这是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。这种机器只是一个虚拟的理想设备，图灵认为这样的一台机器能模拟人类所能进行的任何计算过程。

计算机理论基础中，判断一类计算是否能用计算机在有限时间内解决，靠的也是数学证明。比如著名的旅行销售员问题，内容是求解一个销售员走遍每个城市的最短总路径，本质上是一个还未解决的数学问题。因为虽然目前计算机已经有了可以求解这个问题的办法，但耗时都非常多，数学理论则试图证明，这类问题用计算机是真的有更快的解法，还是确实无法找到更快的方法。（这个问题被简化为“证明NP=P”，在计算机科学理论里的地位相当于数学里的“哥德巴赫猜想”。）

除此之外，不仅仅是数学影响着计算机科学，计算机作为人类强大的帮手，也在影响着数学。比如四色定理，就是靠计算机来辅助证明的。