0.1　算法的作用

首先讓我們了解一下計算機科學最基礎的概念——“算法”。一般來講，算法（algorithm）是完成一項任務所遵循的一系列步驟。（在第5章，我們將給出比較精確的定義。）例如，有關于烹飪的算法（稱為菜譜），有在陌生城市準確尋找道路的算法（通常稱為道路指南），有使用洗衣機的算法（通常標示在洗衣機蓋子的內側或者貼在自助洗衣店的墻上），有演奏音樂的算法（以樂譜的形式表示），還有魔術表演的算法（見圖0-1）。

圖0-1　一個魔術的算法

在機器（如計算機）執行一項任務之前，必須先找到完成這項任務的算法，并用與該機器兼容的形式表示出來。算法的表示稱作程序（program）。為了人們讀寫方便，計算機程序通常打印在紙上或者顯示在計算機屏幕上。為了便于機器識別，程序需要以一種與該機器技術兼容的形式進行編碼。開發程序、采取與機器兼容的形式進行編碼并將其輸入機器中的過程，稱作程序設計/編程（programming），有時也稱作編碼（coding）。程序及其所表示的算法統稱為軟件（software），而機械本身稱為硬件（hardware）。

算法的研究起源于數學學科。事實也的確如此，探尋算法是數學家的重要活動，遠遠早于當今計算機的出現。它的目標是找出一組指令，描述如何解決某一特定類型的所有問題。求解兩個多位數商的長除算法是早期研究中一個最著名的例子。另一個例子是古希臘數學家歐幾里得發現的歐幾里得算法——求兩個正整數的最大公約數（見圖0-2）。

圖0-2　求兩個正整數的最大公約數的歐幾里得算法

一旦我們找到執行任務的算法，執行該任務時就不再需要了解該算法所依據的原理——任務的執行簡化成了遵照指令操作的過程。（我們可以在不了解算法原理的情況下，根據長除算法求商或者根據歐幾里得算法求最大公約數。）在某種意義上，解決這個問題的智能被編碼到了算法中。

通過算法來捕獲和傳達智能（至少是智能行為），我們能夠構建出執行有用任務的機器。因此，機器展現出來的智能水平受限于算法所傳達的智能。只有存在執行某一項任務的算法時，我們才可以制造出執行這一任務的機器。換言之，如果我們找不到解決某問題的算法，機器就解決不了這個問題。

20世紀30年代，庫爾特·哥德爾（Kurt G?del）發表了不完備性定理的論文，它使確定算法能力的局限性成為數學學科的一個研究課題。這個定理實質上闡述的是，在任何一個包括傳統意義的算術系統的數學理論內，總有一些命題的真偽無法通過算法的手段來確定。簡言之，對算術系統的任何全面研究都超越了算法活動的能力范圍。這一認識動搖了數學的基礎，于是關于算法能力的研究隨之而來，它開創了今天的計算機科學這門學科。的確，正是算法的研究構成了計算機科學的核心。