不可數(shù)

從結(jié)繩記事開(kāi)始，數(shù)和計(jì)算就成為人類認(rèn)識(shí)世界、改造世界、創(chuàng)造新世界的有力工具。掰指頭數(shù)數(shù)是最基本的智力活動(dòng)之一，部分動(dòng)物也會(huì)，這應(yīng)該是自然數(shù)的起源。負(fù)數(shù)的概念最早出現(xiàn)在公元前三世紀(jì)我國(guó)的《九章算術(shù)》，西方國(guó)家直到1637年才由笛卡爾在《幾何》中勉強(qiáng)承認(rèn)負(fù)數(shù)的地位。0是在公元五世紀(jì)左右由印度人發(fā)明的（可能源于印度“絕對(duì)無(wú)”的觀念），之后由阿拉伯人列為10個(gè)數(shù)字之一，廣為傳播，差不多和負(fù)數(shù)在同一時(shí)期被西方國(guó)家接受。小數(shù)也是《九章算術(shù)》發(fā)明的，今天使用的小數(shù)計(jì)數(shù)法則是文藝復(fù)興之后的16~17世紀(jì)才確定下來(lái)。

“實(shí)數(shù)”這個(gè)詞在18世紀(jì)才正式登上歷史舞臺(tái)。實(shí)數(shù)給人踏實(shí)的感覺(jué)，可以和直線上的點(diǎn)建立一一對(duì)應(yīng)關(guān)系。實(shí)數(shù)集被稱為“連續(xù)統(tǒng)”。十進(jìn)制數(shù)位的整齊劃一加強(qiáng)了實(shí)在感：兩個(gè)整數(shù)之間等間隔地插入10個(gè)小數(shù)，再在兩個(gè)小數(shù)之間更細(xì)密地等間隔插入10個(gè)小數(shù)……模式統(tǒng)一，秩序井然。我國(guó)自古以來(lái)很多哲學(xué)家都深信冥冥之中自有定數(shù)，18世紀(jì)岳麓書(shū)院山長(zhǎng)曠敏本總結(jié)了這種信念：“是非審之于心，毀譽(yù)聽(tīng)之于人，得失安之于數(shù)”¹。

但這種淡定，實(shí)為幻覺(jué)。

在實(shí)數(shù)概念出現(xiàn)之前的1683年，自然數(shù)就已經(jīng)讓伽利略隱隱不安了：對(duì)自然數(shù)做最簡(jiǎn)單的“數(shù)數(shù)”動(dòng)作，只數(shù)偶數(shù)，每個(gè)偶數(shù)對(duì)應(yīng)一個(gè)自然數(shù)（那個(gè)偶數(shù)的1/2），一一對(duì)應(yīng)，因此偶數(shù)和自然數(shù)一樣多。但明明偶數(shù)只是自然數(shù)的一半，另一半是迥異的奇數(shù)啊，這是怎么回事？

人類在懵懵懂懂中走過(guò)100多年，19世紀(jì)終于迎來(lái)了一位認(rèn)真“數(shù)數(shù)”的人——德國(guó)數(shù)學(xué)家、集合論的創(chuàng)始人格奧爾格·康托(Georg Cantor, 1845—1918)。1873年，康托在一封信中提出，他懷疑在自然數(shù)和實(shí)數(shù)之間不能建立讓伽利略困惑的那種一一對(duì)應(yīng)關(guān)系，即實(shí)數(shù)不像自然數(shù)那樣是“可數(shù)的”。一年后康托就證明了自己的懷疑。18年后的1891年，康托發(fā)表另一種證法——對(duì)角線證明法(diagonal proof)^[1]。這一絕妙思路開(kāi)辟了一條全新路徑，庫(kù)爾特·哥德?tīng)?Kurt G?del, 1906—1978)和阿蘭·圖靈(Alan Turing, 1912—1954)的偉大證明中都會(huì)用到它。

對(duì)角線法是一種反證法，只用到自然數(shù)常識(shí)和數(shù)學(xué)歸納法，不用公式，只借助文字，就能說(shuō)清楚。

先假定實(shí)數(shù)像自然數(shù)那樣是可數(shù)的，那么就可以排列成一個(gè)陣列：每個(gè)實(shí)數(shù)占一行，各行用小數(shù)點(diǎn)對(duì)齊，我們只需關(guān)心小數(shù)點(diǎn)后面的序列，遇到整數(shù)或有理數(shù)，只把后面的小數(shù)位都寫(xiě)成0。實(shí)數(shù)有無(wú)窮多個(gè)，因此這個(gè)陣列就有無(wú)窮行，先后次序無(wú)所謂，無(wú)論你怎么排，第一行記為第1個(gè)實(shí)數(shù)，第二行記為第2個(gè)實(shí)數(shù)，如此排列下去，直到你相信包含了所有實(shí)數(shù)。

康托的對(duì)角線操作是：第1個(gè)數(shù)，取小數(shù)點(diǎn)后的第一位；第2個(gè)數(shù)，取小數(shù)點(diǎn)后的第二位；第3個(gè)數(shù)，取小數(shù)點(diǎn)后的第三位……再把取出來(lái)的數(shù)位按上述自然次序排成一個(gè)無(wú)限長(zhǎng)的數(shù)，把小數(shù)點(diǎn)放在這個(gè)數(shù)的最前面，然后讓這個(gè)數(shù)的每位都加1，如果遇到9，就變成0，這樣就得到一個(gè)新數(shù)。

把得到的新數(shù)與前面已經(jīng)排好次序的實(shí)數(shù)序列逐項(xiàng)對(duì)比：第1個(gè)數(shù)的第一位和這個(gè)數(shù)的第一位不同，第2個(gè)數(shù)的第二位和這個(gè)數(shù)的第二位不同……，第N個(gè)數(shù)的第N位和這個(gè)數(shù)的第N位不同……，一直比對(duì)下去，如果這個(gè)新數(shù)和已經(jīng)排好序列的實(shí)數(shù)集合中的任何一個(gè)數(shù)都不同，即這個(gè)新數(shù)不在實(shí)數(shù)集合中。這和集合中已經(jīng)包含了所有實(shí)數(shù)的假設(shè)是矛盾的。 “實(shí)數(shù)不可數(shù)”得證！

1895年，為了區(qū)分自然數(shù)的可數(shù)性和實(shí)數(shù)的不可數(shù)性，康托把自然數(shù)集合的基數(shù)（也稱為勢(shì)）記為?₀（阿列夫零），稱為第一超限數(shù)，即可數(shù)的無(wú)窮大。根據(jù)冪集的定義，自然數(shù)的冪集的基為2^?0，康托證明了這正是實(shí)數(shù)（連續(xù)統(tǒng)）的基數(shù)?？低型茰y(cè)，第二超限數(shù)?₁就是2^?0，在?₀和?₁之間不存在其他超限數(shù)，即“連續(xù)統(tǒng)假設(shè)”。1900年，德國(guó)著名數(shù)學(xué)家大衛(wèi)·希爾伯特(David Hilbert,1862—1943)把連續(xù)統(tǒng)假設(shè)列為20世紀(jì)有待解決的23個(gè)重要數(shù)學(xué)問(wèn)題的1號(hào)問(wèn)題。1963年，美國(guó)數(shù)學(xué)家保羅·科恩(Paul Joseph Cohen,1934—2007)證明連續(xù)統(tǒng)假設(shè)無(wú)法通過(guò)定理證明，這是一條獨(dú)立于公理的陳述，無(wú)法通過(guò)公理證明或反駁。

對(duì)于第二超限數(shù)?₁，康托還有驚人發(fā)現(xiàn)：首先，實(shí)數(shù)和它的真子集（例如0到1之間的實(shí)數(shù)）是等勢(shì)的，因此考察0到1之間的實(shí)數(shù)的性質(zhì)，可以推廣到所有實(shí)數(shù)。其次，連續(xù)統(tǒng)（直線）和平面乃至N維空間的點(diǎn)之間也能建立一一對(duì)應(yīng)關(guān)系，只需要把表示各個(gè)維度的數(shù)字逐位合并成一個(gè)新數(shù)就行，因此也是等勢(shì)的?？低斜蛔约旱倪@個(gè)發(fā)現(xiàn)震撼得說(shuō)不出話來(lái)，他在一封信中寫(xiě)道：“我能看到它，但我不相信它。”

無(wú)窮對(duì)康托不僅是震撼，還有無(wú)盡的折磨。他對(duì)無(wú)窮的研究當(dāng)時(shí)就飽受爭(zhēng)議，遭到哲學(xué)家、神學(xué)家和數(shù)學(xué)家的抨擊，他的老師利奧波德·克羅內(nèi)克（Leopold Kronecker，1823—1891，德國(guó)數(shù)學(xué)家與邏輯學(xué)家）甚至斥之為無(wú)稽之談。1884年，康托精神崩潰，他自己歸因于對(duì)連續(xù)統(tǒng)的緊張工作和克羅內(nèi)克的攻擊。

不可計(jì)算數(shù)

從折磨康托的不可數(shù)轉(zhuǎn)回具體數(shù)字，我們發(fā)現(xiàn)的不是秩序，而是更多的詭異。

人們最初認(rèn)為整數(shù)之間的小數(shù)排列有序，都可以表示為兩個(gè)整數(shù)之比（分母不為零），也就是后來(lái)所謂的“有理數(shù)”，這個(gè)詞反映出人們期望數(shù)字能夠具有良好的秩序。但這種美好的愿望在公元前六世紀(jì)就被打破了，畢達(dá)哥拉斯(Pythagoras)的學(xué)生希帕索斯(Hippasus)發(fā)現(xiàn)，根據(jù)畢達(dá)哥拉斯定理（勾股定理），直角邊均為單位1的直角三角形的斜邊無(wú)法表示成一個(gè)有理數(shù)。這一發(fā)現(xiàn)讓相信數(shù)乃萬(wàn)物之本的畢達(dá)哥拉斯學(xué)派幾乎瘋掉，他們把希帕索斯扔進(jìn)了地中海，把這個(gè)數(shù)稱為“無(wú)理數(shù)”，并一直掩藏這個(gè)發(fā)現(xiàn)。后來(lái)人們逐漸意識(shí)到，無(wú)理數(shù)根本不是個(gè)案，相比之下，有理數(shù)才是汪洋大海中稀疏的小島。

代數(shù)是數(shù)學(xué)的一個(gè)古老分支，代數(shù)方程是解決現(xiàn)實(shí)問(wèn)題強(qiáng)有力的工具。求解整系數(shù)方程的整數(shù)根在公元前就被人們津津樂(lè)道，西方國(guó)家稱之為丟番圖方程²，這也是我國(guó)《九章算術(shù)》第八章的話題。

代數(shù)方程的解（根）稱為代數(shù)數(shù)，好奇的人們不禁要問(wèn)：“所有的實(shí)數(shù)都是代數(shù)數(shù)嗎？是否存在不是任何代數(shù)方程根的實(shí)數(shù)？”1740年，瑞士數(shù)學(xué)家萊昂哈德·歐拉(Leonhard Euler, 1707—1783)猜想這樣的數(shù)是存在的，并稱之為“超越數(shù)”（因?yàn)樗鼈兂搅舜鷶?shù)）。100年后的1841年，法國(guó)數(shù)學(xué)家約瑟夫·劉維爾(Joseph Liouville)用階乘構(gòu)造出了第一個(gè)超越數(shù)，1882年，德國(guó)數(shù)學(xué)家費(fèi)迪南德·林德曼(Ferdinand von Lindemann,1852—1939)證明圓周率π也是超越數(shù)，之后自然常數(shù)e（代表歐拉）也被證明是超越數(shù)，后來(lái)找到的超越數(shù)越來(lái)越多，但是一直沒(méi)有一種通用方法證明一個(gè)實(shí)數(shù)是否是超越數(shù)。

是否存在能夠找到所有代數(shù)數(shù)的通用方法？這就是希爾伯特1900年提出的23個(gè)問(wèn)題中的第10號(hào)問(wèn)題“丟番圖方程可解性的判定”。在1928年數(shù)學(xué)大會(huì)上，希爾伯特又提出三個(gè)問(wèn)題，第三個(gè)就是比第10號(hào)問(wèn)題更具一般性的判定問(wèn)題(Entscheidungsproblem)：尋求一種確定的方法，從而能夠在有窮步驟內(nèi)確定某類問(wèn)題中的任何一個(gè)是否具有某一特定的性質(zhì)?！八惴ā边@個(gè)古老詞匯從此被賦予了明確的含義。

1936年，美國(guó)數(shù)學(xué)家阿隆佐·邱奇(Alonzo Church, 1903—1995)和圖靈分別對(duì)判定問(wèn)題給出了否定回答。兩人不約而同地定義了一種“新數(shù)”——“可計(jì)算數(shù)”，只是用詞稍有不同：邱奇用的是“Calculable Numbers”，圖靈用的是“Computable Numbers”。

圖靈在論文開(kāi)頭就給出了定義：“可計(jì)算數(shù)可以簡(jiǎn)單描述為其小數(shù)表達(dá)式可在有限步驟內(nèi)計(jì)算出來(lái)的實(shí)數(shù)。”這里的“有限步驟”(finite means)并不是說(shuō)確定數(shù)位的過(guò)程有限（事實(shí)上往往是無(wú)限的），而是指確定數(shù)位的方法是有限的，即算法有限。

有理數(shù)顯然是可計(jì)算的，圖靈斷言所有代數(shù)數(shù)都是可計(jì)算的，超越數(shù)有一部分是可計(jì)算的，這其中包括π和e。

圖靈證明了所有可計(jì)算數(shù)是可數(shù)的，而實(shí)數(shù)是不可數(shù)的，因此，實(shí)數(shù)“絕大多數(shù)”是不可計(jì)算的。

圖靈

1930年12月，18歲的圖靈第二次參加劍橋大學(xué)三一學(xué)院的入學(xué)考試，仍未被錄取。他的第二選擇是國(guó)王學(xué)院。這一次，他決心專攻數(shù)學(xué)，全心鉆研英國(guó)大數(shù)學(xué)家哈代(G. H. Hardy, 1877—1947)的經(jīng)典著作《純數(shù)學(xué)教程》備考。1931年秋，劍橋大學(xué)國(guó)王學(xué)院迎來(lái)了最著名的學(xué)生之一。

1932年，圖靈研讀的是一本新書(shū)——《量子力學(xué)的數(shù)學(xué)基礎(chǔ)》，這是年輕的匈牙利數(shù)學(xué)家馮·諾伊曼(John von Neumann, 1903—1957)的著作。當(dāng)時(shí)馮·諾伊曼在大衛(wèi)·希爾伯特身邊研究數(shù)學(xué)，其所在的哥廷根大學(xué)是量子力學(xué)的圣地，所以寫(xiě)出這樣一部著作也在情理之中。

1933年圖靈研讀的是英國(guó)數(shù)學(xué)家伯特蘭·羅素(Bertrand Russell, 1872—1970)的《數(shù)學(xué)哲學(xué)導(dǎo)論》。這部1919年的作品在末尾寫(xiě)到：“如果有學(xué)生因?yàn)檫@本書(shū)而邁入數(shù)理邏輯的大門(mén)，并進(jìn)行認(rèn)真的研究，那么這本書(shū)就達(dá)到寫(xiě)作的初衷了?！眻D靈顯然足以慰藉羅素的衷心。

1934年6月，圖靈順利畢業(yè)，憑借優(yōu)異的成績(jī)，獲得了國(guó)王學(xué)院獎(jiǎng)金資助，得以留校從事研究工作，次年4月獲聘研究員。

1935年春天，圖靈修讀“數(shù)學(xué)基礎(chǔ)”課程，授課教師是麥克斯韋·紐曼(Maxwell Herman Alexander Newman, 1897—1984)。這門(mén)課涵蓋了當(dāng)時(shí)尚未解決的判定問(wèn)題，紐曼把希爾伯特尋求的“確定的方法”稱為“機(jī)械過(guò)程”：用于解決某個(gè)問(wèn)題的一組明確（但無(wú)意識(shí)的、非智能的）指令集。

1935年5月，圖靈考慮到數(shù)理邏輯圣地普林斯頓大學(xué)，申請(qǐng)寶潔獎(jiǎng)學(xué)金未果，但沒(méi)影響這位年輕研究員的心情。初夏時(shí)節(jié)，圖靈躺在劍橋大學(xué)的格蘭切斯特草坪上，想到了解決判定問(wèn)題的思路。第二年春天，圖靈把《論可計(jì)算數(shù)及其在判定問(wèn)題上的應(yīng)用》論文草稿交給了紐曼。

就在閱讀草稿那幾天，紐曼收到了邱奇寄來(lái)的短文“判定問(wèn)題的筆記”（1936年3月發(fā)表）^[3]，基于另一篇已刊出的論文（1936年4月出版）^[4]，邱奇對(duì)判定問(wèn)題給出了否定回答。

按照慣例，邱奇已經(jīng)解決了問(wèn)題，圖靈的論文不能再發(fā)表了。但紐曼意識(shí)到，圖靈的方法與邱奇有很大差異，而且更簡(jiǎn)潔明了，因此他建議倫敦?cái)?shù)學(xué)學(xué)會(huì)發(fā)表圖靈的論文。倫敦?cái)?shù)學(xué)學(xué)會(huì)記錄的收文時(shí)間是5月28日，正式出版于1936年的11月和12月兩期，1937年12月又發(fā)表了三頁(yè)的修訂。在論文序言部分，圖靈引用了邱奇的兩篇論文，聲明邱奇“有效可計(jì)算性(effective calculability）”概念和自己的“可計(jì)算性(computability)”是等價(jià)的。

把論文發(fā)給倫敦?cái)?shù)學(xué)學(xué)會(huì)后，紐曼很快（5月31日）給邱奇寫(xiě)了一封信，比較了兩人證明方法的不同，并直言“我覺(jué)得如果可能，明年他應(yīng)該和你一起研究?！苯Y(jié)果是，1936年9月，圖靈來(lái)到普林斯頓大學(xué)就讀邱奇的博士。

1936年12月，博士新生圖靈在普林斯頓數(shù)學(xué)俱樂(lè)部報(bào)告了自己的論文，聽(tīng)者寥寥，不足十人，這讓他很郁悶，在家書(shū)中寫(xiě)道“只有名人才能吸引聽(tīng)眾”。

1938年6月，圖靈獲得博士學(xué)位^[6]。他的博士論文的要點(diǎn)是：既然存在不可判定的命題，那就以它為真，加入原有系統(tǒng)，從而得到一個(gè)新系統(tǒng)，在新系統(tǒng)中，不可判定命題（已經(jīng)為真）就可判定了。當(dāng)然新系統(tǒng)又會(huì)出現(xiàn)新的不可判定命題，解決方法就是再構(gòu)造新系統(tǒng)，如此迭代，形成分層結(jié)構(gòu)。這篇論文引入的另一個(gè)概念是改進(jìn)的圖靈機(jī)，它可以中斷計(jì)算來(lái)尋求外部信息。當(dāng)然，這些內(nèi)容與圖靈的偉大證明相比都算不了什么，但可以換來(lái)一個(gè)博士學(xué)位。

畢業(yè)之際，馮·諾伊曼想以1500美元的年薪招圖靈為研究助理。圖靈婉拒了，回到劍橋大學(xué)繼續(xù)擔(dān)任研究員，薪水為每學(xué)期10英鎊。

圖靈機(jī)

為了解決判定問(wèn)題，圖靈想象了一種通用計(jì)算機(jī)器，也就是我們今天所謂的“圖靈機(jī)”。圖靈機(jī)后來(lái)的影響超過(guò)了判定問(wèn)題本身，圖靈可能也意識(shí)到了這一點(diǎn)，所以把論文題目定為《論可計(jì)算數(shù)及其在判定問(wèn)題上的應(yīng)用》。

論文第1節(jié)“計(jì)算機(jī)器(Computing Machine)”開(kāi)門(mén)見(jiàn)山地給出了定義：“我們可以將一位正在進(jìn)行實(shí)數(shù)計(jì)算的人比作一臺(tái)只能處理有限種情況q₁, q₂, q₃,?, q_R的機(jī)器，這些情況稱為‘m-格局’。”1937年5月，邱奇對(duì)圖靈的論文發(fā)表評(píng)論文章：“一位持有鉛筆、紙和一串明確指令的人類計(jì)算者，可以被看作是一種圖靈機(jī)”，這是“圖靈機(jī)”一詞最早見(jiàn)諸文字的地方。

時(shí)至今日，已經(jīng)出現(xiàn)的所有計(jì)算機(jī)都是圖靈機(jī)，但不要因此就認(rèn)為圖靈機(jī)就是機(jī)器。事實(shí)上，在計(jì)算機(jī)出現(xiàn)之前，Computer本來(lái)就是指以計(jì)算為工作的人（通常是女性）。人在計(jì)算時(shí)可能會(huì)犯錯(cuò)，這也沒(méi)超出圖靈機(jī)的定義：一臺(tái)根本不會(huì)正確工作或不會(huì)做任何有意義工作的圖靈機(jī)還是圖靈機(jī)，圖靈稱之為“不符合要求的”圖靈機(jī)。絕大多數(shù)數(shù)學(xué)教育，甚至可以說(shuō)所有教育，目的就是把你從一個(gè)“不符合要求的”圖靈機(jī)培養(yǎng)成“符合要求的”圖靈機(jī)。

就像人做演算需要草稿紙，圖靈的機(jī)器也是如此：一條無(wú)限長(zhǎng)的可以左右移動(dòng)的紙帶穿過(guò)機(jī)器，紙帶上是排列整齊的一串方格。任何時(shí)候都只有一個(gè)方格在機(jī)器里，機(jī)器可以讀、寫(xiě)或擦除方格里的字符，就像一個(gè)笨拙的，或者說(shuō)特別認(rèn)真的，做四則運(yùn)算的孩子。

實(shí)際上這臺(tái)裝置連四則運(yùn)算都做不了，它的基本動(dòng)作就是把紙帶左移或右移一格以及在當(dāng)前方格上進(jìn)行讀、寫(xiě)、擦操作，其他什么動(dòng)作都不會(huì)。不過(guò)這正是圖靈想要的，在論文第2節(jié)，他一口氣給出了四個(gè)定義（原文沒(méi)編號(hào)）：

1.如果每一階段的動(dòng)作完全由格局所決定，我們稱這樣的機(jī)器為自動(dòng)機(jī)。

2.如果一臺(tái)自動(dòng)機(jī)打印兩種符號(hào)，第一類符號(hào)完全由0和1組成（其他符號(hào)稱為第二類符號(hào)），那么這樣的機(jī)器就稱為計(jì)算機(jī)器。

3.如果給機(jī)器裝上空白紙帶，并且從正確的初始m-格局開(kāi)始運(yùn)轉(zhuǎn)，那么機(jī)器打印出來(lái)的第一類符號(hào)組成的子序列，就叫做機(jī)器計(jì)算出的序列。

4.在這個(gè)序列的最前面加上一個(gè)十進(jìn)制小數(shù)點(diǎn)，并把它當(dāng)作一個(gè)二進(jìn)制小數(shù)，所得的實(shí)數(shù)就稱為機(jī)器計(jì)算出的數(shù)。

就這么一臺(tái)簡(jiǎn)單的機(jī)器，就能打印出所有可計(jì)算數(shù)？圖靈的魔法在于“m-格局”，m指的是機(jī)器(machine)，格局(configuration)是機(jī)器所處的狀態(tài)，也就是機(jī)器所能處理的情況。機(jī)器運(yùn)行就是在不同狀態(tài)之間切換，機(jī)器的功能取決于格局的定義，也就是會(huì)遇到哪些格局？遇到每種格局應(yīng)該怎么辦？

機(jī)器如此簡(jiǎn)單，遇到的情況也簡(jiǎn)單：目前的方格是空格還是某種字符？能辦的事情更簡(jiǎn)單：左移、右移、寫(xiě)和擦除。簡(jiǎn)單！這就是圖靈機(jī)。

在論文第3節(jié)“計(jì)算機(jī)器示例”中，圖靈展示了如何定義一組格局，讓他的機(jī)器打印出一個(gè)有理數(shù)和一個(gè)無(wú)理數(shù)。

論文第4節(jié)“縮略表”定義了一組常用功能，圖靈開(kāi)始稱為“骨架表”，后來(lái)稱為函數(shù)，也就是后來(lái)程序員都明白的子程序或函數(shù)，差別就是程序員是在計(jì)算機(jī)上寫(xiě)代碼，而圖靈是在沒(méi)有計(jì)算機(jī)的情況下憑空想象。另外他的機(jī)器首先關(guān)注的不是加減乘除等功能函數(shù)，而是在紙帶上進(jìn)行字符串搜尋、拷貝等常用的基本功能。

論文第5節(jié)“可計(jì)算序列的枚舉”。完全格局是指完成一個(gè)操作后的紙帶快照、讀寫(xiě)頭的位置和下一個(gè)格局。從頭開(kāi)始順次把完整格局串成行，就是機(jī)器完整的歷史操作記錄，“我們把機(jī)器表中這樣形式的表達(dá)式寫(xiě)下來(lái)，并且用分號(hào)分隔開(kāi)來(lái)。如此一來(lái)，我們就得了機(jī)器的完整描述?！?/span>

把完整描述進(jìn)行標(biāo)準(zhǔn)化，再把所有符號(hào)替換成阿拉伯?dāng)?shù)字，就得到一個(gè)整數(shù)，稱為描述數(shù)?！耙粋€(gè)可計(jì)算序列是由計(jì)算它的機(jī)器所描述。事實(shí)上，任何可計(jì)算序列都可以通過(guò)這樣的表描述?！币虼?，“每個(gè)可計(jì)算序列至少對(duì)應(yīng)一個(gè)描述數(shù)，但不存在一個(gè)描述數(shù)對(duì)應(yīng)多個(gè)可計(jì)算序列。因此，可計(jì)算序列和可計(jì)算數(shù)是可數(shù)的?！焙?jiǎn)言之，一臺(tái)機(jī)器可以用唯一的一個(gè)整數(shù)進(jìn)行編碼，它對(duì)應(yīng)一個(gè)可計(jì)算數(shù)，機(jī)器是可數(shù)的，可計(jì)算數(shù)也一定是可數(shù)的。

論文第6節(jié)“通用計(jì)算機(jī)器”和第7節(jié)“通用機(jī)的詳細(xì)描述”是這篇文章的中心，篇幅不長(zhǎng)，也相對(duì)容易理解?！鞍l(fā)明一臺(tái)計(jì)算任何可計(jì)算序列的機(jī)器是可能的”，這就是圖靈的通用機(jī)(Universal Machine)。通用機(jī)的輸入是“開(kāi)頭寫(xiě)有某臺(tái)機(jī)器M的標(biāo)準(zhǔn)描述”的紙帶，“可以計(jì)算出與M相同的計(jì)算序列”。

圖靈在論文第7節(jié)定義了一組骨架表來(lái)完成這個(gè)任務(wù)，圖靈第一次用“指令”這個(gè)詞代替表或函數(shù)，這是區(qū)分通用機(jī)和之前只能打印一個(gè)可計(jì)算序列的專用機(jī)的關(guān)鍵。用現(xiàn)在的話說(shuō)，專用機(jī)只能完成一個(gè)任務(wù)，而通用機(jī)是可編程的，指令就是紙帶上的標(biāo)準(zhǔn)描述。

顯然，圖靈想象中的機(jī)器已經(jīng)具備了存儲(chǔ)（紙帶）、軟件（描述）和硬件（通用機(jī)）等概念，只是他沒(méi)用我們今天熟悉的詞語(yǔ)。15年后的1951年，圖靈在曼徹斯特大學(xué)做程序員，他是這樣定義“編程”的：“一種讓數(shù)字計(jì)算機(jī)按照人的意愿工作，并將其正確表達(dá)在穿孔紙帶上的活動(dòng)”。

可計(jì)算數(shù)不可計(jì)算

簡(jiǎn)單總結(jié)一下：每臺(tái)專用機(jī)能夠產(chǎn)生一個(gè)可計(jì)算序列，對(duì)應(yīng)一個(gè)可計(jì)算數(shù)，專用機(jī)的計(jì)算過(guò)程可以編碼成一個(gè)描述數(shù)，通用機(jī)執(zhí)行這個(gè)描述就可以產(chǎn)生專用機(jī)同樣的可計(jì)算序列。我們是否就此可以得出結(jié)論：通用機(jī)是否可以算出所有的可計(jì)算數(shù)？

似乎可以回答“是”。前提是能夠設(shè)計(jì)出所有專用機(jī)，用今天的話說(shuō)就是編寫(xiě)出所有可能的軟件，并在計(jì)算機(jī)上執(zhí)行這些軟件。軟件數(shù)可數(shù)但無(wú)窮多，因此完成這個(gè)任務(wù)的前提是編制無(wú)窮多個(gè)軟件，再無(wú)窮無(wú)盡地執(zhí)行下去，這實(shí)際上是做不到的。

正確答案應(yīng)該是“否”。盡管每個(gè)可計(jì)算數(shù)都可以算出來(lái)，而且所有可計(jì)算數(shù)是可數(shù)的，但是不存在枚舉出所有可計(jì)算數(shù)的算法，只能一個(gè)一個(gè)地算，不存在找到所有可計(jì)算數(shù)的通用算法，這就是“可計(jì)算數(shù)不可計(jì)算”的含義。

證明方法是反用康托的對(duì)角線法，這就是圖靈在論文第8節(jié)提到的“對(duì)角線法的應(yīng)用”。既然可計(jì)算數(shù)是可數(shù)的，那就可以把所有可計(jì)算數(shù)排成隊(duì)列，用對(duì)角線法構(gòu)造出一個(gè)新數(shù)。根據(jù)對(duì)角線法，這個(gè)新數(shù)與隊(duì)列中的任何可計(jì)算數(shù)都不同，因此是不可計(jì)算數(shù)。然而，構(gòu)造這個(gè)新數(shù)的過(guò)程是一個(gè)典型的可計(jì)算過(guò)程，因此這個(gè)新數(shù)是可計(jì)算數(shù)。這就導(dǎo)致了矛盾。

矛盾的根源在于不可能對(duì)可計(jì)算數(shù)實(shí)行對(duì)角線法，上述可計(jì)算數(shù)隊(duì)列根本沒(méi)辦法構(gòu)造出來(lái)。

自然數(shù)可以逐個(gè)枚舉，因此找出所有可計(jì)算數(shù)最直接的思路是逐個(gè)檢查所有自然數(shù)，看它是否描述了一臺(tái)能夠產(chǎn)生一個(gè)可計(jì)算數(shù)的專用圖靈機(jī)。假定機(jī)器D能夠檢查一個(gè)整數(shù)是否符合要求的描述數(shù)，通用機(jī)U能夠按符合要求的描述數(shù)執(zhí)行并產(chǎn)生對(duì)應(yīng)的可計(jì)算數(shù)，機(jī)器H按照對(duì)角線法調(diào)度U和D來(lái)逐位產(chǎn)生新數(shù)。

下面這個(gè)系統(tǒng)開(kāi)始運(yùn)行。

H從i=1開(kāi)始逐個(gè)檢查所有自然數(shù)，用r(i)來(lái)記錄已找到的可計(jì)算數(shù)的個(gè)數(shù)，r(1)=0，之后的規(guī)則是：如果整數(shù)i不是符合要求的描述數(shù)，則r(i)=r(i-1)；反之，r(i) = r(i-1) 1，同時(shí)H調(diào)用U計(jì)算出i對(duì)應(yīng)的可計(jì)算數(shù)的前r(i)位，并把第r(i)位添加到新數(shù)的第r(i)位。

三臺(tái)機(jī)器似乎可以聯(lián)合起來(lái)按部就班地運(yùn)行了。

但機(jī)器H終究會(huì)碰到自己所對(duì)應(yīng)的那個(gè)整數(shù)，設(shè)為k。因?yàn)镠的一切行為正常，因此k是一個(gè)符合要求的描述數(shù)，D也應(yīng)該做出這樣的判斷，按規(guī)則H就會(huì)把k轉(zhuǎn)換成標(biāo)準(zhǔn)描述，交給U去執(zhí)行計(jì)算任務(wù)，也就是產(chǎn)生k對(duì)應(yīng)的可計(jì)算數(shù)的r(k)位。執(zhí)行描述數(shù)k的機(jī)器U就等于H，它會(huì)依次產(chǎn)生r(1),r(2),…, r(k-1)，但要產(chǎn)生r(k)時(shí)卻回到了任務(wù)本身，陷入無(wú)休止的死循環(huán)，永遠(yuǎn)產(chǎn)生不出r(k)。

出現(xiàn)上述困境，說(shuō)明假設(shè)錯(cuò)誤，因此，不存在能夠生成所有可計(jì)算數(shù)的通用算法，也不存在能夠判別任何指定數(shù)是否是可計(jì)算數(shù)的萬(wàn)能機(jī)器。這意味著：軟件要一個(gè)一個(gè)地去編，軟件中的漏洞也要一個(gè)一個(gè)地去查，沒(méi)有萬(wàn)能機(jī)器能幫我們完成這個(gè)任務(wù)。

判定問(wèn)題

從論文第9節(jié)“可計(jì)算數(shù)的范疇”開(kāi)始剩下的十多頁(yè)，是可計(jì)算數(shù)在判定問(wèn)題中的應(yīng)用，被《圖靈傳記》^[7]的作者安德魯·霍奇斯(Andrew Hodges)譽(yù)為“有史以來(lái)數(shù)學(xué)類論文中最不尋常的部分”。其實(shí)上一節(jié)已經(jīng)體現(xiàn)了證明的精髓。

“判定問(wèn)題(Entcheidunsproblem)”這個(gè)德文詞是希爾伯特的助手海因里?！へ惵?Heinrich Behmann, 1891—1970)創(chuàng)造的。在貝曼的想象中，判定過(guò)程是這樣的：

這個(gè)問(wèn)題的一個(gè)特性至關(guān)重要，就是證明過(guò)程只允許根據(jù)指令進(jìn)行純機(jī)械式的計(jì)算，不允許摻雜任何嚴(yán)格意義上的思考活動(dòng)。如果愿意，我們可以說(shuō)機(jī)械的或像機(jī)器一樣地思考（說(shuō)不定以后我們可以用機(jī)器來(lái)運(yùn)行這種過(guò)程）。

貝曼這番話是1921年5月10日在哥廷根數(shù)學(xué)協(xié)會(huì)關(guān)于判定問(wèn)題的座談會(huì)中講到的（這個(gè)材料近年才公開(kāi)^[8]）。

1928年，已屆暮年的希爾伯特在國(guó)際數(shù)學(xué)家大會(huì)上將判定問(wèn)題列為三大問(wèn)題之一，他夢(mèng)想得到一個(gè)肯定回答。英國(guó)數(shù)學(xué)家哈代對(duì)此嗤之以鼻，他指出^[7]：“當(dāng)然不存在這樣的公理，我們應(yīng)該感到慶幸，因?yàn)槿绻覀冋业搅艘惶讬C(jī)械的規(guī)則，為所有數(shù)學(xué)問(wèn)題提供解決方案，那么數(shù)學(xué)家的活動(dòng)就將結(jié)束?！?/span>

哈代和希爾伯特各執(zhí)一詞時(shí)，圖靈還在備考劍橋大學(xué)，攻讀的正是哈代的《純數(shù)學(xué)教程》。四年大學(xué)畢業(yè)后，他才第一次聽(tīng)到判定問(wèn)題，躺在劍橋草坪初夏溫暖的陽(yáng)光下，破解了兩大頂級(jí)數(shù)學(xué)家爭(zhēng)執(zhí)的世紀(jì)難題。

那是1936年，圖靈24歲，一個(gè)剛剛大學(xué)畢業(yè)的翩翩少年，為機(jī)械意義上的計(jì)算畫(huà)出了明確邊界。

這正是： 數(shù)可數(shù)，非常數(shù)

                實(shí)數(shù)不可數(shù)，實(shí)在在何處？

                計(jì)算又可數(shù)，其他為何物？

                其他可想不可及

                機(jī)可及，圖靈機(jī) 

作者介紹

黃鐵軍

·CCF杰出會(huì)員。

·北京大學(xué)教授，計(jì)算機(jī)科學(xué)技術(shù)系主任、數(shù)字媒體研究所所長(zhǎng)。

·主要研究方向?yàn)橐曈X(jué)信息處理和類腦計(jì)算。

腳注

¹ 岳麓書(shū)院講堂中一副對(duì)聯(lián)的前三句，由曠敏本撰書(shū)。曠敏本（1699—1782年），乾隆十九年（1754年）被聘為岳麓書(shū)院山長(zhǎng)，即現(xiàn)代意義上的“院長(zhǎng)”。

² 丟番圖方程(Diophantine equation)：有一個(gè)或者幾個(gè)變量的整系數(shù)方程，它們的求解僅僅在整數(shù)范圍內(nèi)進(jìn)行。丟番圖是古代希臘人，被譽(yù)為代數(shù)學(xué)的鼻祖，他早在公元3世紀(jì)就開(kāi)始研究不定方程，因此常稱不定方程為丟番圖方程。

參考文獻(xiàn)

[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.