孤獨的破譯者和他的計算機器（修訂稿） 作者：若奇 他出生于倫敦，在遠離父母的環(huán)境中孤獨地長大。從小學到中學，他由于性 格離群和糟糕的文科成績而飽受詬病。但他卻從學習數(shù)學，閱讀相對論和量子力 學中獲得莫大樂趣。從中學開始他可能不自覺地發(fā)展了同性戀的性取向。他的第 一個精神“戀人”，一位才華橫溢、與他對自然科學有著同樣熱愛的高年級同學 的突然去世，對他打擊甚深，既讓他永遠喪失了對宗教的信仰，也激發(fā)了他揭開 人類智能活動秘密的最初愿望。 在劍橋大學國王學院，他受到哥廷根數(shù)理邏輯學派的熏陶。大學畢業(yè)后的第 二年，24歲的他就以3６頁的一篇傳世之作奠定了他在計算機科學史上的地位。 二次大戰(zhàn)中他領(lǐng)導英國情報機構(gòu)“第八室”，為破解德國海軍“恩尼格瑪”密碼 系統(tǒng)立下汗馬功勞，對盟軍在大西洋海戰(zhàn)中取得壓倒性優(yōu)勢貢獻巨大。二戰(zhàn)后他 在英國國家物理研究所設(shè)計的ACE計算機被認為是第一臺真正意義上的現(xiàn)代計算 機。1950年他的另一篇開創(chuàng)性論文奠定了計算機人工智能的基礎(chǔ)。他作為世界上 第一個計算機“個人”用戶和第一個專職程序員，使用曼徹斯特大學“Mark-I” 計算機，單槍匹馬地創(chuàng)立了另一門學科“形態(tài)發(fā)生學”。他興趣廣泛，多才多藝， 在數(shù)學，量子力學，地學，化學和生物學等方面都卓有建樹。 他性格孤獨，行為乖僻，有些害羞。因為他公開的同性戀取向，50年代初冷 戰(zhàn)開始后他失去了從事國家機密活動的資格。1952年，40歲的他被依據(jù)當時英國 法律指控非法進行同性戀活動，他高傲而不肯為自己抗辯，但為了避免坐牢從而 得以繼續(xù)他的研究，他不得不接受令他蒙羞的“激素治療”。他身心俱焚，形吊 影單，1954年6月的一天，他被發(fā)現(xiàn)死于寓所的床上，身邊有一只被咬去幾口的 蘋果。檢驗證明這只蘋果被劇毒氰化物浸泡過。他的死充滿疑云，但被警方判定 為自殺。也許，他以無聲的抗議走完了他短暫，輝煌而悲劇的一生。他沒有留下 一句遺言。 2009年9月10日，英國政府正式為他洗去沉冤。布朗首相代表英國政府向他 因同性戀遭受的不公道歉。他說，“我代表英國政府、以及所有因他的工作而自 由生活的人們向他說：‘我們很抱歉，你本應(yīng)得到更多的獎賞。’” 這個人，就是天才的英國數(shù)學家阿蘭?圖靈（Alan Turing，1912-1954）。 二十世紀是人類歷史上科學技術(shù)發(fā)展最快的世紀。100年間，涌現(xiàn)了大量對 世界產(chǎn)生重大的影響的科學和技術(shù)發(fā)現(xiàn)，包括量子力學，相對論，抗生素，基因 科學，飛機，電視等等。但是，在上個世紀結(jié)束的時候，如果要評選一項已經(jīng)滲 透至人們?nèi)粘Ｉ畹乃薪锹洌瑢θ祟惖墓ぷ骱蜕钣绊懽畲蟮谋臼兰o科技發(fā)展 的話，則非計算機莫屬。 如同提到經(jīng)典力學人們必然聯(lián)想起牛頓，提到相對論人們必然聯(lián)想起愛因斯 坦，每項里程碑式的人類文明發(fā)展都有其領(lǐng)軍巨匠大師。計算機的發(fā)展也不例外。 阿蘭?圖靈的名字永遠與計算機科學聯(lián)系在一起。作為人類創(chuàng)造性心智和抽象思 維的典范，“圖靈機”亦將永垂科學青史。“圖靈測試”仍是迄今為止公認的判 定計算機是否具有智能的標準。 為了理解圖靈的主要貢獻，讓我們簡單回顧一下19世紀20世紀之交數(shù)學界的 狀況。 盡管數(shù)學在當時已經(jīng)有了長足的發(fā)展，人們?nèi)匀粚τ嘘P(guān)實數(shù)的一些基本性質(zhì) 感到困惑。在解決實數(shù)是否可數(shù)的過程中，集合論創(chuàng)始人康托（Georg Cantor, 1845-1918）發(fā)展了包含無限元素的集合的理論?？低邪l(fā)現(xiàn)，無限集合的真子集 可以和原集合一樣“大”，有可數(shù)的無限和不可數(shù)的無限等等，這些概念都不是 直觀的。據(jù)說，康托因為思考這些無限的大小和可數(shù)性而走火入魔，后半生生活 在半瘋的狀態(tài)中，出入精神病院，在數(shù)學，音樂，哲學和神學之間游走。 人們意識到，為了更準確地理解世界，必須借助嚴格和可靠的工具。以歐幾 里德幾何原理為代表的公理化方法漸入佳境。 數(shù)學家們開始以前所未有的熱情和異乎尋常的嚴格來重新構(gòu)造數(shù)學的基礎(chǔ)。 皮亞諾(Giuseppe Peano, 1858-1932)建立了以公理系統(tǒng)為基礎(chǔ)的自然數(shù)的運算 系統(tǒng)。弗雷澤(Gottlob Frege, 1848-1925)則更進一步，在集合論和數(shù)理邏輯的 基礎(chǔ)上建立了實數(shù)的運算系統(tǒng)。著名數(shù)學家，近代數(shù)學的代表人物，哥廷根學派 的掌門人希爾伯特(David Hilbert, 1862-1943)在實數(shù)系統(tǒng)的基礎(chǔ)上將歐氏幾何 全部重新推導，將其牢固地建立在前所未有的嚴格的數(shù)學根基上。 到了１９世紀行將結(jié)束的時候，數(shù)學大廈似乎已經(jīng)構(gòu)建得十分宏偉堅固。以 希爾伯特為代表的數(shù)學家們對解決殘存的數(shù)學問題相當樂觀。１９００年８月， 在巴黎召開的第二屆世界數(shù)學家大會上，希爾伯特應(yīng)邀致辭，他豪情滿懷，信心 爆棚地宣稱： 無論這些難題看起來多么難以解決，無論我們現(xiàn)在在它們面前如何困惑無助， 我們?nèi)詧猿诌@樣一個信念：這些難題的解決一定會遵循有限的純粹邏輯的過 程。。。每個數(shù)學問題都必然可解的這一信條是對數(shù)學家們的強有力激勵。我們 聽到來自內(nèi)心的永恒召喚：我們面臨難題。我們要去尋找它的解。通過純粹推理， 我們一定能找到它。因為在數(shù)學中，絕對沒有“我們不可能知道”！ 接著，他列舉了他所認為新世紀應(yīng)該解決的２３個數(shù)學難題（其中許多至今 仍未解決），并挑戰(zhàn)他的數(shù)學同行在新世紀中解決它們。 不僅在數(shù)學界，而且在諸如物理，藝術(shù)，乃至社會方方面面，人們普遍抱有 樂觀情緒，認為新的世紀會帶來各種遺留問題的徹底解決。人類即將達到燦爛的 頂峰。 ?。玻笆兰o帶來的，卻幾乎是徹底的相反。 藝術(shù)上的反叛首先引人注目。抽象派的立體、殘缺不全的幾何圖形顛覆了人 們對古典美的欣賞。音樂界從斯塔文斯基開始，喧鬧而不和諧的“雜亂無章”， 使得晚期浪漫主義風格的瓦格納和德彪西顯得過于柔順。物理學上的沖擊來自１ ９０５年，愛因斯坦的幾篇劃時代論文徹底顛覆了牛頓經(jīng)典力學對時空的認識。 １９１４年的一次世界大戰(zhàn)粉碎了人類和平的夢想，同時催生了數(shù)十年的以失敗 而告終的人類大規(guī)模社會主義試驗。 在數(shù)學界，“破壞”也是料想不到的“天翻地覆”。 世紀初的進展似乎勢如破竹。雄心勃勃的數(shù)學家羅素（Bertrand Russell, 1872-1970,就是那個從英國維多利亞女王時代開始發(fā)表數(shù)學論文，最終活到抗議 越戰(zhàn)的諾貝爾文學獎獲得者，大名鼎鼎的“哲學家”羅素），和他的導師懷特黑 (Alfred Whitehead, 1861-1947)，在１９１２－１９１３年分三卷出版了長達 兩千多頁的《數(shù)學原理》。羅素用了和牛頓的等身名著類似的書名，正是表現(xiàn)了 他的自信。幾年前，他在思考集合論問題時提出了后來以他名字命名的“羅素悖 論”：一個只包含所有不含自身的集合的集合，包含不包含它自己？簡單的比方 就是那個著名的“理發(fā)師悖論”：一個只給所有不給自己修面的人修面的理發(fā)師， 給不給自己修面？他寫信給奠定了集合論基礎(chǔ)的弗雷澤求教，立刻使得弗雷澤 “精神崩潰”，無法回避他畢生的工作存在這樣無法自圓其說的“漏洞”。羅素 自己擔起了為數(shù)學撥亂反正的重任。他試圖將集合分成不同的類型，每個類型只 能包含特定的類型，從而避免類似理發(fā)師悖論那樣由于自我引用導致的悖論。他 和懷特黑用了幾十頁的篇幅，最終成功地證明１＋１＝２（不是哥德巴赫猜想， 而是初等算術(shù)）！ 順便提及，1957年，紐維爾(Allen Newell, 1927-1992)等人使用計算機證 明了《數(shù)學原理》中的許多定理。他們寫信將結(jié)果報知羅素。羅素不無調(diào)侃地回 信說，“得知《數(shù)學原理》現(xiàn)在可以被機器寫出，我十分驚喜?？上液蛻烟睾? 在浪費十年心血寫出此書之前不知道這一可能”。 希爾伯特進一步明確了公理系統(tǒng)的四大要素： 獨立性：公理是最簡約的，無冗余的。 一致性：從公理出發(fā)，按照推理規(guī)則，不會推出相互矛盾的命題。 完備性：從公理出發(fā)可以推出所有的真命題。 可判定性：存在一個有限步驟的一般過程，可以判定任意一個命題的可證明 性。 希爾伯特和他的學生艾克曼(Wilhelm Ackermann, 1896-1962)在《數(shù)理邏輯 原理》一書中建立了后來被稱之為“一階謂詞演算”的邏輯系統(tǒng)，其中特別包括 了完備性和可判定性的的討論。 奧地利人哥德爾(Kurt G?del, 1906-1978)的出現(xiàn)，先是給了希爾伯特們一 個志在必得的微笑，而后給了他們狠狠一擊。 哥德爾在１９２９年首先證明，希爾伯特的一階謂詞邏輯系統(tǒng)確實是完備的， 能夠?qū)С鏊姓婷}。可以想象希爾伯特們會稍帶不屑地說，“不早告訴你了”。 １９３０年，重磅炸彈橫空出世。哥德爾進一步證明，如果將算術(shù)運算公理引入 一階謂詞系統(tǒng)，則由此而成的算術(shù)運算系統(tǒng)是不完備的，即存在這樣的命題，它 們的真?zhèn)问遣豢勺C明的。這個結(jié)論的一個前提是，算術(shù)運算系統(tǒng)是一致的。由此 自然得到，一致性的證明不可能從系統(tǒng)內(nèi)部完成，即算術(shù)運算系統(tǒng)的一致性不能 由其自身證明！ 顛覆是徹底而毀滅性的。希爾伯特和羅素賴以建立數(shù)學大廈的根基居然自己 就是建立在沙灘上。據(jù)說，希爾伯特聽到這個結(jié)論后“相當憤怒”。羅素則徹底 喪失了對數(shù)理邏輯的興趣，不知是寫作《數(shù)學原理》耗盡了他的心血，還是哥德 爾定理擊碎了他的信心。用他自己的話說，“從此我發(fā)現(xiàn)我對抽象問題的處理能 力肯定是大大降低了”。他改而傾心哲學和文學，關(guān)注社會事務(wù)。當他在１９５ ０年獲得諾貝爾文學獎時，人們早已忘記他曾經(jīng)是個數(shù)學家。另一個當時業(yè)已蜚 聲數(shù)學界，以公理系統(tǒng)將量子力學形式化的哥廷根大學邏輯學家馮?諾依曼(John von Neumann, 1903-1957)，從此放棄了純粹數(shù)學的研究，而１０多年后卻因?qū)? 現(xiàn)代計算機的奠基和發(fā)展的貢獻而青史留名。 然而，希爾伯特應(yīng)該還存有希望。哥德爾的結(jié)果并未解決“可判定性”問題。 哥德爾只是證明了，邏輯系統(tǒng)中存在不可能判定真?zhèn)蔚拿}。然而，一個系統(tǒng)是 不完備的，并不等于不存在一般的判定過程，使得可以判定其中任意一個命題是 否可證。在哥德爾不完備定理出世以后，如果還能證明存在這樣的一般過程，退 而求次，看起來還是可說很圓滿了。 最后的“致命”一擊，來自美國數(shù)學家丘奇(Alonzo Church, 1905-1995)和 英國數(shù)學家圖靈。１９３６年，兩人幾乎同時，卻是獨立地循著完全不同的途徑， 證明了“判定問題”的不可解性。即不存在一般的過程，可以判定任意一個命題 在一階謂詞邏輯系統(tǒng)是否可證。丘奇的方法是“蘭姆達演算”，它現(xiàn)在只存在于 數(shù)理邏輯及其相關(guān)的若干狹窄研究領(lǐng)域中，雖然其對現(xiàn)代計算即程序語言如ALGOL, LISP和APL等等的發(fā)展也曾有重要影響。圖靈的工具，則是大名鼎鼎的“圖靈 機”。圖靈機對后世產(chǎn)生了深遠的影響，特別是對２０世紀以來的計算機發(fā)展起 到并且繼續(xù)發(fā)揮著革命性作用。 簡單地說，圖靈在其劃時代論文《論可計算數(shù)及其對判定問題的應(yīng)用》中作 出了以下開創(chuàng)性貢獻： 一． 定義了一種抽象的計算機器 二． 證明了能夠模擬任意計算機器的通用計算機器的存在性 三． 證明了存在任何計算機器都不能解決的問題 那么，圖靈機到底是怎樣一個神通廣大的機器？讓我們跟隨圖靈的論文，進 入圖靈機的王國。 對于圖靈而言，他的計算機器是一種思維模型，是只存在于紙上或頭腦里， 模擬人們演算活動而簡化到了最基本操作的抽象思維工具。這種抽象完全擯棄現(xiàn) 實世界時間和空間的限制，從而得以揭示事物的本質(zhì)。 圖靈試圖將人的計算過程還原為最基本的若干機械操作。人在演算數(shù)學問題 時，面前有張寫著算式的紙，腦子里記著演算規(guī)則。演算過程的任一時刻，人只 關(guān)注于算式的某一部分和某一特定規(guī)則，并據(jù)此寫下新的數(shù)字，或擦除已有數(shù)字， 然后將關(guān)注轉(zhuǎn)向算式的另一部分和另一規(guī)則，直到演算完畢。圖靈論證說，這些 規(guī)則一定是有限的，否則就會由于狀態(tài)無限接近而不可區(qū)分。 這是天才的抽象。圖靈正是據(jù)此來構(gòu)造他的計算機器。 圖靈機由有限的狀態(tài)（圖靈原文中稱為“m-配置”）組成。可把狀態(tài)看作是 計算規(guī)則的模擬。機器被送進一條分成連續(xù)“格子”的“帶子”，這些格子上可 以寫有數(shù)字或符號。顯然，帶子是模擬寫著式子的紙。任何時刻機器只能“看到” 當前一個格子。每個狀態(tài)“告訴”機器，根據(jù)當前看到的符號，采取何種操作， 以及下一個狀態(tài)是什么。圖靈機的操作非常“原始”，只包括左移一格，右移一 格，擦去當前格子的符號，或者在當前格子寫下新的符號。狀態(tài)和當前符號構(gòu)成 圖靈機的一個“配置”。“配置”完全決定了圖靈機的行為。計算機器“寫出” 的０和１的序列就是機器計算出來的結(jié)果。 就是這些。沒有復(fù)雜的“指令”，沒有五花八門的輸入輸出，沒有多少ＧＢ 的存儲器，沒有強大的“ＣＰＵ”或控制器。甚至連后來出現(xiàn)在許多介紹圖靈機 的文章中的“讀寫頭”，在圖靈原文中也是隱含的。在用慣了現(xiàn)代計算機的人們 看來，圖靈機可以說是“土得掉渣”。 那么，這樣“簡陋”的機器到底如何工作呢？ 圖靈在論文中給出了兩個具體計算機器的例子，一個計算二進制０.０１０ １０１。。。（十進制的１／３），另一個計算超越數(shù)０.０１０１１０１１１ ０１１１１.。。。我們來看計算1/3的例子。我們只需一條空白帶子和四個狀態(tài) 來構(gòu)造這個圖靈機： 配置 行為 狀態(tài) 當前符號 操作 下個狀態(tài) ―――――――――――――――――――――――― ｂ 空白 寫0，右移 ｃ ―――――――――――――――――――――――― ｃ 空白 右移 e ―――――――――――――――――――――――― e 空白 寫1，右移 f ———————————————————————— f 空白 右移 b 初始狀態(tài)ｂ下，機器在當前格子上寫1，然后右移一格，“轉(zhuǎn)到”狀態(tài)ｃ。 ｃ看到當前格子是空白，于是右移，然后轉(zhuǎn)到狀態(tài)e。e看到的仍是空白，于是寫 1，右移，并轉(zhuǎn)回狀態(tài)b。如此永遠“循環(huán)”下去，永不停歇。機器“寫”出的結(jié) 果是010101.．．。按圖靈的約定，結(jié)果應(yīng)按前面加上小數(shù)點理解，于是我們得 到 0.010101．．．，也就是十進制的１／3。注意，根據(jù)圖靈的定義，只有永遠 不停“寫出”0或1序列的機器才是正常的，“好”的機器。 細心的讀者也許會發(fā)現(xiàn)，這個圖靈機實際上是隔一格打印一個數(shù)字。這正是 圖靈的匠心所在。圖靈將帶子上的格子分為F-格（數(shù)字格）和E-格（可擦除符號 格）兩類，一個F-格跟著一個E-格。計算結(jié)果由F-格表示，E-格則用于“打標 記”，寫特殊符號，起到“臨時存儲”的作用。對上面這個簡單圖靈機而言，還 用不到E-格。 圖靈機的操作是如此原始，以至于連進行簡單加減運算都需要許多繁復(fù)步驟 才能完成。如果要計算更復(fù)雜的問題，豈非要算到“地老天荒“？但圖靈對這些 具體運算根本毫無興趣。他所關(guān)心的不是要花多少時間，需要多長的帶子才能完 成某個計算，而是可不可能完成它。 圖靈定義抽象計算機器的方法亦有很大彈性，改變一些細節(jié)并不影響可計算 的范圍。下面的例子是一個對原始圖靈機定義略加改造的圖靈機，它的“輸入” 是一條所有格子都是空白的帶子，它的功能是依次打出所有正整數(shù)（也就是完成 加1操作）： 配置 行為 狀態(tài) 當前符號 操作 下個狀態(tài) ―――――――――――――――――――――――― b 空白 P0 i i 0 P1 r 1 P0,L i 空白 P1 r r 空白 L i 其他符號 R r 其中操作Pn（Print）意為在當前格子打印n，P0即打印0。L（Left）和 R(Right)分別意為左移或右移一格。狀態(tài)b可視為起始操作，打印數(shù)字0，然后轉(zhuǎn) 到狀態(tài)i（increment，加1）。根據(jù)當前符號，i可以有三種動作。如果當前符號 是0，則將其改為1，這同時也就完成了加1操作。如果當前符號是1，則將其改為 0，然后左移一格（進位），重復(fù)i操作。如果當前符號是空白，說明進位到了新 的最高位，于是打印1。然后轉(zhuǎn)到狀態(tài)r（rewind，回到最后一位有效數(shù)字）。這 個圖靈機依次打印0，1，10（十進制2），11（十進制3），100（十進制4） 等 等。讀者可以看到，這個“加法器”對原始圖靈機有多處修改，例如，它每次新 打印的數(shù)字都覆蓋了前一個數(shù)字；它不使用E-格，也不隔格打印；它的結(jié)果向左 方而不是向右方“延伸”，等等。 圖靈在論文的隨后幾頁為我們構(gòu)造了完成諸如搜索，復(fù)制，擦除，“跑”到 帶子最左端，跑到帶子右端最后一個格子，比較，打標記等等更為復(fù)雜動作的狀 態(tài)。特別的，他引入了“公共任務(wù)”的概念，用可以帶參數(shù)的m-函數(shù)表示。以此 簡化圖靈機的說明。他很快就在論文中把這些函數(shù)稱為“指令”。我們也可以看 出這些函數(shù)和現(xiàn)代計算機程序語言中的子程序，函數(shù)，循環(huán)，遞歸調(diào)用等構(gòu)造的 類似。 事實上，圖靈在真正的自動計算機出現(xiàn)前１０多年就開始“編程”了。圖靈 將使用這些函數(shù)構(gòu)造他的“通用計算機器”。 我們再來看一個圖靈論文中稍為復(fù)雜的m-函數(shù)的例子。“擦除從起始符號起 的第一個α”的函數(shù)e是這樣定義的： e(C,B,α) f(e1(C,B,α),B,α) e1(C,B,α) E C 這里的E表示“擦除當前符號α”。m-函數(shù)e擦除第一個α，然后轉(zhuǎn)到C。如 果不存在α，則轉(zhuǎn)到B。函數(shù)e的定義“引用”了一個已經(jīng)定義過的“搜索函數(shù)” f，f完成搜索從起始符號э開始的第一個α的功能。如果找到這樣的α，機器轉(zhuǎn) 到狀態(tài)C，否則轉(zhuǎn)到狀態(tài)B。在函數(shù)e的定義中，C實際上e1（C, B，α）。 圖靈接著定義了函數(shù)e的另一個版本： e(B, α) e(e(B, α),B, α) 這個只有兩個參數(shù)的e“神通廣大”。它首先“調(diào)用”三參數(shù)的e擦除帶子最 左邊的第一個α,然后轉(zhuǎn)到三參數(shù)的e的第一個參數(shù)表示的狀態(tài)，而這個狀態(tài)正好 又是兩參數(shù)的e。于是又去“調(diào)用”三參數(shù)的e，擦除當前的第一個α（也就是原 來的第二個α），等等，直到所有的α都被擦除，機器轉(zhuǎn)到狀態(tài)B。了解計算機 編程的讀者已經(jīng)看出，這里包含了計算機程序設(shè)計中的遞歸調(diào)用，以及許多老一 代程序語言都不支持的函數(shù)“overloading”。圖靈的思想確實大大超前于時代。 圖靈機也可以視為“算法（algorithm）”的體現(xiàn)。算法以有限的符號，有 限的步驟，精確地描述一類計算過程。實際上，圖靈機后來被廣泛地用于算法研 究。 圖靈機的計算結(jié)果是一個可計算序列。顯然，對一個可計算序列，可以構(gòu)造 不同的圖靈機，它們的計算結(jié)果相同。為了用一種標準方式表達圖靈機的結(jié)構(gòu)， 他將圖靈機的配置“規(guī)范化”一個五元組 ?。ó斍盃顟B(tài)，當前符號，要寫的新符號，移動方向，下一狀態(tài)） 如果將所有m-函數(shù)展開，任何圖靈機都可由這樣一組有限的五元組表示。為 了規(guī)范化，圖靈規(guī)定，擦除操作相當于打印空白符號，保持當前符號不變相當于 打印當前符號。然后將所有的配置，符號和動作都分別排上序號，比如，對某個 特定的有20個狀態(tài)，使用15個符號的圖靈機，狀態(tài)用帶下標的q表示，即ｑ從q１ 到q２０，符號用帶下標的Ｓ表示，即從S１到S１５（其中S0是空白，Ｓ１是數(shù) 字０，Ｓ２是數(shù)字１）。再以字母A代替q的下標：狀態(tài)ｑ１表示為ＤＡ，ｑ２表 示為ＤＡＡ，qi表示為D后跟隨i個A; 用字母C替代符號S的下標：Ｓ１表示為Ｄ Ｃ，Ｓ２表示為ＤＣＣ， Sj表示為D后跟隨j個C等等。動作用L或R表示右移和或 左移，用N表示不移動。這樣，計算１／３的圖靈機可以寫成下列標準表達式 （S.D, Standard Description，其中分號分開各個五元組）： ＤＡＤＤＣＲＤＡＡ；ＤＡＡＤＤＲＤＡＡＡ；ＤＡＡＡＤＤＣＣＤＡＡＡＡ；ＤＡＡＡＡＤＤＲＤＡ； 圖靈實際上是用有限的符號為他的計算機器編碼。進一步，如果用數(shù)字表示 每個不同字母，比如１表示Ａ，２表示Ｃ，３表示Ｄ，４表示Ｌ，５表示Ｒ，6 表示N,７表示分號；則數(shù)字 ３１３３２５３１１７３１１３３５３１１１７３１１１３３２２５３１１１１７３１１１１３３５３１７ 就是該圖靈機的標準表達數(shù)（D.N）。D.N（亦即S.D）唯一地確定一個圖靈 機的結(jié)構(gòu)，也就是唯一一個可計算序列。反過來，對每個可計算序列，至少存在 一個標準表達數(shù)。不難想象，絕大部分任意正整數(shù)都不是一個合格的圖靈機的標 準表達數(shù)。事實上，最小的可作為圖靈機標準表達數(shù)的正整數(shù)是３１３３４３１ ７（只打印空格！因此，這個圖靈機按圖靈的定義是一個不好的機器）。最小的 完全符合圖靈定義的“好”圖靈機標準表達數(shù)是313325317（計算0.1111.。。）。 圖靈還定義了“完全配置”的概念。在圖靈機工作的任一階段，被查看的格 子的序號，帶子上的全部符號，以及當前的狀態(tài)，構(gòu)成此階段的圖靈機的一個 “完全配置”。形象地說，這就是圖靈機的一個“快照”。 繞了這么大一個圈子，圖靈到底要干什么？別急。好戲才剛開場。 圖靈下面要做的，是一個絕對天才的創(chuàng)造：他要構(gòu)造一個“通用計算機器”， 只要給這臺機器提供寫有某個圖靈機的標準表達的帶子，就可以模擬這個圖靈機 的計算，得出相同的可計算序列。圖靈論文的第６和第７節(jié)詳細給出了通用圖靈 機的構(gòu)造和所有狀態(tài)，用到了我們上面提到的那些m-函數(shù)。圖靈證明，如此構(gòu)造 的這個通用圖靈機的計算結(jié)果正好就是提供給它的標準表達所代表的那個圖靈機 的結(jié)果。 對通用圖靈機構(gòu)造的詳細描述超出本文的篇幅。粗略地說，其“輸入”是寫 有任一欲被模擬的特定圖靈機的標準表達式（由D,A,C,L,R,N和；編碼而成）的 帶子，“輸出”是被模擬的圖靈機的一個個相續(xù)的完全配置，以及每個完全配置 所對應(yīng)的當前打印數(shù)字。這個相續(xù)的數(shù)字序列正是被模擬圖靈機的計算結(jié)果。如 此，則通用圖靈機可以“惟妙惟肖”地模擬任一特定圖靈機的工作。 到目前為止一切似乎進展順利。我們已經(jīng)有了神通廣大可以模擬任何圖靈機 的通用圖靈機。圖靈還將給我們帶來何種驚喜？ 不幸的是，圖靈很快就給我們的熱切期待澆上一盆涼水：圖靈機并非萬能。 利用通用圖靈機，他巧妙地證明了，不可能構(gòu)造這樣一個圖靈機，當給它提供任 意一個圖靈機的標準表達后，能判定該機器是否是“好”的（即是否能夠無休止 地打印數(shù)字），甚至不能判定任意一個圖靈機是否最終會打印一個0。 盡管通用圖靈機“仿誰象誰”，但它并無“三歲看小，七歲看老”的未卜先 知的本事。 圖靈論文的最終目的是證明希爾伯特“判定問題”無解。為此，圖靈將圖靈 機的標準表達和數(shù)理邏輯的一階謂詞演算聯(lián)系起來。 一階謂詞是這樣的一類邏輯表達式，例如 （ｘ）（ｙ）（Ｇ（ｘ，ｙ）－＞?。牵ǎ?，ｘ）） 式子的意義可以不同，但表示某種交換律，對偶關(guān)系。比如一個解釋是， （ｘ），（ｙ）表示對所有的人ｘ和ｙ，Ｇ（ａ，ｂ）表示“ａ是ｂ的親戚”。 －＞表示“可推出”，“隱含”。在上述解釋下，式子的意思是，如果ｘ是ｙ的 親戚，那么ｙ也是ｘ的親戚。 圖靈用若干邏輯式來表達圖靈機配置的五元組，這樣，一個圖靈機就可以用 邏輯式的“邏輯積”來表達。然后，通過將希爾伯特的“判定問題”表達為一個 更為復(fù)雜的邏輯公式，成功地將問題轉(zhuǎn)化為“如果判定問題有解（即存在一般判 定過程），則存在一個圖靈機，它能判定被它模擬的圖靈機最終是否打?。?#8221;。 我們已經(jīng)知道，這樣的圖靈機不存在，因此，一般的“判定過程”不存在。 至此，圖靈圓滿地解決了希爾伯特的判定問題。 以圖靈機作為工具，圖靈繼而證明了一大類數(shù)字(包括π和е)和函數(shù)是可被 圖靈機計算的。不僅如此，圖靈機還能證明希爾伯特一階謂詞系統(tǒng)中所有可證公 式?，F(xiàn)在人們一般接受，任何直覺上可計算的數(shù)和函數(shù)，都可以被圖靈機計算。 而無法用圖靈機計算的，本質(zhì)上也是不可計算的。因此，圖靈機的計算能力與直 覺上人作為計算者的能力本質(zhì)上相同。這是對人類智慧及其局限的深刻洞察。 在1936年，我們有了三種關(guān)于可計算性的定義：圖靈的通用圖靈機，哥德爾 的遞歸函數(shù)，和丘奇的蘭姆達函數(shù)。圖靈證明了圖靈機與蘭姆達函數(shù)的等價。后 來，丘奇的學生科雷尼(Stephen Kleene, 1909-1994)證明了遞歸函數(shù)與蘭姆達 函數(shù)的等價。于是這三個表面上似乎不相關(guān)的定義被統(tǒng)一起來，揭示了可計算性 的本質(zhì)。 正如一部關(guān)于可計算性理論的著名專著中所評價的，“圖靈關(guān)于通用圖靈機 存在的定理是上個世紀的智力里程碑之一”。 通用圖靈機可以說是現(xiàn)代“存儲程序通用計算機”的雛形。圖靈的思維是革 命性的。他的構(gòu)造中已經(jīng)有了“軟件”的思想：標準表達就是一個計算程序。程 序和數(shù)據(jù)被同樣“輸入”和“存儲”，計算機是通用的，其工作由程序控制。這 些幾乎１０年后才由被后人稱為“計算機之父”的馮?諾依曼總結(jié)提煉而成為現(xiàn) 代計算機體系結(jié)構(gòu)核心的思想，至少部分歸功于圖靈。馮?諾依曼對從圖靈那里 所獲得的啟發(fā)從不諱言。１９３６到１９３８年，圖靈在美國普林斯頓大學師從 丘奇攻讀博士學位，馮?諾依曼當時正在那里任教，兩人過從甚密。圖靈獲得學 位后，馮?諾依曼曾表示希望雇用圖靈在普林斯頓工作。圖靈謝絕了，回到英國， 不久即進入皇家密碼學校，即戰(zhàn)時的英國密碼破譯中心，開始了幫助英國和盟軍 擊敗德國的密碼破譯工作。 現(xiàn)代通用計算機（也就是現(xiàn)在遍布于世的大小電腦）的計算能力本質(zhì)上不超 過通用圖靈機。也就是說，圖靈在現(xiàn)代計算機誕生10年以前就不但證明了它可以 做什么，而且也證明了它不能做什么！ 圖靈機的意義早已超越了對證明“判定問題”的應(yīng)用。由于圖靈機深刻體現(xiàn) 了人類機械思維的本質(zhì)，它成為一個通用工具。許多數(shù)學家和數(shù)理邏輯學家使用 它（通常是改造后的變體）來證明一些復(fù)雜的數(shù)學定理。圖靈機至今仍是研究算 法復(fù)雜性和可計算性的重要手段，亦是研究形式語言與自動機的基本工具。圖靈 機也被用于研究人腦，神經(jīng)網(wǎng)絡(luò)和思維的機制。甚至有人以圖靈機作為研究宇宙 的模型。 當圖靈和丘奇的否定性結(jié)果發(fā)表時，希爾伯特剛剛退休。他的哥廷根大學數(shù) 學系作為世界數(shù)學中心的地位，由于德國瘋狂的反猶浪潮，也已經(jīng)岌岌可危。大 批優(yōu)秀的猶太血統(tǒng)數(shù)學家不得不背井離鄉(xiāng)，遠走高飛。據(jù)說，一次宴會上，希爾 伯特碰巧坐在德國教育部長身旁，部長關(guān)心地問道，現(xiàn)在哥廷根的數(shù)學研究情況 如何？希爾伯特不無悲傷地說，“數(shù)學？哥廷根現(xiàn)在哪還有什么數(shù)學！”。希爾 伯特在其生命的最后１２年從未對哥德爾和圖靈的證明公開發(fā)表評論。他死后， 墓碑上刻著“我們必須知道，我們能夠知道！”。 知道我們能做什么固然很好，知道我們不能做什么也很重要。比如，有了熱 力學第二定律，我們就知道任何形式的“永動機”是不可能的。有人向你兜售永 動機，你就知道他必然是騙子。有了“判定過程”的不存在性，我們也就不會再 費神勞力企圖發(fā)明一種萬能驗證程序，可以查出任意程序的“蟲子”，或者判定 任意程序的最終結(jié)果。等等。 圖靈發(fā)明了抽象的圖靈機，制造過破譯密碼的電動解碼機，也設(shè)計過當時體 系結(jié)構(gòu)領(lǐng)先的真正的可編程序帶存儲器的電子計算機ACE。他的設(shè)計思想和編程 理念被應(yīng)用到了曼徹斯特大學“馬克Ｉ”計算機上，并深刻影響了后世。他的 “機器指令集”類似于３０年后才開始流行的“簡約指令體系結(jié)構(gòu)”（RISC）思 想。這是圖靈思想遠超時代的另一證明。 圖靈一生都在思考人的心智如何“運算”，能否用機器模擬的問題。１９５ ０年，他在另一篇影響深遠的論文《計算機器與智能》中提出了“機器能否思考” 的問題，并給出了機器智能的判定標準，即后來被稱為“圖靈測試”。他提出， 如果一個測試人對處于黑室中的一臺機器和一個人提出問題，經(jīng)過一段充分時間 “較量”，他不能從答案中分出哪個是人，哪個是機器，就可以認為機器擁有了 智能。這篇文章被認為是人工智能的開山之作。 圖靈曾樂觀地預(yù)言，到２０世紀末，機器智能將能夠達到以７０％的成功率 通過圖靈測試?；蛘哂捎趫D靈英年早逝，后繼乏人，或者由于我們對智能的本質(zhì) 還遠未了解，我們現(xiàn)在離這個標準還差的太遠?，F(xiàn)在世界上每年都舉行機器智能 大賽，但參賽者都心知肚明，不敢妄稱試圖通過圖靈測試，而只是期望擊敗自己 的機器人對手。近兩年的大賽獲勝者是一個叫做Ａｌｉｃｅ的機器，“她”現(xiàn)在 有一個網(wǎng)站 http://alicebot./ 誰愿意都可以和她聊天。偶爾她也會說出很“聰明”的話。不過很容易判斷， 她的“智能”十分有限。 圖靈為我們留下了永久的遺產(chǎn)。他的智慧結(jié)晶，圖靈機，現(xiàn)在仍然是人們探 索人類自身能力和局限的有力工具。圖靈孤獨而默默地離開了我們，留下了許多 奧秘和疑團。就像人類面臨的其他許多奧秘一樣，我們有可能最終找到其中一些 的答案。還有很多，我們甚至將永遠無法知道，它們是不是有答案。 |
|
|
