在普通人眼里，計算就是計算機做的事情，電子表格、文檔處理、電子郵件，諸如此類。計算機在人們腦海里就是臺式電腦或筆記本，里面有電子電路，一般都帶有顯示器和鼠標，以前還流行用真空管。對于我們自己的大腦，我們也模模糊糊覺得有點像計算機，有邏輯演算、記憶存儲和輸入輸出。

自從計算機誕生以來，計算的概念已經走過了很長一段時間，現(xiàn)在許多科學家都將計算視為自然界中很普遍的現(xiàn)象。細胞、組織、植物、免疫系統(tǒng)和金融市場顯然和計算機的運作方式不一樣，那么他們說的計算到底是什么呢？他們又為什么要這樣說呢？

什么是計算？什么可以計算？

香農的信息定義關注的是消息源的可預測性。不過在現(xiàn)實世界中，信息是用來分析并產生意義的東西，信息被存儲，并和其它信息結合，產生結果或行為。總之，信息是用來計算的。

歷史上計算的意義變化很大。直到20世紀40年代末，計算都是指的手工進行數(shù)學運算（小學生稱之為“做算術”）。計算員（Computer）就是做數(shù)學運算的人。我以前的老師伯克斯（Art Burks）常和我們說他娶的是“計算機”——指的是二戰(zhàn)時被征召入伍手工計算彈道的婦女，伯克斯的夫人在遇到他時正是這樣一位計算員。

現(xiàn)在計算指的是各種各樣的計算機干的事情，另外自然界的復雜系統(tǒng)似乎也干這個。但是計算到底是什么呢？它又能做些什么呢？計算機什么都能算嗎？是不是存在原則上的局限性？這些問題都是在20世紀中葉才得到解決。

希爾伯特問題和哥德爾定理

對計算的基礎及其局限的研究，導致了電子計算機的發(fā)明，但其最初的根源卻是為了解決一組抽象（而且深奧）的數(shù)學問題。這些問題是德國數(shù)學大師希爾伯特（David

Hilbert）于1900年在巴黎的國際數(shù)學家大會上提出來的。

希爾伯特，1862–1943（美國物理學會西格爾圖像檔案，蘭德收藏）

（AIP Emilio Segre

Visual Archives, Lande Collection）

希爾伯特在演講中提出了在世紀之交面臨的23個丞待解決的數(shù)學問題。其中第2和第10問題后來影響最大。實際上，它們不僅僅是數(shù)學內部的問題；它們是關于數(shù)學本身以及數(shù)學能證明什么的問題?？偟膩碚f，這些問題可以分為三個部分：

1數(shù)學是不是完備的？

也就是說，是不是所有數(shù)學命題都可以用一組有限的公理證明或證否。

舉個例子，還記得中學幾何里學過的歐幾里得公理吧？記不記得用這些公理可以證明“三角形內角和為180度”這樣的定理？希爾伯特的問題是：是不是有某個公理集可以證明所有真命題？

2數(shù)學是不是一致的？

換句話說，是不是可以證明的都是真命題？“真命題”是專業(yè)術語，但我在這里用的是直接意義。假如我們證出了假命題，例如1+1=3，數(shù)學就是不一致的，這樣就會有大麻煩。

3是不是所有命題都是數(shù)學可判定的？

也就是說，是不是對所有命題都有明確程序（definite procedure）可以在有限時間內告訴我們命題是真是假？這樣你就可以提出一個數(shù)學命題，比如“所有比2大的偶數(shù)都可以表示為兩個素數(shù)之和，”然后將它交給計算機，計算機就會用“明確程序”在有限時間里得出命題是“真”還是“假”的結論。

最后這個問題就是所謂的Entscheidungsproblem（“判定問題”），它可以追溯到17世紀的數(shù)學家萊布尼茨（Gottfried Leibniz）。萊布尼茨建造了他自己的計算機器，并且認為人類將建造出能判定所有數(shù)學命題真假的機器。

這三個問題過了30年都沒有解決，不過希爾伯特很有信心，認為答案一定是“是，”并且還斷言“不存在不可解的問題?！?/p>

然而他的樂觀斷言并沒有維持太久?？梢哉f非常短命。因為就在希爾伯特做出上述斷言的同一次會議中，一位25歲的數(shù)學家宣布了對不完備性定理的證明，他的發(fā)現(xiàn)震驚了整個數(shù)學界，這位年輕人名叫哥德爾（Kurt G?del）。不完備性定理說的是，如果上面的問題2的答案是“是”（即數(shù)學是一致的），那么問題1（數(shù)學是不是完備的）的答案就必須是“否?！?/p>

哥德爾，1906-1978（照片由普林斯頓大學圖書館提供）

哥德爾的不完備性定理是從算術著手。他證明，如果算術是一致的，那么在算術中必然存在無法被證明的真命題——也就是說，算術是不完備的。而如果算術是不一致的，那么就會存在能被證明的假命題，這樣整個數(shù)學都會崩塌。

哥德爾的證明很復雜。不過直觀上卻很容易解釋。哥德爾給出了一個數(shù)學命題，翻譯成白話就是“這個命題是不可證的?！?/p>

仔細思考一下。這個命題很奇怪，它居然談論的是它自身——事實上，它說的是它不可證。我們姑且稱它為“命題A?！爆F(xiàn)在假設命題A可證。那么這樣它就為假（因為它說它不可證）。這就意味著證明了假命題——從而算術是不一致的。好了，那我們就假設它命題A不可證。這就意味著命題A為真（因為它斷言的就是自己不可證），但這樣就存在不可證的真命題——算術是不完備的。因此，算術要么不一致，要么不完備。

難以想象這個命題如何轉換成用數(shù)學語言表述，但是哥德爾做到了——哥德爾的證明的復雜和精彩之處就在此，在這里我們不去討論。

絕大多數(shù)數(shù)學家和哲學家都堅定地認為希爾伯特問題能被正面解決，這對他們是個沉重的打擊。就像數(shù)學作家霍吉斯（Andrew Hodges）說的：“這是在研究中驚人的轉折，因為希爾伯特曾以為他的計劃將一統(tǒng)天下。對于那些認為數(shù)學完美而且無懈可擊的人來說，這讓人難以接受……”

圖靈機和不可計算性

哥德爾干凈利落地解決了希爾伯特第一和第二問題，接著第三問題又被英國數(shù)學家圖靈（Alan Turing）干掉了。

圖靈，1912-1954

1935年，圖靈23歲，在劍橋跟隨邏輯學家紐曼（Max Newman）攻讀研究生。紐曼向圖靈介紹了哥德爾剛剛得出的不完備性定理。在理解哥德爾的結果之后，圖靈發(fā)現(xiàn)了該如何解決希爾伯特第三問題，判定問題，同樣，他的答案也是“否?！?/p>

圖靈是怎么證明的呢？前面說過，判定問題問的是，是不是有“明確程序”能判定任意命題是否可證？“明確程序”指的是什么呢？圖靈的第一步就是定義這個概念。沿著萊布尼茨在兩個世紀以前的思路，圖靈通過構想一種強有力的運算機器來闡述他的定義，這個機器不僅能進行算術運算，也能操作符號，這樣就能證明數(shù)學命題。通過思考人類如何計算，他構造了一種假象的機器，這種機器現(xiàn)在被稱為圖靈機。圖靈機后來成了電子計算機的藍圖。

?本文摘自第一推動叢書《復雜》（梅拉妮·米歇爾）第四章 計算