在普通人眼里庙楚，計算就是計算機做的事情上荡，電子表格、文檔處理、電子郵件酪捡，諸如此類叁征。計算機在人們腦海里就是臺式電腦或筆記本，里面有電子電路逛薇，一般都帶有顯示器和鼠標捺疼，以前還流行用真空管。對于我們自己的大腦永罚，我們也模模糊糊覺得有點像計算機啤呼，有邏輯演算、記憶存儲和輸入輸出呢袱。
自從計算機誕生以來官扣，計算的概念已經(jīng)走過了很長一段時間，現(xiàn)在許多科學家都將計算視為自然界中很普遍的現(xiàn)象产捞。細胞醇锚、組織、植物坯临、免疫系統(tǒng)和金融市場顯然和計算機的運作方式不一樣，那么他們說的計算到底是什么呢恋昼？他們又為什么要這樣說呢看靠？
什么是計算？什么可以計算液肌？
香農(nóng)的信息定義關(guān)注的是消息源的可預測性挟炬。不過在現(xiàn)實世界中，信息是用來分析并產(chǎn)生意義的東西嗦哆，信息被存儲谤祖，并和其它信息結(jié)合，產(chǎn)生結(jié)果或行為老速≈嘞玻總之，信息是用來計算的橘券。
歷史上計算的意義變化很大额湘。直到20世紀40年代末，計算都是指的手工進行數(shù)學運算（小學生稱之為“做算術(shù)”）旁舰。計算員（Computer）就是做數(shù)學運算的人锋华。我以前的老師伯克斯（Art Burks）常和我們說他娶的是“計算機”——指的是二戰(zhàn)時被征召入伍手工計算彈道的婦女，伯克斯的夫人在遇到他時正是這樣一位計算員箭窜。
現(xiàn)在計算指的是各種各樣的計算機干的事情毯焕，另外自然界的復雜系統(tǒng)似乎也干這個。但是計算到底是什么呢磺樱？它又能做些什么呢纳猫？計算機什么都能算嗎婆咸？是不是存在原則上的局限性？這些問題都是在20世紀中葉才得到解決续担。
希爾伯特問題和哥德爾定理
對計算的基礎(chǔ)及其局限的研究擅耽，導致了電子計算機的發(fā)明，但其最初的根源卻是為了解決一組抽象（而且深奧）的數(shù)學問題物遇。這些問題是德國數(shù)學大師希爾伯特（David
Hilbert）于1900年在巴黎的國際數(shù)學家大會上提出來的乖仇。
希爾伯特，1862–1943（美國物理學會西格爾圖像檔案询兴，蘭德收藏）
（AIP Emilio Segre
Visual Archives, Lande Collection）
希爾伯特在演講中提出了在世紀之交面臨的23個丞待解決的數(shù)學問題乃沙。其中第2和第10問題后來影響最大。實際上诗舰，它們不僅僅是數(shù)學內(nèi)部的問題警儒；它們是關(guān)于數(shù)學本身以及數(shù)學能證明什么的問題】舾總的來說蜀铲，這些問題可以分為三個部分：
1數(shù)學是不是完備的？
也就是說属百，是不是所有數(shù)學命題都可以用一組有限的公理證明或證否记劝。
舉個例子，還記得中學幾何里學過的歐幾里得公理吧族扰？記不記得用這些公理可以證明“三角形內(nèi)角和為180度”這樣的定理厌丑？希爾伯特的問題是：是不是有某個公理集可以證明所有真命題？
2數(shù)學是不是一致的渔呵？
換句話說怒竿，是不是可以證明的都是真命題？“真命題”是專業(yè)術(shù)語扩氢，但我在這里用的是直接意義耕驰。假如我們證出了假命題，例如1+1=3类茂，數(shù)學就是不一致的耍属，這樣就會有大麻煩。
3是不是所有命題都是數(shù)學可判定的巩检？
也就是說厚骗，是不是對所有命題都有明確程序（definite procedure）可以在有限時間內(nèi)告訴我們命題是真是假？這樣你就可以提出一個數(shù)學命題兢哭，比如“所有比2大的偶數(shù)都可以表示為兩個素數(shù)之和领舰，”然后將它交給計算機，計算機就會用“明確程序”在有限時間里得出命題是“真”還是“假”的結(jié)論。
最后這個問題就是所謂的Entscheidungsproblem（“判定問題”）冲秽，它可以追溯到17世紀的數(shù)學家萊布尼茨（Gottfried Leibniz）舍咖。萊布尼茨建造了他自己的計算機器，并且認為人類將建造出能判定所有數(shù)學命題真假的機器锉桑。
這三個問題過了30年都沒有解決排霉，不過希爾伯特很有信心，認為答案一定是“是民轴，”并且還斷言“不存在不可解的問題攻柠。”
然而他的樂觀斷言并沒有維持太久后裸」迮ィ可以說非常短命。因為就在希爾伯特做出上述斷言的同一次會議中微驶，一位25歲的數(shù)學家宣布了對不完備性定理的證明浪谴，他的發(fā)現(xiàn)震驚了整個數(shù)學界，這位年輕人名叫哥德爾（Kurt G?del）因苹。不完備性定理說的是苟耻，如果上面的問題2的答案是“是”（即數(shù)學是一致的），那么問題1（數(shù)學是不是完備的）的答案就必須是“否扶檐×撼剩”
哥德爾，1906-1978（照片由普林斯頓大學圖書館提供）
哥德爾的不完備性定理是從算術(shù)著手蘸秘。他證明，如果算術(shù)是一致的蝗茁，那么在算術(shù)中必然存在無法被證明的真命題——也就是說醋虏，算術(shù)是不完備的。而如果算術(shù)是不一致的哮翘，那么就會存在能被證明的假命題颈嚼，這樣整個數(shù)學都會崩塌。
哥德爾的證明很復雜饭寺。不過直觀上卻很容易解釋阻课。哥德爾給出了一個數(shù)學命題，翻譯成白話就是“這個命題是不可證的艰匙∠奚罚”
仔細思考一下。這個命題很奇怪员凝，它居然談論的是它自身——事實上署驻，它說的是它不可證。我們姑且稱它為“命題A⊥希”現(xiàn)在假設(shè)命題A可證瓶蚂。那么這樣它就為假（因為它說它不可證）。這就意味著證明了假命題——從而算術(shù)是不一致的宣吱。好了窃这，那我們就假設(shè)它命題A不可證。這就意味著命題A為真（因為它斷言的就是自己不可證）征候，但這樣就存在不可證的真命題——算術(shù)是不完備的杭攻。因此，算術(shù)要么不一致倍奢，要么不完備朴上。
難以想象這個命題如何轉(zhuǎn)換成用數(shù)學語言表述，但是哥德爾做到了——哥德爾的證明的復雜和精彩之處就在此卒煞，在這里我們不去討論痪宰。
絕大多數(shù)數(shù)學家和哲學家都堅定地認為希爾伯特問題能被正面解決，這對他們是個沉重的打擊畔裕。就像數(shù)學作家霍吉斯（Andrew Hodges）說的：“這是在研究中驚人的轉(zhuǎn)折衣撬，因為希爾伯特曾以為他的計劃將一統(tǒng)天下。對于那些認為數(shù)學完美而且無懈可擊的人來說扮饶，這讓人難以接受……”
圖靈機和不可計算性
哥德爾干凈利落地解決了希爾伯特第一和第二問題具练，接著第三問題又被英國數(shù)學家圖靈（Alan Turing）干掉了。
圖靈甜无，1912-1954
1935年扛点，圖靈23歲，在劍橋跟隨邏輯學家紐曼（Max Newman）攻讀研究生岂丘。紐曼向圖靈介紹了哥德爾剛剛得出的不完備性定理陵究。在理解哥德爾的結(jié)果之后，圖靈發(fā)現(xiàn)了該如何解決希爾伯特第三問題奥帘，判定問題铜邮，同樣，他的答案也是“否寨蹋∷伤猓”
圖靈是怎么證明的呢？前面說過已旧，判定問題問的是秸苗，是不是有“明確程序”能判定任意命題是否可證？“明確程序”指的是什么呢评姨？圖靈的第一步就是定義這個概念难述。沿著萊布尼茨在兩個世紀以前的思路萤晴，圖靈通過構(gòu)想一種強有力的運算機器來闡述他的定義，這個機器不僅能進行算術(shù)運算胁后，也能操作符號店读，這樣就能證明數(shù)學命題。通過思考人類如何計算攀芯，他構(gòu)造了一種假象的機器屯断，這種機器現(xiàn)在被稱為圖靈機。圖靈機后來成了電子計算機的藍圖侣诺。
?本文摘自第一推動叢書《復雜》（梅拉妮·米歇爾）第四章 計算
