從結(jié)繩記事開始，數(shù)和計算就成為人類認識世界、改造世界、創(chuàng)造新世界的有力工具。
不可數(shù)
從結(jié)繩記事開始，數(shù)和計算就成為人類認識世界、改造世界、創(chuàng)造新世界的有力工具。掰指頭數(shù)數(shù)是最基本的智力活動之一，部分動物也會，這應(yīng)該是自然數(shù)的起源。負數(shù)的概念最早出現(xiàn)在公元前三世紀我國的《九章算術(shù)》，西方國家直到1637年才由笛卡爾在《幾何》中勉強承認負數(shù)的地位。0是在公元五世紀左右由印度人發(fā)明的（可能源于印度“絕對無”的觀念），之后由阿拉伯人列為10個數(shù)字之一，廣為傳播，差不多和負數(shù)在同一時期被西方國家接受。小數(shù)也是《九章算術(shù)》發(fā)明的，今天使用的小數(shù)計數(shù)法則是文藝復(fù)興之后的16~17世紀才確定下來。
“實數(shù)”這個詞在18世紀才正式登上歷史舞臺。實數(shù)給人踏實的感覺，可以和直線上的點建立一一對應(yīng)關(guān)系。實數(shù)集被稱為“連續(xù)統(tǒng)”。十進制數(shù)位的整齊劃一加強了實在感：兩個整數(shù)之間等間隔地插入10個小數(shù)，再在兩個小數(shù)之間更細密地等間隔插入10個小數(shù)……模式統(tǒng)一，秩序井然。我國自古以來很多哲學(xué)家都深信冥冥之中自有定數(shù)，18世紀岳麓書院山長曠敏本總結(jié)了這種信念：“是非審之于心，毀譽聽之于人，得失安之于數(shù)”1。
但這種淡定，實為幻覺。
在實數(shù)概念出現(xiàn)之前的1683年，自然數(shù)就已經(jīng)讓伽利略隱隱不安了：對自然數(shù)做最簡單的“數(shù)數(shù)”動作，只數(shù)偶數(shù)，每個偶數(shù)對應(yīng)一個自然數(shù)（那個偶數(shù)的1/2），一一對應(yīng)，因此偶數(shù)和自然數(shù)一樣多。但明明偶數(shù)只是自然數(shù)的一半，另一半是迥異的奇數(shù)啊，這是怎么回事？
人類在懵懵懂懂中走過100多年，19世紀終于迎來了一位認真“數(shù)數(shù)”的人——德國數(shù)學(xué)家、集合論的創(chuàng)始人格奧爾格·康托(Georg Cantor, 1845—1918)。1873年，康托在一封信中提出，他懷疑在自然數(shù)和實數(shù)之間不能建立讓伽利略困惑的那種一一對應(yīng)關(guān)系，即實數(shù)不像自然數(shù)那樣是“可數(shù)的”。一年后康托就證明了自己的懷疑。18年后的1891年，康托發(fā)表另一種證法——對角線證明法(diagonal proof)[1]。這一絕妙思路開辟了一條全新路徑，庫爾特·哥德爾(Kurt G?del, 1906—1978)和阿蘭·圖靈(Alan Turing, 1912—1954)的偉大證明中都會用到它。
對角線法是一種反證法，只用到自然數(shù)常識和數(shù)學(xué)歸納法，不用公式，只借助文字，就能說清楚。
先假定實數(shù)像自然數(shù)那樣是可數(shù)的，那么就可以排列成一個陣列：每個實數(shù)占一行，各行用小數(shù)點對齊，我們只需關(guān)心小數(shù)點后面的序列，遇到整數(shù)或有理數(shù)，只把后面的小數(shù)位都寫成0。實數(shù)有無窮多個，因此這個陣列就有無窮行，先后次序無所謂，無論你怎么排，第一行記為第1個實數(shù)，第二行記為第2個實數(shù)，如此排列下去，直到你相信包含了所有實數(shù)。
康托的對角線操作是：第1個數(shù)，取小數(shù)點后的第一位；第2個數(shù)，取小數(shù)點后的第二位；第3個數(shù)，取小數(shù)點后的第三位……再把取出來的數(shù)位按上述自然次序排成一個無限長的數(shù)，把小數(shù)點放在這個數(shù)的最前面，然后讓這個數(shù)的每位都加1，如果遇到9，就變成0，這樣就得到一個新數(shù)。
把得到的新數(shù)與前面已經(jīng)排好次序的實數(shù)序列逐項對比：第1個數(shù)的第一位和這個數(shù)的第一位不同，第2個數(shù)的第二位和這個數(shù)的第二位不同……，第N個數(shù)的第N位和這個數(shù)的第N位不同……，一直比對下去，如果這個新數(shù)和已經(jīng)排好序列的實數(shù)集合中的任何一個數(shù)都不同，即這個新數(shù)不在實數(shù)集合中。這和集合中已經(jīng)包含了所有實數(shù)的假設(shè)是矛盾的。 “實數(shù)不可數(shù)”得證！
1895年，為了區(qū)分自然數(shù)的可數(shù)性和實數(shù)的不可數(shù)性，康托把自然數(shù)集合的基數(shù)（也稱為勢）記為?0（阿列夫零），稱為第一超限數(shù)，即可數(shù)的無窮大。根據(jù)冪集的定義，自然數(shù)的冪集的基為2?0，康托證明了這正是實數(shù)（連續(xù)統(tǒng)）的基數(shù)。康托推測，第二超限數(shù)?1就是2?0，在?0和?1之間不存在其他超限數(shù)，即“連續(xù)統(tǒng)假設(shè)”。1900年，德國著名數(shù)學(xué)家大衛(wèi)·希爾伯特(David Hilbert,1862—1943)把連續(xù)統(tǒng)假設(shè)列為20世紀有待解決的23個重要數(shù)學(xué)問題的1號問題。1963年，美國數(shù)學(xué)家保羅·科恩(Paul Joseph Cohen,1934—2007)證明連續(xù)統(tǒng)假設(shè)無法通過定理證明，這是一條獨立于公理的陳述，無法通過公理證明或反駁。
對于第二超限數(shù)?1，康托還有驚人發(fā)現(xiàn)：首先，實數(shù)和它的真子集（例如0到1之間的實數(shù)）是等勢的，因此考察0到1之間的實數(shù)的性質(zhì)，可以推廣到所有實數(shù)。其次，連續(xù)統(tǒng)（直線）和平面乃至N維空間的點之間也能建立一一對應(yīng)關(guān)系，只需要把表示各個維度的數(shù)字逐位合并成一個新數(shù)就行，因此也是等勢的?？低斜蛔约旱倪@個發(fā)現(xiàn)震撼得說不出話來，他在一封信中寫道：“我能看到它，但我不相信它?！?/span>
無窮對康托不僅是震撼，還有無盡的折磨。他對無窮的研究當(dāng)時就飽受爭議，遭到哲學(xué)家、神學(xué)家和數(shù)學(xué)家的抨擊，他的老師利奧波德·克羅內(nèi)克（Leopold Kronecker，1823—1891，德國數(shù)學(xué)家與邏輯學(xué)家）甚至斥之為無稽之談。1884年，康托精神崩潰，他自己歸因于對連續(xù)統(tǒng)的緊張工作和克羅內(nèi)克的攻擊。
不可計算數(shù)
從折磨康托的不可數(shù)轉(zhuǎn)回具體數(shù)字，我們發(fā)現(xiàn)的不是秩序，而是更多的詭異。
人們最初認為整數(shù)之間的小數(shù)排列有序，都可以表示為兩個整數(shù)之比（分母不為零），也就是后來所謂的“有理數(shù)”，這個詞反映出人們期望數(shù)字能夠具有良好的秩序。但這種美好的愿望在公元前六世紀就被打破了，畢達哥拉斯(Pythagoras)的學(xué)生希帕索斯(Hippasus)發(fā)現(xiàn)，根據(jù)畢達哥拉斯定理（勾股定理），直角邊均為單位1的直角三角形的斜邊無法表示成一個有理數(shù)。這一發(fā)現(xiàn)讓相信數(shù)乃萬物之本的畢達哥拉斯學(xué)派幾乎瘋掉，他們把希帕索斯扔進了地中海，把這個數(shù)稱為“無理數(shù)”，并一直掩藏這個發(fā)現(xiàn)。后來人們逐漸意識到，無理數(shù)根本不是個案，相比之下，有理數(shù)才是汪洋大海中稀疏的小島。
代數(shù)是數(shù)學(xué)的一個古老分支，代數(shù)方程是解決現(xiàn)實問題強有力的工具。求解整系數(shù)方程的整數(shù)根在公元前就被人們津津樂道，西方國家稱之為丟番圖方程2，這也是我國《九章算術(shù)》第八章的話題。
代數(shù)方程的解（根）稱為代數(shù)數(shù)，好奇的人們不禁要問：“所有的實數(shù)都是代數(shù)數(shù)嗎？是否存在不是任何代數(shù)方程根的實數(shù)？”1740年，瑞士數(shù)學(xué)家萊昂哈德·歐拉(Leonhard Euler, 1707—1783)猜想這樣的數(shù)是存在的，并稱之為“超越數(shù)”（因為它們超越了代數(shù)）。100年后的1841年，法國數(shù)學(xué)家約瑟夫·劉維爾(Joseph Liouville)用階乘構(gòu)造出了第一個超越數(shù)，1882年，德國數(shù)學(xué)家費迪南德·林德曼(Ferdinand von Lindemann,1852—1939)證明圓周率π也是超越數(shù)，之后自然常數(shù)e（代表歐拉）也被證明是超越數(shù)，后來找到的超越數(shù)越來越多，但是一直沒有一種通用方法證明一個實數(shù)是否是超越數(shù)。
是否存在能夠找到所有代數(shù)數(shù)的通用方法？這就是希爾伯特1900年提出的23個問題中的第10號問題“丟番圖方程可解性的判定”。在1928年數(shù)學(xué)大會上，希爾伯特又提出三個問題，第三個就是比第10號問題更具一般性的判定問題(Entscheidungsproblem)：尋求一種確定的方法，從而能夠在有窮步驟內(nèi)確定某類問題中的任何一個是否具有某一特定的性質(zhì)?！八惴ā边@個古老詞匯從此被賦予了明確的含義。
1936年，美國數(shù)學(xué)家阿隆佐·邱奇(Alonzo Church, 1903—1995)和圖靈分別對判定問題給出了否定回答。兩人不約而同地定義了一種“新數(shù)”——“可計算數(shù)”，只是用詞稍有不同：邱奇用的是“Calculable Numbers”，圖靈用的是“Computable Numbers”。
圖靈在論文開頭就給出了定義：“可計算數(shù)可以簡單描述為其小數(shù)表達式可在有限步驟內(nèi)計算出來的實數(shù)?！边@里的“有限步驟”(finite means)并不是說確定數(shù)位的過程有限（事實上往往是無限的），而是指確定數(shù)位的方法是有限的，即算法有限。
有理數(shù)顯然是可計算的，圖靈斷言所有代數(shù)數(shù)都是可計算的，超越數(shù)有一部分是可計算的，這其中包括π和e。
圖靈證明了所有可計算數(shù)是可數(shù)的，而實數(shù)是不可數(shù)的，因此，實數(shù)“絕大多數(shù)”是不可計算的。
圖靈
1930年12月，18歲的圖靈第二次參加劍橋大學(xué)三一學(xué)院的入學(xué)考試，仍未被錄取。他的第二選擇是國王學(xué)院。這一次，他決心專攻數(shù)學(xué)，全心鉆研英國大數(shù)學(xué)家哈代(G. H. Hardy, 1877—1947)的經(jīng)典著作《純數(shù)學(xué)教程》備考。1931年秋，劍橋大學(xué)國王學(xué)院迎來了最著名的學(xué)生之一。
1932年，圖靈研讀的是一本新書——《量子力學(xué)的數(shù)學(xué)基礎(chǔ)》，這是年輕的匈牙利數(shù)學(xué)家馮·諾伊曼(John von Neumann, 1903—1957)的著作。當(dāng)時馮·諾伊曼在大衛(wèi)·希爾伯特身邊研究數(shù)學(xué)，其所在的哥廷根大學(xué)是量子力學(xué)的圣地，所以寫出這樣一部著作也在情理之中。
1933年圖靈研讀的是英國數(shù)學(xué)家伯特蘭·羅素(Bertrand Russell, 1872—1970)的《數(shù)學(xué)哲學(xué)導(dǎo)論》。這部1919年的作品在末尾寫到：“如果有學(xué)生因為這本書而邁入數(shù)理邏輯的大門，并進行認真的研究，那么這本書就達到寫作的初衷了?！眻D靈顯然足以慰藉羅素的衷心。
1934年6月，圖靈順利畢業(yè)，憑借優(yōu)異的成績，獲得了國王學(xué)院獎金資助，得以留校從事研究工作，次年4月獲聘研究員。
1935年春天，圖靈修讀“數(shù)學(xué)基礎(chǔ)”課程，授課教師是麥克斯韋·紐曼(Maxwell Herman Alexander Newman, 1897—1984)。這門課涵蓋了當(dāng)時尚未解決的判定問題，紐曼把希爾伯特尋求的“確定的方法”稱為“機械過程”：用于解決某個問題的一組明確（但無意識的、非智能的）指令集。
1935年5月，圖靈考慮到數(shù)理邏輯圣地普林斯頓大學(xué)，申請寶潔獎學(xué)金未果，但沒影響這位年輕研究員的心情。初夏時節(jié)，圖靈躺在劍橋大學(xué)的格蘭切斯特草坪上，想到了解決判定問題的思路。第二年春天，圖靈把《論可計算數(shù)及其在判定問題上的應(yīng)用》論文草稿交給了紐曼。
就在閱讀草稿那幾天，紐曼收到了邱奇寄來的短文“判定問題的筆記”（1936年3月發(fā)表）[3]，基于另一篇已刊出的論文（1936年4月出版）[4]，邱奇對判定問題給出了否定回答。
按照慣例，邱奇已經(jīng)解決了問題，圖靈的論文不能再發(fā)表了。但紐曼意識到，圖靈的方法與邱奇有很大差異，而且更簡潔明了，因此他建議倫敦數(shù)學(xué)學(xué)會發(fā)表圖靈的論文。倫敦數(shù)學(xué)學(xué)會記錄的收文時間是5月28日，正式出版于1936年的11月和12月兩期，1937年12月又發(fā)表了三頁的修訂。在論文序言部分，圖靈引用了邱奇的兩篇論文，聲明邱奇“有效可計算性(effective calculability）”概念和自己的“可計算性(computability)”是等價的。
把論文發(fā)給倫敦數(shù)學(xué)學(xué)會后，紐曼很快（5月31日）給邱奇寫了一封信，比較了兩人證明方法的不同，并直言“我覺得如果可能，明年他應(yīng)該和你一起研究。”結(jié)果是，1936年9月，圖靈來到普林斯頓大學(xué)就讀邱奇的博士。
1936年12月，博士新生圖靈在普林斯頓數(shù)學(xué)俱樂部報告了自己的論文，聽者寥寥，不足十人，這讓他很郁悶，在家書中寫道“只有名人才能吸引聽眾”。
1938年6月，圖靈獲得博士學(xué)位[6]。他的博士論文的要點是：既然存在不可判定的命題，那就以它為真，加入原有系統(tǒng)，從而得到一個新系統(tǒng)，在新系統(tǒng)中，不可判定命題（已經(jīng)為真）就可判定了。當(dāng)然新系統(tǒng)又會出現(xiàn)新的不可判定命題，解決方法就是再構(gòu)造新系統(tǒng)，如此迭代，形成分層結(jié)構(gòu)。這篇論文引入的另一個概念是改進的圖靈機，它可以中斷計算來尋求外部信息。當(dāng)然，這些內(nèi)容與圖靈的偉大證明相比都算不了什么，但可以換來一個博士學(xué)位。
畢業(yè)之際，馮·諾伊曼想以1500美元的年薪招圖靈為研究助理。圖靈婉拒了，回到劍橋大學(xué)繼續(xù)擔(dān)任研究員，薪水為每學(xué)期10英鎊。
圖靈機
為了解決判定問題，圖靈想象了一種通用計算機器，也就是我們今天所謂的“圖靈機”。圖靈機后來的影響超過了判定問題本身，圖靈可能也意識到了這一點，所以把論文題目定為《論可計算數(shù)及其在判定問題上的應(yīng)用》。
論文第1節(jié)“計算機器(Computing Machine)”開門見山地給出了定義：“我們可以將一位正在進行實數(shù)計算的人比作一臺只能處理有限種情況q1, q2, q3,?, qR的機器，這些情況稱為‘m-格局’?！?937年5月，邱奇對圖靈的論文發(fā)表評論文章：“一位持有鉛筆、紙和一串明確指令的人類計算者，可以被看作是一種圖靈機”，這是“圖靈機”一詞最早見諸文字的地方。
時至今日，已經(jīng)出現(xiàn)的所有計算機都是圖靈機，但不要因此就認為圖靈機就是機器。事實上，在計算機出現(xiàn)之前，Computer本來就是指以計算為工作的人（通常是女性）。人在計算時可能會犯錯，這也沒超出圖靈機的定義：一臺根本不會正確工作或不會做任何有意義工作的圖靈機還是圖靈機，圖靈稱之為“不符合要求的”圖靈機。絕大多數(shù)數(shù)學(xué)教育，甚至可以說所有教育，目的就是把你從一個“不符合要求的”圖靈機培養(yǎng)成“符合要求的”圖靈機。
就像人做演算需要草稿紙，圖靈的機器也是如此：一條無限長的可以左右移動的紙帶穿過機器，紙帶上是排列整齊的一串方格。任何時候都只有一個方格在機器里，機器可以讀、寫或擦除方格里的字符，就像一個笨拙的，或者說特別認真的，做四則運算的孩子。
實際上這臺裝置連四則運算都做不了，它的基本動作就是把紙帶左移或右移一格以及在當(dāng)前方格上進行讀、寫、擦操作，其他什么動作都不會。不過這正是圖靈想要的，在論文第2節(jié)，他一口氣給出了四個定義（原文沒編號）：
1.如果每一階段的動作完全由格局所決定，我們稱這樣的機器為自動機。
2.如果一臺自動機打印兩種符號，第一類符號完全由0和1組成（其他符號稱為第二類符號），那么這樣的機器就稱為計算機器。
3.如果給機器裝上空白紙帶，并且從正確的初始m-格局開始運轉(zhuǎn)，那么機器打印出來的第一類符號組成的子序列，就叫做機器計算出的序列。
4.在這個序列的最前面加上一個十進制小數(shù)點，并把它當(dāng)作一個二進制小數(shù)，所得的實數(shù)就稱為機器計算出的數(shù)。
就這么一臺簡單的機器，就能打印出所有可計算數(shù)？圖靈的魔法在于“m-格局”，m指的是機器(machine)，格局(configuration)是機器所處的狀態(tài)，也就是機器所能處理的情況。機器運行就是在不同狀態(tài)之間切換，機器的功能取決于格局的定義，也就是會遇到哪些格局？遇到每種格局應(yīng)該怎么辦？
機器如此簡單，遇到的情況也簡單：目前的方格是空格還是某種字符？能辦的事情更簡單：左移、右移、寫和擦除。簡單！這就是圖靈機。
在論文第3節(jié)“計算機器示例”中，圖靈展示了如何定義一組格局，讓他的機器打印出一個有理數(shù)和一個無理數(shù)。
論文第4節(jié)“縮略表”定義了一組常用功能，圖靈開始稱為“骨架表”，后來稱為函數(shù)，也就是后來程序員都明白的子程序或函數(shù)，差別就是程序員是在計算機上寫代碼，而圖靈是在沒有計算機的情況下憑空想象。另外他的機器首先關(guān)注的不是加減乘除等功能函數(shù)，而是在紙帶上進行字符串搜尋、拷貝等常用的基本功能。
論文第5節(jié)“可計算序列的枚舉”。完全格局是指完成一個操作后的紙帶快照、讀寫頭的位置和下一個格局。從頭開始順次把完整格局串成行，就是機器完整的歷史操作記錄，“我們把機器表中這樣形式的表達式寫下來，并且用分號分隔開來。如此一來，我們就得了機器的完整描述?！?/span>
把完整描述進行標準化，再把所有符號替換成阿拉伯?dāng)?shù)字，就得到一個整數(shù)，稱為描述數(shù)?！耙粋€可計算序列是由計算它的機器所描述。事實上，任何可計算序列都可以通過這樣的表描述?！币虼?，“每個可計算序列至少對應(yīng)一個描述數(shù)，但不存在一個描述數(shù)對應(yīng)多個可計算序列。因此，可計算序列和可計算數(shù)是可數(shù)的?！焙喲灾?，一臺機器可以用唯一的一個整數(shù)進行編碼，它對應(yīng)一個可計算數(shù)，機器是可數(shù)的，可計算數(shù)也一定是可數(shù)的。
論文第6節(jié)“通用計算機器”和第7節(jié)“通用機的詳細描述”是這篇文章的中心，篇幅不長，也相對容易理解?！鞍l(fā)明一臺計算任何可計算序列的機器是可能的”，這就是圖靈的通用機(Universal Machine)。通用機的輸入是“開頭寫有某臺機器M的標準描述”的紙帶，“可以計算出與M相同的計算序列”。
圖靈在論文第7節(jié)定義了一組骨架表來完成這個任務(wù)，圖靈第一次用“指令”這個詞代替表或函數(shù)，這是區(qū)分通用機和之前只能打印一個可計算序列的專用機的關(guān)鍵。用現(xiàn)在的話說，專用機只能完成一個任務(wù)，而通用機是可編程的，指令就是紙帶上的標準描述。
顯然，圖靈想象中的機器已經(jīng)具備了存儲（紙帶）、軟件（描述）和硬件（通用機）等概念，只是他沒用我們今天熟悉的詞語。15年后的1951年，圖靈在曼徹斯特大學(xué)做程序員，他是這樣定義“編程”的：“一種讓數(shù)字計算機按照人的意愿工作，并將其正確表達在穿孔紙帶上的活動”。
可計算數(shù)不可計算
簡單總結(jié)一下：每臺專用機能夠產(chǎn)生一個可計算序列，對應(yīng)一個可計算數(shù)，專用機的計算過程可以編碼成一個描述數(shù)，通用機執(zhí)行這個描述就可以產(chǎn)生專用機同樣的可計算序列。我們是否就此可以得出結(jié)論：通用機是否可以算出所有的可計算數(shù)？
似乎可以回答“是”。前提是能夠設(shè)計出所有專用機，用今天的話說就是編寫出所有可能的軟件，并在計算機上執(zhí)行這些軟件。軟件數(shù)可數(shù)但無窮多，因此完成這個任務(wù)的前提是編制無窮多個軟件，再無窮無盡地執(zhí)行下去，這實際上是做不到的。
正確答案應(yīng)該是“否”。盡管每個可計算數(shù)都可以算出來，而且所有可計算數(shù)是可數(shù)的，但是不存在枚舉出所有可計算數(shù)的算法，只能一個一個地算，不存在找到所有可計算數(shù)的通用算法，這就是“可計算數(shù)不可計算”的含義。
證明方法是反用康托的對角線法，這就是圖靈在論文第8節(jié)提到的“對角線法的應(yīng)用”。既然可計算數(shù)是可數(shù)的，那就可以把所有可計算數(shù)排成隊列，用對角線法構(gòu)造出一個新數(shù)。根據(jù)對角線法，這個新數(shù)與隊列中的任何可計算數(shù)都不同，因此是不可計算數(shù)。然而，構(gòu)造這個新數(shù)的過程是一個典型的可計算過程，因此這個新數(shù)是可計算數(shù)。這就導(dǎo)致了矛盾。
矛盾的根源在于不可能對可計算數(shù)實行對角線法，上述可計算數(shù)隊列根本沒辦法構(gòu)造出來。
自然數(shù)可以逐個枚舉，因此找出所有可計算數(shù)最直接的思路是逐個檢查所有自然數(shù)，看它是否描述了一臺能夠產(chǎn)生一個可計算數(shù)的專用圖靈機。假定機器D能夠檢查一個整數(shù)是否符合要求的描述數(shù)，通用機U能夠按符合要求的描述數(shù)執(zhí)行并產(chǎn)生對應(yīng)的可計算數(shù)，機器H按照對角線法調(diào)度U和D來逐位產(chǎn)生新數(shù)。
下面這個系統(tǒng)開始運行。
H從i=1開始逐個檢查所有自然數(shù)，用r(i)來記錄已找到的可計算數(shù)的個數(shù)，r(1)=0，之后的規(guī)則是：如果整數(shù)i不是符合要求的描述數(shù)，則r(i)=r(i-1)；反之，r(i) = r(i-1) 1，同時H調(diào)用U計算出i對應(yīng)的可計算數(shù)的前r(i)位，并把第r(i)位添加到新數(shù)的第r(i)位。
三臺機器似乎可以聯(lián)合起來按部就班地運行了。
但機器H終究會碰到自己所對應(yīng)的那個整數(shù)，設(shè)為k。因為H的一切行為正常，因此k是一個符合要求的描述數(shù)，D也應(yīng)該做出這樣的判斷，按規(guī)則H就會把k轉(zhuǎn)換成標準描述，交給U去執(zhí)行計算任務(wù)，也就是產(chǎn)生k對應(yīng)的可計算數(shù)的r(k)位。執(zhí)行描述數(shù)k的機器U就等于H，它會依次產(chǎn)生r(1),r(2),…, r(k-1)，但要產(chǎn)生r(k)時卻回到了任務(wù)本身，陷入無休止的死循環(huán)，永遠產(chǎn)生不出r(k)。
出現(xiàn)上述困境，說明假設(shè)錯誤，因此，不存在能夠生成所有可計算數(shù)的通用算法，也不存在能夠判別任何指定數(shù)是否是可計算數(shù)的萬能機器。這意味著：軟件要一個一個地去編，軟件中的漏洞也要一個一個地去查，沒有萬能機器能幫我們完成這個任務(wù)。
判定問題
從論文第9節(jié)“可計算數(shù)的范疇”開始剩下的十多頁，是可計算數(shù)在判定問題中的應(yīng)用，被《圖靈傳記》[7]的作者安德魯·霍奇斯(Andrew Hodges)譽為“有史以來數(shù)學(xué)類論文中最不尋常的部分”。其實上一節(jié)已經(jīng)體現(xiàn)了證明的精髓。
“判定問題(Entcheidunsproblem)”這個德文詞是希爾伯特的助手海因里?！へ惵?Heinrich Behmann, 1891—1970)創(chuàng)造的。在貝曼的想象中，判定過程是這樣的：
這個問題的一個特性至關(guān)重要，就是證明過程只允許根據(jù)指令進行純機械式的計算，不允許摻雜任何嚴格意義上的思考活動。如果愿意，我們可以說機械的或像機器一樣地思考（說不定以后我們可以用機器來運行這種過程）。
貝曼這番話是1921年5月10日在哥廷根數(shù)學(xué)協(xié)會關(guān)于判定問題的座談會中講到的（這個材料近年才公開[8]）。
1928年，已屆暮年的希爾伯特在國際數(shù)學(xué)家大會上將判定問題列為三大問題之一，他夢想得到一個肯定回答。英國數(shù)學(xué)家哈代對此嗤之以鼻，他指出[7]：“當(dāng)然不存在這樣的公理，我們應(yīng)該感到慶幸，因為如果我們找到了一套機械的規(guī)則，為所有數(shù)學(xué)問題提供解決方案，那么數(shù)學(xué)家的活動就將結(jié)束。”
哈代和希爾伯特各執(zhí)一詞時，圖靈還在備考劍橋大學(xué)，攻讀的正是哈代的《純數(shù)學(xué)教程》。四年大學(xué)畢業(yè)后，他才第一次聽到判定問題，躺在劍橋草坪初夏溫暖的陽光下，破解了兩大頂級數(shù)學(xué)家爭執(zhí)的世紀難題。
那是1936年，圖靈24歲，一個剛剛大學(xué)畢業(yè)的翩翩少年，為機械意義上的計算畫出了明確邊界。
這正是： 數(shù)可數(shù)，非常數(shù)
實數(shù)不可數(shù)，實在在何處？
計算又可數(shù)，其他為何物？
其他可想不可及
機可及，圖靈機
作者介紹
黃鐵軍
·CCF杰出會員。
·北京大學(xué)教授，計算機科學(xué)技術(shù)系主任、數(shù)字媒體研究所所長。
·主要研究方向為視覺信息處理和類腦計算。
腳注
1 岳麓書院講堂中一副對聯(lián)的前三句，由曠敏本撰書。曠敏本（1699—1782年），乾隆十九年（1754年）被聘為岳麓書院山長，即現(xiàn)代意義上的“院長”。
2 丟番圖方程(Diophantine equation)：有一個或者幾個變量的整系數(shù)方程，它們的求解僅僅在整數(shù)范圍內(nèi)進行。丟番圖是古代希臘人，被譽為代數(shù)學(xué)的鼻祖，他早在公元3世紀就開始研究不定方程，因此常稱不定方程為丟番圖方程。
參考文獻
[1] Cantor G. Ueber eine elementare Frage der Mannigfaltigkeitslehre[M]// Jahresbericht der Deutsche Mathematiker-Vereinigung 1890-1891. 1891,1:75-78.
[2] Petzold C. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine[M]. John Wiley & Sons, 2011. （中文版： 楊衛(wèi)東,朱皓 等譯. 圖靈的秘密. 人民郵電出版社, 2012）
[3] Church A. A Note on the Entcheidunsproblem[J]. Journal of Symbolic Logic. 1936,1(1):40-41.
[4] Church A. An unsolvable problem of elementary number theory[J]. American Journal of Mathematics. 1936,58 (2): 345-363.
[5] Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem[C]// Proceedings of the London Mathematical Society. 1936:230-65.
[6] Turing A. Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161.
[7] Hodges A. Alan Turing: The Enigma[M]. Simon & Schuster, 1983: 104.
[8] Ewald W. From Kant to Hilbert: A Source Book in the Foundation of Mathematics[M]. Oxford University Press. 1996, Vol. II, 1113.
中國計算機學(xué)會
微信號：ccfvoice
