0.1　算法的作用

首先让我们了解一下计算机科学最基础的概念——“算法”。一般来讲，算法（algorithm）是完成一项任务所遵循的一系列步骤。（在第5章，我们将给出比较精确的定义。）例如，有关于烹饪的算法（称为菜谱），有在陌生城市准确寻找道路的算法（通常称为道路指南），有使用洗衣机的算法（通常标示在洗衣机盖子的内侧或者贴在自助洗衣店的墙上），有演奏音乐的算法（以乐谱的形式表示），还有魔术表演的算法（见图0-1）。

图0-1　一个魔术的算法

在机器（如计算机）执行一项任务之前，必须先找到完成这项任务的算法，并用与该机器兼容的形式表示出来。算法的表示称作程序（program）。为了人们读写方便，计算机程序通常打印在纸上或者显示在计算机屏幕上。为了便于机器识别，程序需要以一种与该机器技术兼容的形式进行编码。开发程序、采取与机器兼容的形式进行编码并将其输入机器中的过程，称作程序设计/编程（programming），有时也称作编码（coding）。程序及其所表示的算法统称为软件（software），而机械本身称为硬件（hardware）。

算法的研究起源于数学学科。事实也的确如此，探寻算法是数学家的重要活动，远远早于当今计算机的出现。它的目标是找出一组指令，描述如何解决某一特定类型的所有问题。求解两个多位数商的长除算法是早期研究中一个最著名的例子。另一个例子是古希腊数学家欧几里得发现的欧几里得算法——求两个正整数的最大公约数（见图0-2）。

图0-2　求两个正整数的最大公约数的欧几里得算法

一旦我们找到执行任务的算法，执行该任务时就不再需要了解该算法所依据的原理——任务的执行简化成了遵照指令操作的过程。（我们可以在不了解算法原理的情况下，根据长除算法求商或者根据欧几里得算法求最大公约数。）在某种意义上，解决这个问题的智能被编码到了算法中。

通过算法来捕获和传达智能（至少是智能行为），我们能够构建出执行有用任务的机器。因此，机器展现出来的智能水平受限于算法所传达的智能。只有存在执行某一项任务的算法时，我们才可以制造出执行这一任务的机器。换言之，如果我们找不到解决某问题的算法，机器就解决不了这个问题。

20世纪30年代，库尔特·哥德尔（Kurt Gödel）发表了不完备性定理的论文，它使确定算法能力的局限性成为数学学科的一个研究课题。这个定理实质上阐述的是，在任何一个包括传统意义的算术系统的数学理论内，总有一些命题的真伪无法通过算法的手段来确定。简言之，对算术系统的任何全面研究都超越了算法活动的能力范围。这一认识动摇了数学的基础，于是关于算法能力的研究随之而来，它开创了今天的计算机科学这门学科。的确，正是算法的研究构成了计算机科学的核心。