# 計算能力

雖然通用電腦可以做任何計算裝置所能計算的事物,但還是有它無法計算的東西,像是定義含糊籠統的問題,實際上我們很少遇到不可計算的問題,因為要找一個定義周詳且大家都想解決的不可計算的問題非常困難,終止問題(halting problem)就是這樣的一個罕見例子.假設我要寫一個電腦程式,用它來檢驗另一個程式最後是否會終止,若被檢驗的程式不包含任何迴圈或遞迴結構,則它最後一定會結束,但若它包含了迴圈或遞迴結構,則程式可能會一直執行下去,因此還是找不到可以檢驗某個程式是否會落入無窮循環的演算法.終止問題是個不可計算的問題.

杜林憑空想像出來的終止問題是不可計算問題的典範,現實中所發生的大部分不可計算的問題都和他一樣或類似.但無法解決終止問題並不能說是電腦的弱點,因為終止問題本來就是不可解的,也就是說沒有一部可以解決終止問題的機器.到目前為止,就我們所了解,沒有任何東西能執行通用電腦所不能執行的計算,數位電腦所能計算的問題顯然也包括任何計算裝置能夠計算的問題.最後這段敘述也稱為邱奇論題(Church thesis),它以與杜林同時期的學者邱奇(Alonzo Church)為名.關於計算及邏輯問題研究,數學家已經討論好幾個世紀了,但科學史上最令人讚嘆的同步學術研究之ㄧ就是杜林 邱奇及波斯特(Emil Post)幾乎同時提出通用計算的觀念.他們的描述方式迴異,但都在1937年發表這些結果,也為以後的計算機革命奠定基礎.

另一個與終止問題很相近的不可計算函數,就是要決定某個已知的數學陳述是真或假的問題.就在杜林提出終止問題不久前,1931年,歌爾德以其不完全定理證明了這個問題亦沒有演算法可解.歌爾德的定理提到,在嚴謹而有效的數學系統中,存在一些無法證明真假的陳述,數學家以證明或反證陳述真假為職責,而歌爾德卻證明他們在某些情況下無法履行這個[職責].

有些數學家及哲學家認為歌爾德的不完全定理是近乎神秘,不可思議的論調,少部分的人則認為,這個定理證明了人類的直覺終究勝過電腦,也就是說人類或許可以用[直覺]來判斷電腦無法證明的問題.這是一種感情上的爭議,對那些不喜歡和電腦相提並論的哲學家而言,反而成為他們的把柄.但這種事是荒謬的,不論人類是否一瞬間以直覺勝過電腦,從歌爾德的不完全定理來看,我們沒有理由相信世界上存在著任何數學家可以證明但電腦無法證明的數學陳述.據我們目前所知,任何人類所能證明的理論,電腦也可以證明,然而,人類無法計算那些電腦無法解決的不可計算問題.

雖然人類絞盡腦汁才提出一些不可計算問題的例子,但我們卻可以輕易的證明大部分的數學函數是不可計算的.因為任何程式都能以有限個位元表示,而描述一個函數通常都要無限多個位元,因此函數數目要比程式多得多.

函數是什麼?Ex.餘弦或自然對數.數學家可以定義出各類怪異的函數,不一定有其用處,但在數學家眼中,仍是一個合理的函數,因為它能將任一數值完全轉換成另一個數值.

我們可以用數學方式證明函數的個數無限多於程式個數,因此,對大部分的函數而言,都沒有相對應的程式可以計算,若要確實計算出它們的個數相當的困難(包括計算無限多個數,還要分辨不同程度的無限),但結論是正確的,就統計的觀點來說,絕大部分的數學函數都是不可計算的.幸運的是,幾乎所有的不可計算函數都沒什麼用處,事實上所有我們想用來計算的函數都是可計算的.