1.1.3　計算的需要及其局限性

幾乎在整個歷史進程中，人類都主要是依靠大腦來進行計算的。分析一下采用紙和筆進行手工計算的過程，如圖1.1所示。紙相當于存儲部件，其基本目的是信息存儲。在紙上的信息，可以包括進行計算時應當遵循的一系列指令（即算法和程序），以及所用的數據，計算過程的中間結果和最終結果都記錄在紙上，必要的計算過程在大腦中進行，大腦可以被稱為處理器，完成兩種主要功能：控制功能（即解釋指令并保證以正確的順序執行）和執行功能即進行諸如加法、減法、乘法和除法等具體的計算）。但是，隨著計算的規模和復雜程度的不斷增長，這種計算存在著嚴重的不足：計算速度有限，計算容易出錯。因此，人類借助于計算機來完成更快、更精確、更復雜的計算，其計算過程如圖1.2所示。這里，存儲部件（M）相當于手工計算所用的紙，用來存放指令和數據；中央處理部件（CPU）由程序控制部件（PCU）和算術邏輯部件（ALU）構成，相當于人的大腦，程序控制部件解釋指令并按順序排好，算術邏輯部件執行指令。比較手工計算和借助計算機計算的過程，人們不難發現，其最顯著的差別是信息的表示方式不同。人類使用的是有著大量符號的正常語言，通常又以十進制的形式表示數。而在計算機中，信息的存儲和處理均以二進制形式進行，只用0和1兩個符號表示。為了在機器和用戶之間提供通信，就需要在計算機語言與人類語言之間提供信息轉換的手段，這就是圖1.2中輸入/輸出（I/O）設備的主要功能。

通過上述分析，可以把計算理解為求某個函數f（x）的值，這里x是給予的輸入數據，z=f（x）是要求輸出的數據。x，z，f均可給予廣泛的解釋，x，z可以代表數、詞句、信息文件等等，f可以是數值計算、定理證明、文件更新規程等等。為了用一特定計算機求f（x），必須能將f表達成一串函數f1，f2，…，n，這些函數可以由計算機指令系統來確定。指令系統就是計算機能夠執行基本功能的集合。f1，f2，…，fn就可以理解為對f（x）求值的程序。基本操作的序列：

y1=f2（x）

y2=f3（x）

?

yn-2=fn-1（x）

z=fn（yn-1）

可以作為計算的一個形式定義。

那么，所有的問題是否都可以計算呢？

1936年，英國數學家圖靈提出了計算機抽象模型——Turing機。人們在對Turing機研究的基礎上，得到了如下的概念和認識：

①任何給定的x，如果f（x）可以由Turing機在有限步內完成計算，則稱函數是有效的或可計算的。實際上，很多計算機應用問題都是可計算的。

②存在不可計算的函數。例如，沒有經驗的程序員可能會編出一個在一定輸入條件下無法停止的程序。又如，編寫一個能測定任何程序是否停止的調試程序，這幾乎是不可能的，因為只有當這個程序應用到全部可能的程序類時，這個說法才成立。這兩個問題都屬于不可解問題或不可計算的。

③即使問題是可解的，但也有難處理的或不現實的。例如，計算機不能實現任意大的二進制數的乘法計算。有大量的“困難”問題在實際中很重要，但在計算過程中其需要的存儲空間太大以及計算時間太長，以致沒有一臺實際的計算機能夠解它們。這樣的結論，實際上是基于下面兩個理由：一是計算機不可能存放所有可能的問題的答案；二是計算機處理信息的速度是有限的。

例如，Hanoi塔問題。在一個基座上豎立著3根軸A，B和C，軸A上套著n（n=64）個圓盤，按直徑的遞減順序由下而上疊放在一起，如圖1.3所示。要求一次一個地把這些圓盤從A移到B，但在任何情況下都不允許把大的圓盤疊放在小的圓盤上面，在移動過程中可以借助C軸來暫時存放圓盤。

這個移動過程是一個規模為n個圓盤的移動，可以進一步分解為規模為兩次n-1的移動和一次規模為1個圓盤的移動，而每個規模為n-1的移動規則與規模為n的移動規則相同。移動過程可以描述為如下算法：

這個過程實際上是一個遞歸算法，用數學歸納法不難證明這個算法的正確性。但這里關心的是計算機是否能夠解決一個任意大小的n的Hanoi塔問題。為了回答這個問題，不妨把上面的移動過程中的移動次數表示為如下的遞歸方程：

然后解這個遞歸方程，可以得到移動次數為：

T（n）=2×T（n-1）+1

=2×（2×T（n-2）+1）+1

=22×（2×T（n-3）+1）+21+20

=23×T（n-3）+22+21+20

…

=2n-1+2n-2+…+22+21+20

=2n-1-1

通過計算可得，64個盤的移動次數為：264-1=18446744073709551615次。假設一臺計算機1μs可移動一次圓盤.那么把這個算法轉換成計算機程序來完成移動64個圓盤所需的時間將近60萬年。

顯然Hanoi塔問題雖然有解決算法，但是屬于難解問題，即使計算機的速度由于技術的改進有所增長，解決類似問題仍然存在著局限性。

這就給出一個啟示，單純依靠提高計算機的速度是不能從根本上解決這類問題。也就是說，在運用計算機解決實際問題的過程中，不僅要考慮計算機硬件技術的應用，更重要的是要考慮計算機軟件方面的技術方法和過程的應用，應該從系統的角度考慮問題解決的途徑。