孤獨(dú)的破譯者和他的計(jì)算機(jī)器（修訂稿）作者：若奇 他出生于倫敦，在遠(yuǎn)離父母的環(huán)境中孤獨(dú)地長大。從小學(xué)到中學(xué)，他由于性格離群和糟糕的文科成績而飽受詬病。但他卻從學(xué)習(xí)數(shù)學(xué)，閱讀相對論和量子力學(xué)中獲得莫大樂趣。從中學(xué)開始他可能不自覺地發(fā)展了同性戀的性取向。他的第一個(gè)精神“戀人”，一位才華橫溢、與他對自然科學(xué)有著同樣熱愛的高年級(jí)同學(xué)的突然去世，對他打擊甚深，既讓他永遠(yuǎn)喪失了對宗教的信仰，也激發(fā)了他揭開人類智能活動(dòng)秘密的最初愿望?！ ≡趧虼髮W(xué)國王學(xué)院，他受到哥廷根數(shù)理邏輯學(xué)派的熏陶。大學(xué)畢業(yè)后的第二年，24歲的他就以3６頁的一篇傳世之作奠定了他在計(jì)算機(jī)科學(xué)史上的地位。二次大戰(zhàn)中他領(lǐng)導(dǎo)英國情報(bào)機(jī)構(gòu)“第八室”，為破解德國海軍“恩尼格瑪”密碼系統(tǒng)立下汗馬功勞，對盟軍在大西洋海戰(zhàn)中取得壓倒性優(yōu)勢貢獻(xiàn)巨大。二戰(zhàn)后他在英國國家物理研究所設(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)開始后他失去了從事國家機(jī)密活動(dòng)的資格。1952年，40歲的他被依據(jù)當(dāng)時(shí)英國法律指控非法進(jìn)行同性戀活動(dòng)，他高傲而不肯為自己抗辯，但為了避免坐牢從而得以繼續(xù)他的研究，他不得不接受令他蒙羞的“激素治療”。他身心俱焚，形吊影單，1954年6月的一天，他被發(fā)現(xiàn)死于寓所的床上，身邊有一只被咬去幾口的蘋果。檢驗(yàn)證明這只蘋果被劇毒氰化物浸泡過。他的死充滿疑云，但被警方判定為自殺。也許，他以無聲的抗議走完了他短暫，輝煌而悲劇的一生。他沒有留下一句遺言?！ ?009年9月10日，英國政府正式為他洗去沉冤。布朗首相代表英國政府向他因同性戀遭受的不公道歉。他說，“我代表英國政府、以及所有因他的工作而自由生活的人們向他說：‘我們很抱歉，你本應(yīng)得到更多的獎(jiǎng)賞。’” 這個(gè)人，就是天才的英國數(shù)學(xué)家阿蘭?圖靈（Alan Turing，1912-1954）。 二十世紀(jì)是人類歷史上科學(xué)技術(shù)發(fā)展最快的世紀(jì)。100年間，涌現(xiàn)了大量對世界產(chǎn)生重大的影響的科學(xué)和技術(shù)發(fā)現(xiàn)，包括量子力學(xué)，相對論，抗生素，基因科學(xué)，飛機(jī)，電視等等。但是，在上個(gè)世紀(jì)結(jié)束的時(shí)候，如果要評(píng)選一項(xiàng)已經(jīng)滲透至人們?nèi)粘Ｉ畹乃薪锹?，對人類的工作和生活影響最大的本世紀(jì)科技發(fā)展的話，則非計(jì)算機(jī)莫屬?！ ∪缤岬浇?jīng)典力學(xué)人們必然聯(lián)想起牛頓，提到相對論人們必然聯(lián)想起愛因斯坦，每項(xiàng)里程碑式的人類文明發(fā)展都有其領(lǐng)軍巨匠大師。計(jì)算機(jī)的發(fā)展也不例外。阿蘭?圖靈的名字永遠(yuǎn)與計(jì)算機(jī)科學(xué)聯(lián)系在一起。作為人類創(chuàng)造性心智和抽象思維的典范，“圖靈機(jī)”亦將永垂科學(xué)青史。“圖靈測試”仍是迄今為止公認(rèn)的判定計(jì)算機(jī)是否具有智能的標(biāo)準(zhǔn)?！ 榱死斫鈭D靈的主要貢獻(xiàn)，讓我們簡單回顧一下19世紀(jì)20世紀(jì)之交數(shù)學(xué)界的狀況?！ ”M管數(shù)學(xué)在當(dāng)時(shí)已經(jīng)有了長足的發(fā)展，人們?nèi)匀粚τ嘘P(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é)之間游走?！ ∪藗円庾R(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é)根基上?！ 〉搅耍保故兰o(jì)行將結(jié)束的時(shí)候，數(shù)學(xué)大廈似乎已經(jīng)構(gòu)建得十分宏偉堅(jiān)固。以希爾伯特為代表的數(shù)學(xué)家們對解決殘存的數(shù)學(xué)問題相當(dāng)樂觀。１９００年８月，在巴黎召開的第二屆世界數(shù)學(xué)家大會(huì)上，希爾伯特應(yīng)邀致辭，他豪情滿懷，信心爆棚地宣稱： 無論這些難題看起來多么難以解決，無論我們現(xiàn)在在它們面前如何困惑無助，我們?nèi)詧?jiān)持這樣一個(gè)信念：這些難題的解決一定會(huì)遵循有限的純粹邏輯的過程。。。每個(gè)數(shù)學(xué)問題都必然可解的這一信條是對數(shù)學(xué)家們的強(qiáng)有力激勵(lì)。我們聽到來自內(nèi)心的永恒召喚：我們面臨難題。我們要去尋找它的解。通過純粹推理，我們一定能找到它。因?yàn)樵跀?shù)學(xué)中，絕對沒有“我們不可能知道”！ 接著，他列舉了他所認(rèn)為新世紀(jì)應(yīng)該解決的２３個(gè)數(shù)學(xué)難題（其中許多至今仍未解決），并挑戰(zhàn)他的數(shù)學(xué)同行在新世紀(jì)中解決它們。 不僅在數(shù)學(xué)界，而且在諸如物理，藝術(shù)，乃至社會(huì)方方面面，人們普遍抱有樂觀情緒，認(rèn)為新的世紀(jì)會(huì)帶來各種遺留問題的徹底解決。人類即將達(dá)到燦爛的頂峰。 ?。玻笆兰o(jì)帶來的，卻幾乎是徹底的相反?！ ∷囆g(shù)上的反叛首先引人注目。抽象派的立體、殘缺不全的幾何圖形顛覆了人們對古典美的欣賞。音樂界從斯塔文斯基開始，喧鬧而不和諧的“雜亂無章”，使得晚期浪漫主義風(fēng)格的瓦格納和德彪西顯得過于柔順。物理學(xué)上的沖擊來自１９０５年，愛因斯坦的幾篇?jiǎng)潟r(shí)代論文徹底顛覆了牛頓經(jīng)典力學(xué)對時(shí)空的認(rèn)識(shí)。１９１４年的一次世界大戰(zhàn)粉碎了人類和平的夢想，同時(shí)催生了數(shù)十年的以失敗而告終的人類大規(guī)模社會(huì)主義試驗(yàn)?！ ≡跀?shù)學(xué)界，“破壞”也是料想不到的“天翻地覆”?！ ∈兰o(jì)初的進(jìn)展似乎勢如破竹。雄心勃勃的數(shù)學(xué)家羅素（Bertrand Russell, 1872-1970,就是那個(gè)從英國維多利亞女王時(shí)代開始發(fā)表數(shù)學(xué)論文，最終活到抗議越戰(zhàn)的諾貝爾文學(xué)獎(jiǎng)獲得者，大名鼎鼎的“哲學(xué)家”羅素），和他的導(dǎo)師懷特黑(Alfred Whitehead, 1861-1947)，在１９１２－１９１３年分三卷出版了長達(dá)兩千多頁的《數(shù)學(xué)原理》。羅素用了和牛頓的等身名著類似的書名，正是表現(xiàn)了他的自信。幾年前，他在思考集合論問題時(shí)提出了后來以他名字命名的“羅素悖論”：一個(gè)只包含所有不含自身的集合的集合，包含不包含它自己？簡單的比方就是那個(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ī)器寫出，我十分驚喜?？上液蛻烟睾谠诶速M(fèi)十年心血寫出此書之前不知道這一可能”?！ ∠柌剡M(jìn)一步明確了公理系統(tǒng)的四大要素： 獨(dú)立性：公理是最簡約的，無冗余的?！ ∫恢滦裕簭墓沓霭l(fā)，按照推理規(guī)則，不會(huì)推出相互矛盾的命題?！ ⊥陚湫裕簭墓沓霭l(fā)可以推出所有的真命題。 可判定性：存在一個(gè)有限步驟的一般過程，可以判定任意一個(gè)命題的可證明性?！ ∠柌睾退膶W(xué)生艾克曼(Wilhelm Ackermann, 1896-1962)在《數(shù)理邏輯原理》一書中建立了后來被稱之為“一階謂詞演算”的邏輯系統(tǒng)，其中特別包括了完備性和可判定性的的討論?！ W地利人哥德爾(Kurt G?del, 1906-1978)的出現(xiàn)，先是給了希爾伯特們一個(gè)志在必得的微笑，而后給了他們狠狠一擊?！ 「绲聽栐冢保梗玻鼓晔紫茸C明，希爾伯特的一階謂詞邏輯系統(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)憤怒”。羅素則徹底喪失了對數(shù)理邏輯的興趣，不知是寫作《數(shù)學(xué)原理》耗盡了他的心血，還是哥德爾定理擊碎了他的信心。用他自己的話說，“從此我發(fā)現(xiàn)我對抽象問題的處理能力肯定是大大降低了”。他改而傾心哲學(xué)和文學(xué)，關(guān)注社會(huì)事務(wù)。當(dāng)他在１９５０年獲得諾貝爾文學(xué)獎(jiǎng)時(shí)，人們早已忘記他曾經(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ū)ΜF(xiàn)代計(jì)算機(jī)的奠基和發(fā)展的貢獻(xiàn)而青史留名。 然而，希爾伯特應(yīng)該還存有希望。哥德爾的結(jié)果并未解決“可判定性”問題。哥德爾只是證明了，邏輯系統(tǒng)中存在不可能判定真?zhèn)蔚拿}。然而，一個(gè)系統(tǒng)是不完備的，并不等于不存在一般的判定過程，使得可以判定其中任意一個(gè)命題是否可證。在哥德爾不完備定理出世以后，如果還能證明存在這樣的一般過程，退而求次，看起來還是可說很圓滿了?！ ∽詈蟮?#8220;致命”一擊，來自美國數(shù)學(xué)家丘奇(Alonzo Church, 1905-1995)和英國數(shù)學(xué)家圖靈。１９３６年，兩人幾乎同時(shí)，卻是獨(dú)立地循著完全不同的途徑，證明了“判定問題”的不可解性。即不存在一般的過程，可以判定任意一個(gè)命題在一階謂詞邏輯系統(tǒng)是否可證。丘奇的方法是“蘭姆達(dá)演算”，它現(xiàn)在只存在于數(shù)理邏輯及其相關(guān)的若干狹窄研究領(lǐng)域中，雖然其對現(xiàn)代計(jì)算即程序語言如ALGOL, LISP和APL等等的發(fā)展也曾有重要影響。圖靈的工具，則是大名鼎鼎的“圖靈機(jī)”。圖靈機(jī)對后世產(chǎn)生了深遠(yuǎn)的影響，特別是對２０世紀(jì)以來的計(jì)算機(jī)發(fā)展起到并且繼續(xù)發(fā)揮著革命性作用?！ 『唵蔚卣f，圖靈在其劃時(shí)代論文《論可計(jì)算數(shù)及其對判定問題的應(yīng)用》中作出了以下開創(chuàng)性貢獻(xiàn)： 一． 定義了一種抽象的計(jì)算機(jī)器 二． 證明了能夠模擬任意計(jì)算機(jī)器的通用計(jì)算機(jī)器的存在性 三． 證明了存在任何計(jì)算機(jī)器都不能解決的問題 那么，圖靈機(jī)到底是怎樣一個(gè)神通廣大的機(jī)器？讓我們跟隨圖靈的論文，進(jìn)入圖靈機(jī)的王國?！ τ趫D靈而言，他的計(jì)算機(jī)器是一種思維模型，是只存在于紙上或頭腦里，模擬人們演算活動(dòng)而簡化到了最基本操作的抽象思維工具。這種抽象完全擯棄現(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ī)可以說是“土得掉渣”?！ ∧敲矗@樣“簡陋”的機(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ǔ)”的作用。對上面這個(gè)簡單圖靈機(jī)而言，還用不到E-格?！ D靈機(jī)的操作是如此原始，以至于連進(jìn)行簡單加減運(yùn)算都需要許多繁復(fù)步驟才能完成。如果要計(jì)算更復(fù)雜的問題，豈非要算到“地老天荒“？但圖靈對這些具體運(yùn)算根本毫無興趣。他所關(guān)心的不是要花多少時(shí)間，需要多長的帶子才能完成某個(gè)計(jì)算，而是可不可能完成它?！ D靈定義抽象計(jì)算機(jī)器的方法亦有很大彈性，改變一些細(xì)節(jié)并不影響可計(jì)算的范圍。下面的例子是一個(gè)對原始圖靈機(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è)“加法器”對原始圖靈機(jī)有多處修改，例如，它每次新打印的數(shù)字都覆蓋了前一個(gè)數(shù)字；它不使用E-格，也不隔格打印；它的結(jié)果向左方而不是向右方“延伸”，等等。 圖靈在論文的隨后幾頁為我們構(gòu)造了完成諸如搜索，復(fù)制，擦除，“跑”到帶子最左端，跑到帶子右端最后一個(gè)格子，比較，打標(biāo)記等等更為復(fù)雜動(dòng)作的狀態(tài)。特別的，他引入了“公共任務(wù)”的概念，用可以帶參數(shù)的m-函數(shù)表示。以此簡化圖靈機(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ī)器”?！ ∥覀冊賮砜匆粋€(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，α）?！ D靈接著定義了函數(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ì)算序列。顯然，對一個(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)，比如，對某個(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ì)算序列。反過來，對每個(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.。。）?！ D靈還定義了“完全配置”的概念。在圖靈機(jī)工作的任一階段，被查看的格子的序號(hào)，帶子上的全部符號(hào)，以及當(dāng)前的狀態(tài)，構(gòu)成此階段的圖靈機(jī)的一個(gè)“完全配置”。形象地說，這就是圖靈機(jī)的一個(gè)“快照”?！ ±@了這么大一個(gè)圈子，圖靈到底要干什么？別急。好戲才剛開場?！ D靈下面要做的，是一個(gè)絕對天才的創(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é)果。 對通用圖靈機(jī)構(gòu)造的詳細(xì)描述超出本文的篇幅。粗略地說，其“輸入”是寫有任一欲被模擬的特定圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)式（由D,A,C,L,R,N和；編碼而成）的帶子，“輸出”是被模擬的圖靈機(jī)的一個(gè)個(gè)相續(xù)的完全配置，以及每個(gè)完全配置所對應(yīng)的當(dāng)前打印數(shù)字。這個(gè)相續(xù)的數(shù)字序列正是被模擬圖靈機(jī)的計(jì)算結(jié)果。如此，則通用圖靈機(jī)可以“惟妙惟肖”地模擬任一特定圖靈機(jī)的工作?！ 〉侥壳盀橹挂磺兴坪踹M(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?！ ”M管通用圖靈機(jī)“仿誰象誰”，但它并無“三歲看小，七歲看老”的未卜先知的本事?！ D靈論文的最終目的是證明希爾伯特“判定問題”無解。為此，圖靈將圖靈機(jī)的標(biāo)準(zhǔn)表達(dá)和數(shù)理邏輯的一階謂詞演算聯(lián)系起來?！ ∫浑A謂詞是這樣的一類邏輯表達(dá)式，例如 （ｘ）（ｙ）（Ｇ（ｘ，ｙ）－＞?。牵ǎ?，ｘ）） 式子的意義可以不同，但表示某種交換律，對偶關(guān)系。比如一個(gè)解釋是，（ｘ），（ｙ）表示對所有的人ｘ和ｙ，Ｇ（ａ，ｂ）表示“ａ是ｂ的親戚”。－＞表示“可推出”，“隱含”。在上述解釋下，式子的意思是，如果ｘ是ｙ的親戚，那么ｙ也是ｘ的親戚?！ D靈用若干邏輯式來表達(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)中所有可證公式?，F(xiàn)在人們一般接受，任何直覺上可計(jì)算的數(shù)和函數(shù)，都可以被圖靈機(jī)計(jì)算。而無法用圖靈機(jī)計(jì)算的，本質(zhì)上也是不可計(jì)算的。因此，圖靈機(jī)的計(jì)算能力與直覺上人作為計(jì)算者的能力本質(zhì)上相同。這是對人類智慧及其局限的深刻洞察?！ ≡?936年，我們有了三種關(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ì)?！ ≌缫徊筷P(guān)于可計(jì)算性理論的著名專著中所評(píng)價(jià)的，“圖靈關(guān)于通用圖靈機(jī)存在的定理是上個(gè)世紀(jì)的智力里程碑之一”?！ ⊥ㄓ脠D靈機(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)核心的思想，至少部分歸功于圖靈。馮?諾依曼對從圖靈那里所獲得的啟發(fā)從不諱言。１９３６到１９３８年，圖靈在美國普林斯頓大學(xué)師從丘奇攻讀博士學(xué)位，馮?諾依曼當(dāng)時(shí)正在那里任教，兩人過從甚密。圖靈獲得學(xué)位后，馮?諾依曼曾表示希望雇用圖靈在普林斯頓工作。圖靈謝絕了，回到英國，不久即進(jìn)入皇家密碼學(xué)校，即戰(zhàn)時(shí)的英國密碼破譯中心，開始了幫助英國和盟軍擊敗德國的密碼破譯工作。 現(xiàn)代通用計(jì)算機(jī)（也就是現(xiàn)在遍布于世的大小電腦）的計(jì)算能力本質(zhì)上不超過通用圖靈機(jī)。也就是說，圖靈在現(xiàn)代計(jì)算機(jī)誕生10年以前就不但證明了它可以做什么，而且也證明了它不能做什么！ 圖靈機(jī)的意義早已超越了對證明“判定問題”的應(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é)中心的地位，由于德國瘋狂的反猶浪潮，也已經(jīng)岌岌可危。大批優(yōu)秀的猶太血統(tǒng)數(shù)學(xué)家不得不背井離鄉(xiāng)，遠(yuǎn)走高飛。據(jù)說，一次宴會(huì)上，希爾伯特碰巧坐在德國教育部長身旁，部長關(guān)心地問道，現(xiàn)在哥廷根的數(shù)學(xué)研究情況如何？希爾伯特不無悲傷地說，“數(shù)學(xué)？哥廷根現(xiàn)在哪還有什么數(shù)學(xué)！”。希爾伯特在其生命的最后１２年從未對哥德爾和圖靈的證明公開發(fā)表評(píng)論。他死后，墓碑上刻著“我們必須知道，我們能夠知道！”?！ ≈牢覀兡茏鍪裁垂倘缓芎茫牢覀儾荒茏鍪裁匆埠苤匾?。比如，有了熱力學(xué)第二定律，我們就知道任何形式的“永動(dòng)機(jī)”是不可能的。有人向你兜售永動(dòng)機(jī)，你就知道他必然是騙子。有了“判定過程”的不存在性，我們也就不會(huì)再費(fèi)神勞力企圖發(fā)明一種萬能驗(yàn)證程序，可以查出任意程序的“蟲子”，或者判定任意程序的最終結(jié)果。等等?！ D靈發(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é)構(gòu)”（RISC）思想。這是圖靈思想遠(yuǎn)超時(shí)代的另一證明?！ D靈一生都在思考人的心智如何“運(yùn)算”，能否用機(jī)器模擬的問題。１９５０年，他在另一篇影響深遠(yuǎn)的論文《計(jì)算機(jī)器與智能》中提出了“機(jī)器能否思考”的問題，并給出了機(jī)器智能的判定標(biāo)準(zhǔn)，即后來被稱為“圖靈測試”。他提出，如果一個(gè)測試人對處于黑室中的一臺(tái)機(jī)器和一個(gè)人提出問題，經(jīng)過一段充分時(shí)間“較量”，他不能從答案中分出哪個(gè)是人，哪個(gè)是機(jī)器，就可以認(rèn)為機(jī)器擁有了智能。這篇文章被認(rèn)為是人工智能的開山之作。 圖靈曾樂觀地預(yù)言，到２０世紀(jì)末，機(jī)器智能將能夠達(dá)到以７０％的成功率通過圖靈測試?；蛘哂捎趫D靈英年早逝，后繼乏人，或者由于我們對智能的本質(zhì)還遠(yuǎn)未了解，我們現(xiàn)在離這個(gè)標(biāo)準(zhǔn)還差的太遠(yuǎn)?，F(xiàn)在世界上每年都舉行機(jī)器智能大賽，但參賽者都心知肚明，不敢妄稱試圖通過圖靈測試，而只是期望擊敗自己的機(jī)器人對手。近兩年的大賽獲勝者是一個(gè)叫做Ａｌｉｃｅ的機(jī)器，“她”現(xiàn)在有一個(gè)網(wǎng)站 http://alicebot.blogspot.com/ 誰愿意都可以和她聊天。偶爾她也會(huì)說出很“聰明”的話。不過很容易判斷，她的“智能”十分有限?！ D靈為我們留下了永久的遺產(chǎn)。他的智慧結(jié)晶，圖靈機(jī)，現(xiàn)在仍然是人們探索人類自身能力和局限的有力工具。圖靈孤獨(dú)而默默地離開了我們，留下了許多奧秘和疑團(tuán)。就像人類面臨的其他許多奧秘一樣，我們有可能最終找到其中一些的答案。還有很多，我們甚至將永遠(yuǎn)無法知道，它們是不是有答案。
聯(lián)系客服
