孤獨的破譯者和他的計算機器（修訂稿）

作者：若奇

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

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

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

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

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

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

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

　　為了理解圖靈的主要貢獻，讓我們簡單回顧一下19世紀20世紀之交數(shù)學界的
狀況。

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

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

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

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

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

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

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

　?。玻笆兰o帶來的，卻幾乎是徹底的相反。

　　藝術上的反叛首先引人注目。抽象派的立體、殘缺不全的幾何圖形顛覆了人
們對古典美的欣賞。音樂界從斯塔文斯基開始，喧鬧而不和諧的“雜亂無章”，
使得晚期浪漫主義風格的瓦格納和德彪西顯得過于柔順。物理學上的沖擊來自１
９０５年，愛因斯坦的幾篇劃時代論文徹底顛覆了牛頓經(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ā)師，
給不給自己修面？他寫信給奠定了集合論基礎的弗雷澤求教，立刻使得弗雷澤
“精神崩潰”，無法回避他畢生的工作存在這樣無法自圓其說的“漏洞”。羅素
自己擔起了為數(shù)學撥亂反正的重任。他試圖將集合分成不同的類型，每個類型只
能包含特定的類型，從而避免類似理發(fā)師悖論那樣由于自我引用導致的悖論。他
和懷特黑用了幾十頁的篇幅，最終成功地證明１＋１＝２（不是哥德巴赫猜想，
而是初等算術）！

　　順便提及，1957年，紐維爾(Allen Newell, 1927-1992)等人使用計算機證
明了《數(shù)學原理》中的許多定理。他們寫信將結果報知羅素。羅素不無調(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ū)С鏊姓婷}?？梢韵胂笙柌貍儠詭Р恍嫉卣f，“不早告訴你了”。
１９３０年，重磅炸彈橫空出世。哥德爾進一步證明，如果將算術運算公理引入
一階謂詞系統(tǒng)，則由此而成的算術運算系統(tǒng)是不完備的，即存在這樣的命題，它
們的真?zhèn)问遣豢勺C明的。這個結論的一個前提是，算術運算系統(tǒng)是一致的。由此
自然得到，一致性的證明不可能從系統(tǒng)內(nèi)部完成，即算術運算系統(tǒng)的一致性不能
由其自身證明！

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

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

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

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

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

　　那么，圖靈機到底是怎樣一個神通廣大的機器？讓我們跟隨圖靈的論文，進
入圖靈機的王國。

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

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

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

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

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

　　那么，這樣“簡陋”的機器到底如何工作呢？

　　圖靈在論文中給出了兩個具體計算機器的例子，一個計算二進制０.０１０
１０１。。。（十進制的１／３），另一個計算超越數(shù)０.０１０１１０１１１
０１１１１.。。。我們來看計算1/3的例子。我們只需一條空白帶子和四個狀態(tài)
來構造這個圖靈機：
	
		配置				行為
	狀態(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)”下去，永不停歇。機器“寫”出的結
果是010101.．．。按圖靈的約定，結果應按前面加上小數(shù)點理解，于是我們得
到 0.010101．．．，也就是十進制的１／3。注意，根據(jù)圖靈的定義，只有永遠
不停“寫出”0或1序列的機器才是正常的，“好”的機器。

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

　　圖靈機的操作是如此原始，以至于連進行簡單加減運算都需要許多繁復步驟
才能完成。如果要計算更復雜的問題，豈非要算到“地老天荒“？但圖靈對這些
具體運算根本毫無興趣。他所關心的不是要花多少時間，需要多長的帶子才能完
成某個計算，而是可不可能完成它。

　　圖靈定義抽象計算機器的方法亦有很大彈性，改變一些細節(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，然后左移一格（進位），重復i操作。如果當前符號是空白，說明進位到了新
的最高位，于是打印1。然后轉(zhuǎn)到狀態(tài)r（rewind，回到最后一位有效數(shù)字）。這
個圖靈機依次打印0，1，10（十進制2），11（十進制3），100（十進制4） 等
等。讀者可以看到，這個“加法器”對原始圖靈機有多處修改，例如，它每次新
打印的數(shù)字都覆蓋了前一個數(shù)字；它不使用E-格，也不隔格打??；它的結果向左
方而不是向右方“延伸”，等等。

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

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

　　我們再來看一個圖靈論文中稍為復雜的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)看出，這里包含了計算機程序設計中的遞歸調(diào)用，以及許多老一
代程序語言都不支持的函數(shù)“overloading”。圖靈的思想確實大大超前于時代。

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

　　圖靈機的計算結果是一個可計算序列。顯然，對一個可計算序列，可以構造
不同的圖靈機，它們的計算結果相同。為了用一種標準方式表達圖靈機的結構，
他將圖靈機的配置“規(guī)范化”一個五元組

　　（當前狀態(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）唯一地確定一個圖靈
機的結構，也就是唯一一個可計算序列。反過來，對每個可計算序列，至少存在
一個標準表達數(shù)。不難想象，絕大部分任意正整數(shù)都不是一個合格的圖靈機的標
準表達數(shù)。事實上，最小的可作為圖靈機標準表達數(shù)的正整數(shù)是３１３３４３１
７（只打印空格！因此，這個圖靈機按圖靈的定義是一個不好的機器）。最小的
完全符合圖靈定義的“好”圖靈機標準表達數(shù)是313325317（計算0.1111.。。）。

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

　　繞了這么大一個圈子，圖靈到底要干什么？別急。好戲才剛開場。

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

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

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

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

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

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

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

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

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

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

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

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

　　正如一部關于可計算性理論的著名專著中所評價的，“圖靈關于通用圖靈機
存在的定理是上個世紀的智力里程碑之一”。

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

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

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

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

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

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

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

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

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