孤獨(dú)的破譯者和他的計(jì)算機(jī)器（修訂稿）

作者：若奇

　　他出生于倫敦,，在遠(yuǎn)離父母的環(huán)境中孤獨(dú)地長(zhǎng)大,。從小學(xué)到中學(xué)，他由于性
格離群和糟糕的文科成績(jī)而飽受詬病,。但他卻從學(xué)習(xí)數(shù)學(xué)，閱讀相對(duì)論和量子力
學(xué)中獲得莫大樂趣,。從中學(xué)開始他可能不自覺地發(fā)展了同性戀的性取向,。他的第
一個(gè)精神“戀人”，一位才華橫溢,、與他對(duì)自然科學(xué)有著同樣熱愛的高年級(jí)同學(xué)
的突然去世,，對(duì)他打擊甚深，既讓他永遠(yuǎn)喪失了對(duì)宗教的信仰,，也激發(fā)了他揭開
人類智能活動(dòng)秘密的最初愿望,。

　　在劍橋大學(xué)國(guó)王學(xué)院，他受到哥廷根數(shù)理邏輯學(xué)派的熏陶,。大學(xué)畢業(yè)后的第
二年,，24歲的他就以3６頁的一篇傳世之作奠定了他在計(jì)算機(jī)科學(xué)史上的地位。
二次大戰(zhàn)中他領(lǐng)導(dǎo)英國(guó)情報(bào)機(jī)構(gòu)“第八室”,，為破解德國(guó)海軍“恩尼格瑪”密碼
系統(tǒng)立下汗馬功勞,，對(duì)盟軍在大西洋海戰(zhàn)中取得壓倒性優(yōu)勢(shì)貢獻(xiàn)巨大。二戰(zhàn)后他
在英國(guó)國(guó)家物理研究所設(shè)計(jì)的ACE計(jì)算機(jī)被認(rèn)為是第一臺(tái)真正意義上的現(xiàn)代計(jì)算
機(jī),。1950年他的另一篇開創(chuàng)性論文奠定了計(jì)算機(jī)人工智能的基礎(chǔ),。他作為世界上
第一個(gè)計(jì)算機(jī)“個(gè)人”用戶和第一個(gè)專職程序員，使用曼徹斯特大學(xué)“Mark-I”
計(jì)算機(jī),，單槍匹馬地創(chuàng)立了另一門學(xué)科“形態(tài)發(fā)生學(xué)”,。他興趣廣泛,，多才多藝，
在數(shù)學(xué),，量子力學(xué),，地學(xué)，化學(xué)和生物學(xué)等方面都卓有建樹,。

　　他性格孤獨(dú),，行為乖僻，有些害羞,。因?yàn)樗_的同性戀取向,，50年代初冷
戰(zhàn)開始后他失去了從事國(guó)家機(jī)密活動(dòng)的資格。1952年,，40歲的他被依據(jù)當(dāng)時(shí)英國(guó)
法律指控非法進(jìn)行同性戀活動(dòng),，他高傲而不肯為自己抗辯，但為了避免坐牢從而
得以繼續(xù)他的研究,，他不得不接受令他蒙羞的“激素治療”,。他身心俱焚，形吊
影單,，1954年6月的一天,，他被發(fā)現(xiàn)死于寓所的床上，身邊有一只被咬去幾口的
蘋果,。檢驗(yàn)證明這只蘋果被劇毒氰化物浸泡過,。他的死充滿疑云，但被警方判定
為自殺,。也許,，他以無聲的抗議走完了他短暫，輝煌而悲劇的一生,。他沒有留下
一句遺言,。

　　2009年9月10日，英國(guó)政府正式為他洗去沉冤,。布朗首相代表英國(guó)政府向他
因同性戀遭受的不公道歉,。他說，“我代表英國(guó)政府,、以及所有因他的工作而自
由生活的人們向他說：‘我們很抱歉,，你本應(yīng)得到更多的獎(jiǎng)賞。’”

　　這個(gè)人,，就是天才的英國(guó)數(shù)學(xué)家阿蘭?圖靈（Alan Turing,，1912-1954）。

　　二十世紀(jì)是人類歷史上科學(xué)技術(shù)發(fā)展最快的世紀(jì)。100年間,，涌現(xiàn)了大量對(duì)
世界產(chǎn)生重大的影響的科學(xué)和技術(shù)發(fā)現(xiàn),，包括量子力學(xué)，相對(duì)論,，抗生素,，基因
科學(xué)，飛機(jī),，電視等等,。但是，在上個(gè)世紀(jì)結(jié)束的時(shí)候,，如果要評(píng)選一項(xiàng)已經(jīng)滲
透至人們?nèi)粘Ｉ畹乃薪锹?，?duì)人類的工作和生活影響最大的本世紀(jì)科技發(fā)展
的話，則非計(jì)算機(jī)莫屬,。

　　如同提到經(jīng)典力學(xué)人們必然聯(lián)想起牛頓,，提到相對(duì)論人們必然聯(lián)想起愛因斯
坦，每項(xiàng)里程碑式的人類文明發(fā)展都有其領(lǐng)軍巨匠大師,。計(jì)算機(jī)的發(fā)展也不例外,。
阿蘭?圖靈的名字永遠(yuǎn)與計(jì)算機(jī)科學(xué)聯(lián)系在一起。作為人類創(chuàng)造性心智和抽象思
維的典范,，“圖靈機(jī)”亦將永垂科學(xué)青史,。“圖靈測(cè)試”仍是迄今為止公認(rèn)的判
定計(jì)算機(jī)是否具有智能的標(biāo)準(zhǔn)。

　　為了理解圖靈的主要貢獻(xiàn),，讓我們簡(jiǎn)單回顧一下19世紀(jì)20世紀(jì)之交數(shù)學(xué)界的
狀況,。

　　盡管數(shù)學(xué)在當(dāng)時(shí)已經(jīng)有了長(zhǎng)足的發(fā)展，人們?nèi)匀粚?duì)有關(guān)實(shí)數(shù)的一些基本性質(zhì)
感到困惑,。在解決實(shí)數(shù)是否可數(shù)的過程中，集合論創(chuàng)始人康托（Georg Cantor, 
1845-1918）發(fā)展了包含無限元素的集合的理論,?？低邪l(fā)現(xiàn)，無限集合的真子集
可以和原集合一樣“大”,，有可數(shù)的無限和不可數(shù)的無限等等,，這些概念都不是
直觀的。據(jù)說,，康托因?yàn)樗伎歼@些無限的大小和可數(shù)性而走火入魔,，后半生生活
在半瘋的狀態(tài)中，出入精神病院,，在數(shù)學(xué),，音樂，哲學(xué)和神學(xué)之間游走,。

　　人們意識(shí)到,，為了更準(zhǔn)確地理解世界,，必須借助嚴(yán)格和可靠的工具。以歐幾
里德幾何原理為代表的公理化方法漸入佳境,。

　　數(shù)學(xué)家們開始以前所未有的熱情和異乎尋常的嚴(yán)格來重新構(gòu)造數(shù)學(xué)的基礎(chǔ),。
皮亞諾(Giuseppe Peano, 1858-1932)建立了以公理系統(tǒng)為基礎(chǔ)的自然數(shù)的運(yùn)算
系統(tǒng)。弗雷澤(Gottlob Frege, 1848-1925)則更進(jìn)一步,，在集合論和數(shù)理邏輯的
基礎(chǔ)上建立了實(shí)數(shù)的運(yùn)算系統(tǒng),。著名數(shù)學(xué)家，近代數(shù)學(xué)的代表人物,，哥廷根學(xué)派
的掌門人希爾伯特(David Hilbert, 1862-1943)在實(shí)數(shù)系統(tǒng)的基礎(chǔ)上將歐氏幾何
全部重新推導(dǎo),，將其牢固地建立在前所未有的嚴(yán)格的數(shù)學(xué)根基上。

　　到了１９世紀(jì)行將結(jié)束的時(shí)候,，數(shù)學(xué)大廈似乎已經(jīng)構(gòu)建得十分宏偉堅(jiān)固,。以
希爾伯特為代表的數(shù)學(xué)家們對(duì)解決殘存的數(shù)學(xué)問題相當(dāng)樂觀。１９００年８月,，
在巴黎召開的第二屆世界數(shù)學(xué)家大會(huì)上,，希爾伯特應(yīng)邀致辭，他豪情滿懷,，信心
爆棚地宣稱：

　　無論這些難題看起來多么難以解決,，無論我們現(xiàn)在在它們面前如何困惑無助，
我們?nèi)詧?jiān)持這樣一個(gè)信念：這些難題的解決一定會(huì)遵循有限的純粹邏輯的過
程,。,。。每個(gè)數(shù)學(xué)問題都必然可解的這一信條是對(duì)數(shù)學(xué)家們的強(qiáng)有力激勵(lì),。我們
聽到來自內(nèi)心的永恒召喚：我們面臨難題,。我們要去尋找它的解。通過純粹推理,，
我們一定能找到它,。因?yàn)樵跀?shù)學(xué)中，絕對(duì)沒有“我們不可能知道”,！

　　接著,，他列舉了他所認(rèn)為新世紀(jì)應(yīng)該解決的２３個(gè)數(shù)學(xué)難題（其中許多至今
仍未解決），并挑戰(zhàn)他的數(shù)學(xué)同行在新世紀(jì)中解決它們,。

　　不僅在數(shù)學(xué)界,，而且在諸如物理，藝術(shù),，乃至社會(huì)方方面面,，人們普遍抱有
樂觀情緒，認(rèn)為新的世紀(jì)會(huì)帶來各種遺留問題的徹底解決。人類即將達(dá)到燦爛的
頂峰,。

　?。玻笆兰o(jì)帶來的，卻幾乎是徹底的相反,。

　　藝術(shù)上的反叛首先引人注目,。抽象派的立體、殘缺不全的幾何圖形顛覆了人
們對(duì)古典美的欣賞,。音樂界從斯塔文斯基開始,，喧鬧而不和諧的“雜亂無章”，
使得晚期浪漫主義風(fēng)格的瓦格納和德彪西顯得過于柔順,。物理學(xué)上的沖擊來自１
９０５年,，愛因斯坦的幾篇?jiǎng)潟r(shí)代論文徹底顛覆了牛頓經(jīng)典力學(xué)對(duì)時(shí)空的認(rèn)識(shí)。
１９１４年的一次世界大戰(zhàn)粉碎了人類和平的夢(mèng)想,，同時(shí)催生了數(shù)十年的以失敗
而告終的人類大規(guī)模社會(huì)主義試驗(yàn),。

　　在數(shù)學(xué)界，“破壞”也是料想不到的“天翻地覆”,。

　　世紀(jì)初的進(jìn)展似乎勢(shì)如破竹,。雄心勃勃的數(shù)學(xué)家羅素（Bertrand Russell, 
1872-1970,就是那個(gè)從英國(guó)維多利亞女王時(shí)代開始發(fā)表數(shù)學(xué)論文，最終活到抗議
越戰(zhàn)的諾貝爾文學(xué)獎(jiǎng)獲得者,，大名鼎鼎的“哲學(xué)家”羅素）,，和他的導(dǎo)師懷特黑
(Alfred Whitehead, 1861-1947)，在１９１２－１９１３年分三卷出版了長(zhǎng)達(dá)
兩千多頁的《數(shù)學(xué)原理》,。羅素用了和牛頓的等身名著類似的書名,，正是表現(xiàn)了
他的自信。幾年前,，他在思考集合論問題時(shí)提出了后來以他名字命名的“羅素悖
論”：一個(gè)只包含所有不含自身的集合的集合,，包含不包含它自己？簡(jiǎn)單的比方
就是那個(gè)著名的“理發(fā)師悖論”：一個(gè)只給所有不給自己修面的人修面的理發(fā)師,，
給不給自己修面,？他寫信給奠定了集合論基礎(chǔ)的弗雷澤求教，立刻使得弗雷澤
“精神崩潰”,，無法回避他畢生的工作存在這樣無法自圓其說的“漏洞”。羅素
自己擔(dān)起了為數(shù)學(xué)撥亂反正的重任,。他試圖將集合分成不同的類型,，每個(gè)類型只
能包含特定的類型，從而避免類似理發(fā)師悖論那樣由于自我引用導(dǎo)致的悖論,。他
和懷特黑用了幾十頁的篇幅,，最終成功地證明１＋１＝２（不是哥德巴赫猜想，
而是初等算術(shù)）,！

　　順便提及,，1957年,，紐維爾(Allen Newell, 1927-1992)等人使用計(jì)算機(jī)證
明了《數(shù)學(xué)原理》中的許多定理,。他們寫信將結(jié)果報(bào)知羅素,。羅素不無調(diào)侃地回
信說,，“得知《數(shù)學(xué)原理》現(xiàn)在可以被機(jī)器寫出,，我十分驚喜,?？上液蛻烟睾?
在浪費(fèi)十年心血寫出此書之前不知道這一可能”,。

　　希爾伯特進(jìn)一步明確了公理系統(tǒng)的四大要素：

　　獨(dú)立性：公理是最簡(jiǎn)約的，無冗余的,。
　　一致性：從公理出發(fā),，按照推理規(guī)則，不會(huì)推出相互矛盾的命題,。
　　完備性：從公理出發(fā)可以推出所有的真命題,。
　　可判定性：存在一個(gè)有限步驟的一般過程，可以判定任意一個(gè)命題的可證明
性,。

　　希爾伯特和他的學(xué)生艾克曼(Wilhelm Ackermann, 1896-1962)在《數(shù)理邏輯
原理》一書中建立了后來被稱之為“一階謂詞演算”的邏輯系統(tǒng),，其中特別包括
了完備性和可判定性的的討論。

　　奧地利人哥德爾(Kurt G?del, 1906-1978)的出現(xiàn),，先是給了希爾伯特們一
個(gè)志在必得的微笑,，而后給了他們狠狠一擊。

　　哥德爾在１９２９年首先證明,，希爾伯特的一階謂詞邏輯系統(tǒng)確實(shí)是完備的,，
能夠?qū)С鏊姓婷}?？梢韵胂笙柌貍儠?huì)稍帶不屑地說,，“不早告訴你了”。
１９３０年,，重磅炸彈橫空出世,。哥德爾進(jìn)一步證明，如果將算術(shù)運(yùn)算公理引入
一階謂詞系統(tǒng),，則由此而成的算術(shù)運(yùn)算系統(tǒng)是不完備的,，即存在這樣的命題，它
們的真?zhèn)问遣豢勺C明的,。這個(gè)結(jié)論的一個(gè)前提是,，算術(shù)運(yùn)算系統(tǒng)是一致的。由此
自然得到,，一致性的證明不可能從系統(tǒng)內(nèi)部完成,，即算術(shù)運(yùn)算系統(tǒng)的一致性不能
由其自身證明,！

　　顛覆是徹底而毀滅性的。希爾伯特和羅素賴以建立數(shù)學(xué)大廈的根基居然自己
就是建立在沙灘上,。據(jù)說,，希爾伯特聽到這個(gè)結(jié)論后“相當(dāng)憤怒”。羅素則徹底
喪失了對(duì)數(shù)理邏輯的興趣,，不知是寫作《數(shù)學(xué)原理》耗盡了他的心血,，還是哥德
爾定理擊碎了他的信心。用他自己的話說,，“從此我發(fā)現(xiàn)我對(duì)抽象問題的處理能
力肯定是大大降低了”,。他改而傾心哲學(xué)和文學(xué)，關(guān)注社會(huì)事務(wù),。當(dāng)他在１９５
０年獲得諾貝爾文學(xué)獎(jiǎng)時(shí),，人們?cè)缫淹浰?jīng)是個(gè)數(shù)學(xué)家。另一個(gè)當(dāng)時(shí)業(yè)已蜚
聲數(shù)學(xué)界,，以公理系統(tǒng)將量子力學(xué)形式化的哥廷根大學(xué)邏輯學(xué)家馮?諾依曼(John 
von Neumann, 1903-1957),，從此放棄了純粹數(shù)學(xué)的研究，而１０多年后卻因?qū)?
現(xiàn)代計(jì)算機(jī)的奠基和發(fā)展的貢獻(xiàn)而青史留名,。

　　然而,，希爾伯特應(yīng)該還存有希望。哥德爾的結(jié)果并未解決“可判定性”問題,。
哥德爾只是證明了,，邏輯系統(tǒng)中存在不可能判定真?zhèn)蔚拿}。然而,，一個(gè)系統(tǒng)是
不完備的,，并不等于不存在一般的判定過程，使得可以判定其中任意一個(gè)命題是
否可證,。在哥德爾不完備定理出世以后,，如果還能證明存在這樣的一般過程，退
而求次,，看起來還是可說很圓滿了,。

　　最后的“致命”一擊，來自美國(guó)數(shù)學(xué)家丘奇(Alonzo Church, 1905-1995)和
英國(guó)數(shù)學(xué)家圖靈,。１９３６年,，兩人幾乎同時(shí)，卻是獨(dú)立地循著完全不同的途徑,，
證明了“判定問題”的不可解性,。即不存在一般的過程，可以判定任意一個(gè)命題
在一階謂詞邏輯系統(tǒng)是否可證,。丘奇的方法是“蘭姆達(dá)演算”,，它現(xiàn)在只存在于
數(shù)理邏輯及其相關(guān)的若干狹窄研究領(lǐng)域中，雖然其對(duì)現(xiàn)代計(jì)算即程序語言如ALGOL, 
LISP和APL等等的發(fā)展也曾有重要影響,。圖靈的工具,，則是大名鼎鼎的“圖靈
機(jī)”。圖靈機(jī)對(duì)后世產(chǎn)生了深遠(yuǎn)的影響,，特別是對(duì)２０世紀(jì)以來的計(jì)算機(jī)發(fā)展起
到并且繼續(xù)發(fā)揮著革命性作用,。

　　簡(jiǎn)單地說，圖靈在其劃時(shí)代論文《論可計(jì)算數(shù)及其對(duì)判定問題的應(yīng)用》中作
出了以下開創(chuàng)性貢獻(xiàn)：

　　一．	定義了一種抽象的計(jì)算機(jī)器
　　二．	證明了能夠模擬任意計(jì)算機(jī)器的通用計(jì)算機(jī)器的存在性
　　三．	證明了存在任何計(jì)算機(jī)器都不能解決的問題

　　那么,，圖靈機(jī)到底是怎樣一個(gè)神通廣大的機(jī)器,？讓我們跟隨圖靈的論文，進(jìn)
入圖靈機(jī)的王國(guó),。

　　對(duì)于圖靈而言,，他的計(jì)算機(jī)器是一種思維模型，是只存在于紙上或頭腦里,，
模擬人們演算活動(dòng)而簡(jiǎn)化到了最基本操作的抽象思維工具,。這種抽象完全擯棄現(xiàn)
實(shí)世界時(shí)間和空間的限制，從而得以揭示事物的本質(zhì),。

　　圖靈試圖將人的計(jì)算過程還原為最基本的若干機(jī)械操作,。人在演算數(shù)學(xué)問題
時(shí)，面前有張寫著算式的紙,，腦子里記著演算規(guī)則,。演算過程的任一時(shí)刻，人只
關(guān)注于算式的某一部分和某一特定規(guī)則,，并據(jù)此寫下新的數(shù)字,，或擦除已有數(shù)字，
然后將關(guān)注轉(zhuǎn)向算式的另一部分和另一規(guī)則,，直到演算完畢,。圖靈論證說，這些
規(guī)則一定是有限的,，否則就會(huì)由于狀態(tài)無限接近而不可區(qū)分,。

　　這是天才的抽象。圖靈正是據(jù)此來構(gòu)造他的計(jì)算機(jī)器,。

　　圖靈機(jī)由有限的狀態(tài)（圖靈原文中稱為“m-配置”）組成,。可把狀態(tài)看作是
計(jì)算規(guī)則的模擬,。機(jī)器被送進(jìn)一條分成連續(xù)“格子”的“帶子”,，這些格子上可
以寫有數(shù)字或符號(hào)。顯然,，帶子是模擬寫著式子的紙,。任何時(shí)刻機(jī)器只能“看到”
當(dāng)前一個(gè)格子,。每個(gè)狀態(tài)“告訴”機(jī)器，根據(jù)當(dāng)前看到的符號(hào),，采取何種操作,，
以及下一個(gè)狀態(tài)是什么。圖靈機(jī)的操作非常“原始”,，只包括左移一格,，右移一
格，擦去當(dāng)前格子的符號(hào),，或者在當(dāng)前格子寫下新的符號(hào),。狀態(tài)和當(dāng)前符號(hào)構(gòu)成
圖靈機(jī)的一個(gè)“配置”。“配置”完全決定了圖靈機(jī)的行為,。計(jì)算機(jī)器“寫出”
的０和１的序列就是機(jī)器計(jì)算出來的結(jié)果,。

　　就是這些。沒有復(fù)雜的“指令”,，沒有五花八門的輸入輸出,，沒有多少ＧＢ
的存儲(chǔ)器，沒有強(qiáng)大的“ＣＰＵ”或控制器,。甚至連后來出現(xiàn)在許多介紹圖靈機(jī)
的文章中的“讀寫頭”,，在圖靈原文中也是隱含的。在用慣了現(xiàn)代計(jì)算機(jī)的人們
看來,，圖靈機(jī)可以說是“土得掉渣”,。

　　那么，這樣“簡(jiǎn)陋”的機(jī)器到底如何工作呢,？

　　圖靈在論文中給出了兩個(gè)具體計(jì)算機(jī)器的例子,，一個(gè)計(jì)算二進(jìn)制０.０１０
１０１。,。,。（十進(jìn)制的１／３），另一個(gè)計(jì)算超越數(shù)０.０１０１１０１１１
０１１１１.,。,。。我們來看計(jì)算1/3的例子,。我們只需一條空白帶子和四個(gè)狀態(tài)
來構(gòu)造這個(gè)圖靈機(jī)：
	
		配置				行為
	狀態(tài)　    當(dāng)前符號(hào)		操作	     下個(gè)狀態(tài)
	――――――――――――――――――――――――
	ｂ		空白		寫0,，右移	ｃ
	――――――――――――――――――――――――
	ｃ		空白		右移		e
	――――――――――――――――――――――――
	e		空白		寫1，右移	f
	————————————————————————
	f		空白		右移		b

　　初始狀態(tài)ｂ下,，機(jī)器在當(dāng)前格子上寫1,，然后右移一格，“轉(zhuǎn)到”狀態(tài)ｃ,。
ｃ看到當(dāng)前格子是空白,，于是右移,，然后轉(zhuǎn)到狀態(tài)e。e看到的仍是空白,，于是寫
1,，右移，并轉(zhuǎn)回狀態(tài)b,。如此永遠(yuǎn)“循環(huán)”下去，永不停歇,。機(jī)器“寫”出的結(jié)
果是010101.．．,。按圖靈的約定，結(jié)果應(yīng)按前面加上小數(shù)點(diǎn)理解,，于是我們得
到 0.010101．．．,，也就是十進(jìn)制的１／3。注意,，根據(jù)圖靈的定義,，只有永遠(yuǎn)
不停“寫出”0或1序列的機(jī)器才是正常的，“好”的機(jī)器,。

　　細(xì)心的讀者也許會(huì)發(fā)現(xiàn),，這個(gè)圖靈機(jī)實(shí)際上是隔一格打印一個(gè)數(shù)字。這正是
圖靈的匠心所在,。圖靈將帶子上的格子分為F-格（數(shù)字格）和E-格（可擦除符號(hào)
格）兩類,，一個(gè)F-格跟著一個(gè)E-格。計(jì)算結(jié)果由F-格表示,，E-格則用于“打標(biāo)
記”,，寫特殊符號(hào)，起到“臨時(shí)存儲(chǔ)”的作用,。對(duì)上面這個(gè)簡(jiǎn)單圖靈機(jī)而言,，還
用不到E-格。

　　圖靈機(jī)的操作是如此原始,，以至于連進(jìn)行簡(jiǎn)單加減運(yùn)算都需要許多繁復(fù)步驟
才能完成,。如果要計(jì)算更復(fù)雜的問題，豈非要算到“地老天荒“,？但圖靈對(duì)這些
具體運(yùn)算根本毫無興趣,。他所關(guān)心的不是要花多少時(shí)間，需要多長(zhǎng)的帶子才能完
成某個(gè)計(jì)算,，而是可不可能完成它,。

　　圖靈定義抽象計(jì)算機(jī)器的方法亦有很大彈性，改變一些細(xì)節(jié)并不影響可計(jì)算
的范圍,。下面的例子是一個(gè)對(duì)原始圖靈機(jī)定義略加改造的圖靈機(jī),，它的“輸入”
是一條所有格子都是空白的帶子,，它的功能是依次打出所有正整數(shù)（也就是完成
加1操作）：

		配置				行為
	狀態(tài)　    當(dāng)前符號(hào)		操作	     下個(gè)狀態(tài)
	――――――――――――――――――――――――
	b 		空白		P0		i

	i		0		P1		r
			1		P0,L		i
			空白		P1		r

	r		空白		L		i
			其他符號(hào)	R		r

　　其中操作Pn（Print）意為在當(dāng)前格子打印n，P0即打印0,。L（Left）和
R(Right)分別意為左移或右移一格,。狀態(tài)b可視為起始操作，打印數(shù)字0,，然后轉(zhuǎn)
到狀態(tài)i（increment,，加1）。根據(jù)當(dāng)前符號(hào),，i可以有三種動(dòng)作,。如果當(dāng)前符號(hào)
是0，則將其改為1,，這同時(shí)也就完成了加1操作,。如果當(dāng)前符號(hào)是1，則將其改為
0,，然后左移一格（進(jìn)位）,，重復(fù)i操作。如果當(dāng)前符號(hào)是空白,，說明進(jìn)位到了新
的最高位,，于是打印1。然后轉(zhuǎn)到狀態(tài)r（rewind,，回到最后一位有效數(shù)字）,。這
個(gè)圖靈機(jī)依次打印0，1,，10（十進(jìn)制2）,，11（十進(jìn)制3），100（十進(jìn)制4） 等
等,。讀者可以看到,，這個(gè)“加法器”對(duì)原始圖靈機(jī)有多處修改，例如,，它每次新
打印的數(shù)字都覆蓋了前一個(gè)數(shù)字,；它不使用E-格，也不隔格打??；它的結(jié)果向左
方而不是向右方“延伸”，等等,。

　　圖靈在論文的隨后幾頁為我們構(gòu)造了完成諸如搜索,，復(fù)制，擦除，“跑”到
帶子最左端,，跑到帶子右端最后一個(gè)格子,，比較，打標(biāo)記等等更為復(fù)雜動(dòng)作的狀
態(tài),。特別的,，他引入了“公共任務(wù)”的概念，用可以帶參數(shù)的m-函數(shù)表示,。以此
簡(jiǎn)化圖靈機(jī)的說明,。他很快就在論文中把這些函數(shù)稱為“指令”。我們也可以看
出這些函數(shù)和現(xiàn)代計(jì)算機(jī)程序語言中的子程序,，函數(shù),，循環(huán)，遞歸調(diào)用等構(gòu)造的
類似,。

　　事實(shí)上，圖靈在真正的自動(dòng)計(jì)算機(jī)出現(xiàn)前１０多年就開始“編程”了,。圖靈
將使用這些函數(shù)構(gòu)造他的“通用計(jì)算機(jī)器”,。

　　我們?cè)賮砜匆粋€(gè)圖靈論文中稍為復(fù)雜的m-函數(shù)的例子。“擦除從起始符號(hào)起
的第一個(gè)α”的函數(shù)e是這樣定義的：

	e(C,B,α)				f(e1(C,B,α),B,α)
	e1(C,B,α)		E		C

　　這里的E表示“擦除當(dāng)前符號(hào)α”,。m-函數(shù)e擦除第一個(gè)α,，然后轉(zhuǎn)到C。如
果不存在α,，則轉(zhuǎn)到B,。函數(shù)e的定義“引用”了一個(gè)已經(jīng)定義過的“搜索函數(shù)”
f，f完成搜索從起始符號(hào)э開始的第一個(gè)α的功能,。如果找到這樣的α,，機(jī)器轉(zhuǎn)
到狀態(tài)C，否則轉(zhuǎn)到狀態(tài)B,。在函數(shù)e的定義中,，C實(shí)際上e1（C, B，α）,。

　　圖靈接著定義了函數(shù)e的另一個(gè)版本：

	e(B, α)		e(e(B, α),B, α)

　　這個(gè)只有兩個(gè)參數(shù)的e“神通廣大”,。它首先“調(diào)用”三參數(shù)的e擦除帶子最
左邊的第一個(gè)α,然后轉(zhuǎn)到三參數(shù)的e的第一個(gè)參數(shù)表示的狀態(tài)，而這個(gè)狀態(tài)正好
又是兩參數(shù)的e,。于是又去“調(diào)用”三參數(shù)的e,，擦除當(dāng)前的第一個(gè)α（也就是原
來的第二個(gè)α），等等,，直到所有的α都被擦除,，機(jī)器轉(zhuǎn)到狀態(tài)B。了解計(jì)算機(jī)
編程的讀者已經(jīng)看出，這里包含了計(jì)算機(jī)程序設(shè)計(jì)中的遞歸調(diào)用,，以及許多老一
代程序語言都不支持的函數(shù)“overloading”,。圖靈的思想確實(shí)大大超前于時(shí)代。

　　圖靈機(jī)也可以視為“算法（algorithm）”的體現(xiàn),。算法以有限的符號(hào),，有
限的步驟，精確地描述一類計(jì)算過程,。實(shí)際上,，圖靈機(jī)后來被廣泛地用于算法研
究。

　　圖靈機(jī)的計(jì)算結(jié)果是一個(gè)可計(jì)算序列,。顯然,，對(duì)一個(gè)可計(jì)算序列，可以構(gòu)造
不同的圖靈機(jī),，它們的計(jì)算結(jié)果相同,。為了用一種標(biāo)準(zhǔn)方式表達(dá)圖靈機(jī)的結(jié)構(gòu)，
他將圖靈機(jī)的配置“規(guī)范化”一個(gè)五元組

　?。ó?dāng)前狀態(tài),，當(dāng)前符號(hào)，要寫的新符號(hào),，移動(dòng)方向,，下一狀態(tài)）

　　如果將所有m-函數(shù)展開，任何圖靈機(jī)都可由這樣一組有限的五元組表示,。為
了規(guī)范化,，圖靈規(guī)定，擦除操作相當(dāng)于打印空白符號(hào),，保持當(dāng)前符號(hào)不變相當(dāng)于
打印當(dāng)前符號(hào),。然后將所有的配置，符號(hào)和動(dòng)作都分別排上序號(hào),，比如,，對(duì)某個(gè)
特定的有20個(gè)狀態(tài)，使用15個(gè)符號(hào)的圖靈機(jī),，狀態(tài)用帶下標(biāo)的q表示,，即ｑ從q１
到q２０，符號(hào)用帶下標(biāo)的Ｓ表示,，即從S１到S１５（其中S0是空白,，Ｓ１是數(shù)
字０，Ｓ２是數(shù)字１）,。再以字母A代替q的下標(biāo)：狀態(tài)ｑ１表示為ＤＡ,，ｑ２表
示為ＤＡＡ,，qi表示為D后跟隨i個(gè)A; 用字母C替代符號(hào)S的下標(biāo)：Ｓ１表示為Ｄ
Ｃ，Ｓ２表示為ＤＣＣ,， Sj表示為D后跟隨j個(gè)C等等,。動(dòng)作用L或R表示右移和或
左移，用N表示不移動(dòng),。這樣,，計(jì)算１／３的圖靈機(jī)可以寫成下列標(biāo)準(zhǔn)表達(dá)式
（S.D, Standard Description，其中分號(hào)分開各個(gè)五元組）：

	ＤＡＤＤＣＲＤＡＡ,；ＤＡＡＤＤＲＤＡＡＡ,；ＤＡＡＡＤＤＣＣＤＡＡＡＡ；ＤＡＡＡＡＤＤＲＤＡ,；

　　圖靈實(shí)際上是用有限的符號(hào)為他的計(jì)算機(jī)器編碼,。進(jìn)一步，如果用數(shù)字表示
每個(gè)不同字母,，比如１表示Ａ,，２表示Ｃ，３表示Ｄ,，４表示Ｌ,，５表示Ｒ，6
表示N,７表示分號(hào),；則數(shù)字
	
３１３３２５３１１７３１１３３５３１１１７３１１１３３２２５３１１１１７３１１１１３３５３１７

　　就是該圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)數(shù)（D.N）。D.N（亦即S.D）唯一地確定一個(gè)圖靈
機(jī)的結(jié)構(gòu),，也就是唯一一個(gè)可計(jì)算序列,。反過來，對(duì)每個(gè)可計(jì)算序列,，至少存在
一個(gè)標(biāo)準(zhǔn)表達(dá)數(shù),。不難想象，絕大部分任意正整數(shù)都不是一個(gè)合格的圖靈機(jī)的標(biāo)
準(zhǔn)表達(dá)數(shù),。事實(shí)上,，最小的可作為圖靈機(jī)標(biāo)準(zhǔn)表達(dá)數(shù)的正整數(shù)是３１３３４３１
７（只打印空格！因此,，這個(gè)圖靈機(jī)按圖靈的定義是一個(gè)不好的機(jī)器）,。最小的
完全符合圖靈定義的“好”圖靈機(jī)標(biāo)準(zhǔn)表達(dá)數(shù)是313325317（計(jì)算0.1111.。,。）,。

　　圖靈還定義了“完全配置”的概念。在圖靈機(jī)工作的任一階段,，被查看的格
子的序號(hào),，帶子上的全部符號(hào)，以及當(dāng)前的狀態(tài)，構(gòu)成此階段的圖靈機(jī)的一個(gè)
“完全配置”,。形象地說,，這就是圖靈機(jī)的一個(gè)“快照”。

　　繞了這么大一個(gè)圈子,，圖靈到底要干什么,？別急。好戲才剛開場(chǎng),。

　　圖靈下面要做的,，是一個(gè)絕對(duì)天才的創(chuàng)造：他要構(gòu)造一個(gè)“通用計(jì)算機(jī)器”，
只要給這臺(tái)機(jī)器提供寫有某個(gè)圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)的帶子,，就可以模擬這個(gè)圖靈機(jī)
的計(jì)算,，得出相同的可計(jì)算序列。圖靈論文的第６和第７節(jié)詳細(xì)給出了通用圖靈
機(jī)的構(gòu)造和所有狀態(tài),，用到了我們上面提到的那些m-函數(shù),。圖靈證明，如此構(gòu)造
的這個(gè)通用圖靈機(jī)的計(jì)算結(jié)果正好就是提供給它的標(biāo)準(zhǔn)表達(dá)所代表的那個(gè)圖靈機(jī)
的結(jié)果,。

　　對(duì)通用圖靈機(jī)構(gòu)造的詳細(xì)描述超出本文的篇幅,。粗略地說，其“輸入”是寫
有任一欲被模擬的特定圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)式（由D,A,C,L,R,N和,；編碼而成）的
帶子,，“輸出”是被模擬的圖靈機(jī)的一個(gè)個(gè)相續(xù)的完全配置，以及每個(gè)完全配置
所對(duì)應(yīng)的當(dāng)前打印數(shù)字,。這個(gè)相續(xù)的數(shù)字序列正是被模擬圖靈機(jī)的計(jì)算結(jié)果,。如
此，則通用圖靈機(jī)可以“惟妙惟肖”地模擬任一特定圖靈機(jī)的工作,。

　　到目前為止一切似乎進(jìn)展順利,。我們已經(jīng)有了神通廣大可以模擬任何圖靈機(jī)
的通用圖靈機(jī)。圖靈還將給我們帶來何種驚喜,？

　　不幸的是,，圖靈很快就給我們的熱切期待澆上一盆涼水：圖靈機(jī)并非萬能。
利用通用圖靈機(jī),，他巧妙地證明了,，不可能構(gòu)造這樣一個(gè)圖靈機(jī)，當(dāng)給它提供任
意一個(gè)圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)后,，能判定該機(jī)器是否是“好”的（即是否能夠無休止
地打印數(shù)字）,，甚至不能判定任意一個(gè)圖靈機(jī)是否最終會(huì)打印一個(gè)0。

　　盡管通用圖靈機(jī)“仿誰象誰”,，但它并無“三歲看小,，七歲看老”的未卜先
知的本事,。

　　圖靈論文的最終目的是證明希爾伯特“判定問題”無解。為此,，圖靈將圖靈
機(jī)的標(biāo)準(zhǔn)表達(dá)和數(shù)理邏輯的一階謂詞演算聯(lián)系起來,。

　　一階謂詞是這樣的一類邏輯表達(dá)式，例如
	
	（ｘ）（ｙ）（Ｇ（ｘ,，ｙ）－＞?。牵ǎ?

　　式子的意義可以不同,，但表示某種交換律,，對(duì)偶關(guān)系。比如一個(gè)解釋是,，
（ｘ）,，（ｙ）表示對(duì)所有的人ｘ和ｙ，Ｇ（ａ,，ｂ）表示“ａ是ｂ的親戚”,。
－＞表示“可推出”，“隱含”,。在上述解釋下,，式子的意思是，如果ｘ是ｙ的
親戚,，那么ｙ也是ｘ的親戚,。

　　圖靈用若干邏輯式來表達(dá)圖靈機(jī)配置的五元組，這樣,，一個(gè)圖靈機(jī)就可以用
邏輯式的“邏輯積”來表達(dá),。然后，通過將希爾伯特的“判定問題”表達(dá)為一個(gè)
更為復(fù)雜的邏輯公式,，成功地將問題轉(zhuǎn)化為“如果判定問題有解（即存在一般判
定過程）,，則存在一個(gè)圖靈機(jī),，它能判定被它模擬的圖靈機(jī)最終是否打?。?#8221;。
我們已經(jīng)知道,，這樣的圖靈機(jī)不存在,，因此，一般的“判定過程”不存在,。

　　至此,，圖靈圓滿地解決了希爾伯特的判定問題。

　　以圖靈機(jī)作為工具,，圖靈繼而證明了一大類數(shù)字(包括π和е)和函數(shù)是可被
圖靈機(jī)計(jì)算的,。不僅如此,，圖靈機(jī)還能證明希爾伯特一階謂詞系統(tǒng)中所有可證公
式。現(xiàn)在人們一般接受,，任何直覺上可計(jì)算的數(shù)和函數(shù),，都可以被圖靈機(jī)計(jì)算。
而無法用圖靈機(jī)計(jì)算的,，本質(zhì)上也是不可計(jì)算的,。因此，圖靈機(jī)的計(jì)算能力與直
覺上人作為計(jì)算者的能力本質(zhì)上相同,。這是對(duì)人類智慧及其局限的深刻洞察,。

　　在1936年，我們有了三種關(guān)于可計(jì)算性的定義：圖靈的通用圖靈機(jī),，哥德爾
的遞歸函數(shù),，和丘奇的蘭姆達(dá)函數(shù)。圖靈證明了圖靈機(jī)與蘭姆達(dá)函數(shù)的等價(jià),。后
來,，丘奇的學(xué)生科雷尼(Stephen Kleene, 1909-1994)證明了遞歸函數(shù)與蘭姆達(dá)
函數(shù)的等價(jià)。于是這三個(gè)表面上似乎不相關(guān)的定義被統(tǒng)一起來,，揭示了可計(jì)算性
的本質(zhì),。

　　正如一部關(guān)于可計(jì)算性理論的著名專著中所評(píng)價(jià)的，“圖靈關(guān)于通用圖靈機(jī)
存在的定理是上個(gè)世紀(jì)的智力里程碑之一”,。

　　通用圖靈機(jī)可以說是現(xiàn)代“存儲(chǔ)程序通用計(jì)算機(jī)”的雛形,。圖靈的思維是革
命性的。他的構(gòu)造中已經(jīng)有了“軟件”的思想：標(biāo)準(zhǔn)表達(dá)就是一個(gè)計(jì)算程序,。程
序和數(shù)據(jù)被同樣“輸入”和“存儲(chǔ)”,，計(jì)算機(jī)是通用的，其工作由程序控制,。這
些幾乎１０年后才由被后人稱為“計(jì)算機(jī)之父”的馮?諾依曼總結(jié)提煉而成為現(xiàn)
代計(jì)算機(jī)體系結(jié)構(gòu)核心的思想,，至少部分歸功于圖靈。馮?諾依曼對(duì)從圖靈那里
所獲得的啟發(fā)從不諱言,。１９３６到１９３８年,，圖靈在美國(guó)普林斯頓大學(xué)師從
丘奇攻讀博士學(xué)位，馮?諾依曼當(dāng)時(shí)正在那里任教,，兩人過從甚密,。圖靈獲得學(xué)
位后，馮?諾依曼曾表示希望雇用圖靈在普林斯頓工作,。圖靈謝絕了,，回到英國(guó)，
不久即進(jìn)入皇家密碼學(xué)校,，即戰(zhàn)時(shí)的英國(guó)密碼破譯中心,，開始了幫助英國(guó)和盟軍
擊敗德國(guó)的密碼破譯工作,。

　　現(xiàn)代通用計(jì)算機(jī)（也就是現(xiàn)在遍布于世的大小電腦）的計(jì)算能力本質(zhì)上不超
過通用圖靈機(jī)。也就是說,，圖靈在現(xiàn)代計(jì)算機(jī)誕生10年以前就不但證明了它可以
做什么,，而且也證明了它不能做什么！

　　圖靈機(jī)的意義早已超越了對(duì)證明“判定問題”的應(yīng)用,。由于圖靈機(jī)深刻體現(xiàn)
了人類機(jī)械思維的本質(zhì),，它成為一個(gè)通用工具。許多數(shù)學(xué)家和數(shù)理邏輯學(xué)家使用
它（通常是改造后的變體）來證明一些復(fù)雜的數(shù)學(xué)定理,。圖靈機(jī)至今仍是研究算
法復(fù)雜性和可計(jì)算性的重要手段,，亦是研究形式語言與自動(dòng)機(jī)的基本工具。圖靈
機(jī)也被用于研究人腦,，神經(jīng)網(wǎng)絡(luò)和思維的機(jī)制,。甚至有人以圖靈機(jī)作為研究宇宙
的模型。

　　當(dāng)圖靈和丘奇的否定性結(jié)果發(fā)表時(shí),，希爾伯特剛剛退休,。他的哥廷根大學(xué)數(shù)
學(xué)系作為世界數(shù)學(xué)中心的地位，由于德國(guó)瘋狂的反猶浪潮,，也已經(jīng)岌岌可危,。大
批優(yōu)秀的猶太血統(tǒng)數(shù)學(xué)家不得不背井離鄉(xiāng)，遠(yuǎn)走高飛,。據(jù)說,，一次宴會(huì)上，希爾
伯特碰巧坐在德國(guó)教育部長(zhǎng)身旁,，部長(zhǎng)關(guān)心地問道,，現(xiàn)在哥廷根的數(shù)學(xué)研究情況
如何？希爾伯特不無悲傷地說,，“數(shù)學(xué),？哥廷根現(xiàn)在哪還有什么數(shù)學(xué)！”,。希爾
伯特在其生命的最后１２年從未對(duì)哥德爾和圖靈的證明公開發(fā)表評(píng)論,。他死后，
墓碑上刻著“我們必須知道,，我們能夠知道,！”,。

　　知道我們能做什么固然很好,，知道我們不能做什么也很重要。比如,，有了熱
力學(xué)第二定律,，我們就知道任何形式的“永動(dòng)機(jī)”是不可能的,。有人向你兜售永
動(dòng)機(jī)，你就知道他必然是騙子,。有了“判定過程”的不存在性,，我們也就不會(huì)再
費(fèi)神勞力企圖發(fā)明一種萬能驗(yàn)證程序，可以查出任意程序的“蟲子”,，或者判定
任意程序的最終結(jié)果,。等等。

　　圖靈發(fā)明了抽象的圖靈機(jī),，制造過破譯密碼的電動(dòng)解碼機(jī),，也設(shè)計(jì)過當(dāng)時(shí)體
系結(jié)構(gòu)領(lǐng)先的真正的可編程序帶存儲(chǔ)器的電子計(jì)算機(jī)ACE。他的設(shè)計(jì)思想和編程
理念被應(yīng)用到了曼徹斯特大學(xué)“馬克Ｉ”計(jì)算機(jī)上,，并深刻影響了后世,。他的
“機(jī)器指令集”類似于３０年后才開始流行的“簡(jiǎn)約指令體系結(jié)構(gòu)”（RISC）思
想。這是圖靈思想遠(yuǎn)超時(shí)代的另一證明,。

　　圖靈一生都在思考人的心智如何“運(yùn)算”,，能否用機(jī)器模擬的問題。１９５
０年,，他在另一篇影響深遠(yuǎn)的論文《計(jì)算機(jī)器與智能》中提出了“機(jī)器能否思考”
的問題,，并給出了機(jī)器智能的判定標(biāo)準(zhǔn)，即后來被稱為“圖靈測(cè)試”,。他提出,，
如果一個(gè)測(cè)試人對(duì)處于黑室中的一臺(tái)機(jī)器和一個(gè)人提出問題，經(jīng)過一段充分時(shí)間
“較量”,，他不能從答案中分出哪個(gè)是人,，哪個(gè)是機(jī)器，就可以認(rèn)為機(jī)器擁有了
智能,。這篇文章被認(rèn)為是人工智能的開山之作,。

　　圖靈曾樂觀地預(yù)言，到２０世紀(jì)末,，機(jī)器智能將能夠達(dá)到以７０％的成功率
通過圖靈測(cè)試,。或者由于圖靈英年早逝,，后繼乏人,，或者由于我們對(duì)智能的本質(zhì)
還遠(yuǎn)未了解，我們現(xiàn)在離這個(gè)標(biāo)準(zhǔn)還差的太遠(yuǎn)?，F(xiàn)在世界上每年都舉行機(jī)器智能
大賽,，但參賽者都心知肚明，不敢妄稱試圖通過圖靈測(cè)試,，而只是期望擊敗自己
的機(jī)器人對(duì)手,。近兩年的大賽獲勝者是一個(gè)叫做Ａｌｉｃｅ的機(jī)器,，“她”現(xiàn)在
有一個(gè)網(wǎng)站
　　	http://alicebot./
　　誰愿意都可以和她聊天。偶爾她也會(huì)說出很“聰明”的話,。不過很容易判斷,，
她的“智能”十分有限。

　　圖靈為我們留下了永久的遺產(chǎn),。他的智慧結(jié)晶,，圖靈機(jī)，現(xiàn)在仍然是人們探
索人類自身能力和局限的有力工具,。圖靈孤獨(dú)而默默地離開了我們,，留下了許多
奧秘和疑團(tuán)。就像人類面臨的其他許多奧秘一樣,，我們有可能最終找到其中一些
的答案,。還有很多，我們甚至將永遠(yuǎn)無法知道,，它們是不是有答案,。