引言

研究過計(jì)算機(jī)的歷史、技術(shù)或理論的人，都會(huì)接觸到“圖靈機(jī)”這個(gè)概念。在1936年，為幫助解決數(shù)理邏輯中的一個(gè)問題，英國數(shù)學(xué)家阿蘭·圖靈（1912—1954）提出了圖靈機(jī)。它是一種純屬虛構(gòu)的計(jì)算機(jī)，連計(jì)算機(jī)假設(shè)也算不上。而由此得到的意外收獲是，圖靈創(chuàng)立了一個(gè)新的研究領(lǐng)域——計(jì)算理論（或可計(jì)算性），它主要研究數(shù)字計(jì)算機(jī)的功能和局限性。

盡管圖靈機(jī)是一種并不太合理的計(jì)算機(jī)，但由于其自身極其簡單而大放異彩。最基本的圖靈機(jī)只能進(jìn)行一些簡單的操作。如果連這些操作都不能做，那么這臺(tái)機(jī)器干脆什么都別做了。然而，只要將這些簡單的操作組合起來，圖靈機(jī)就能夠進(jìn)行現(xiàn)代數(shù)字計(jì)算機(jī)可以執(zhí)行的任何計(jì)算。

撥開云霧見天日，通過考查計(jì)算機(jī)的原始基礎(chǔ)，我們就能夠更好地理解數(shù)字計(jì)算機(jī)的能力和局限性，這二者同樣重要。盡管有人早就論證過計(jì)算機(jī)可以做什么，但在這種論證出現(xiàn)多年之前，圖靈就證明了計(jì)算機(jī)永遠(yuǎn)都做不到的事。

圖靈機(jī)仍然是被闡述和探討的熱門話題，你可以試試用喜愛的網(wǎng)絡(luò)搜索引擎搜索“圖靈機(jī)”。然而，我猜很少有人會(huì)閱讀阿蘭·圖靈描述他這項(xiàng)創(chuàng)造的原始論文。或許，這與論文的標(biāo)題“On Computable Numbers, with an Application to the Entscheidungsproblem”（“論可計(jì)算數(shù)及其在判定性問題上的應(yīng)用”）有關(guān)。即使你會(huì)讀最后那個(gè)單詞（試試看，將重音放在第二個(gè)音節(jié)上，把這個(gè)音節(jié)發(fā)成類似“shy”的音，這就差不多了），并且知道它的意思（即判定性問題），你可能也會(huì)擔(dān)心，圖靈一定指望他的讀者對(duì)繁冗的德國數(shù)學(xué)問題有基本的了解?？焖贋g覽這篇論文（其中還用到了德國哥特式字體來表示機(jī)器狀態(tài)）也無法讓人消除這種擔(dān)心。今天的讀者還能手捧70年前倫敦?cái)?shù)學(xué)學(xué)會(huì)集刊中的文章，并堅(jiān)持看到有所收獲，甚至十分滿意嗎？

這本書要講的正是這篇論文。它包含了圖靈原版36頁的論文¹“On Computable Numbers, with an Application to the Entscheidungsproblem”和增補(bǔ)的3頁修訂²，并輔以背景材料和大量注解。閱讀圖靈的原版論文就是在探索他構(gòu)建圖靈機(jī)的思維過程，就像在他充滿想象、內(nèi)容豐富的思想中進(jìn)行一次奇特的旅行。圖靈機(jī)不僅對(duì)計(jì)算產(chǎn)生了深遠(yuǎn)的影響，還深深影響了我們對(duì)數(shù)學(xué)局限性、人類思維方式，甚至宇宙本質(zhì)的理解。（當(dāng)然，圖靈的論文中并沒有出現(xiàn)“圖靈機(jī)”這個(gè)術(shù)語，他稱之為“計(jì)算機(jī)器”。不過，早在1937年³人們就開始使用“圖靈機(jī)”這種說法，并且至今仍是標(biāo)準(zhǔn)術(shù)語。）

¹ 阿蘭·圖靈，“On Computable Numbers, with an Application to the Entscheidungsproblem”，Proceedings of the London Mathematical Society，2nd series，Vol.42（1936），pp.230-265。

² 阿蘭·圖靈，“On Computable Numbers, with an Application to the Entscheidungsproblem A Correction”，Proceedings of the London Mathematical Society，2nd series，Vol.43，(1937)，pp.544-546。

³ 阿隆佐·邱奇對(duì)“On Computable Numbers, with an Application to the Entscheidungsproblem”，一文的評(píng)論，The Journal of Symbolic Logic，Vol. 2，No. 1，1937年3月，42-43。

我在對(duì)圖靈論文進(jìn)行注釋的過程中，發(fā)現(xiàn)用解釋和闡述頻繁打斷他的敘述還是很有用的。我努力做到（但并沒有完全做到）不打斷他的某一整句話。大部分情況下，我會(huì)在討論中保留圖靈自己的術(shù)語和符號(hào)，不過有時(shí)，雖然圖靈沒有采用某個(gè)術(shù)語，如果我覺得這個(gè)術(shù)語在解釋其工作時(shí)很有用，也會(huì)引入這些術(shù)語。

圖靈論文的內(nèi)容會(huì)像下面這樣表示。

為了避免混淆，我們會(huì)更多地提及可計(jì)算序列，而非可計(jì)算數(shù)。

我們（指出版商和我）努力保留圖靈原始論文的字體和版式，⁴除非有一些奇怪的表示方法（比如冒號(hào)前加空格）在現(xiàn)代文字處理軟件中總報(bào)錯(cuò)。原稿中所有的行間距也得以保留。圖靈的論文中存在一些印刷錯(cuò)誤、技術(shù)性錯(cuò)誤和理論上的疏漏，盡管我沒有在原文中加以修正，但會(huì)在評(píng)注中一一指出。圖靈對(duì)他自己論文內(nèi)容的引用，仍沿用原發(fā)表期刊中的頁碼，我沒有修改這些引用，不過在評(píng)注中指出了被引用部分在本書中的頁碼。偶爾，你會(huì)在圖靈的論文中發(fā)現(xiàn)一個(gè)括起來的數(shù)字，例如：

⁴ 中文版依然保留圖靈原始論文的印刷體和排版，其下是中譯文，譯文不再保留頁碼和版式?！幷咦?/p>

如果用數(shù)字代替這些字母，如在§5中，那么我們可以得到這個(gè)完全格局的數(shù)字表示，也可以稱作它的描述數(shù)。

這是原論文的分頁處以及標(biāo)注的頁碼。我這本書的腳注采用的是圓圈編號(hào)，而圖靈論文的腳注使用符號(hào)標(biāo)注，并寫在陰影部分。

如果只保留本書陰影部分的英文內(nèi)容，再組合起來，得到的就是完整的圖靈論文，而我這個(gè)勞而無功的作者只能欲哭無淚了。更有趣的閱讀方式是，先讀本書，再讀沒有被我打斷的圖靈論文。

圖靈的論文分散在本書的第4~15章，其修訂內(nèi)容在第16章。他的論文分為11個(gè)部分和一個(gè)附錄，對(duì)應(yīng)到本書的頁碼是：

圖靈寫這篇論文的最初動(dòng)機(jī)是想解決德國數(shù)學(xué)家大衛(wèi)·希爾伯特（1862—1943）構(gòu)想的一個(gè)問題。希爾伯特想尋找一種通用的方法來判定數(shù)理邏輯中的任意命題是否可證。尋找這種“通用的方法”被稱為判定性問題。盡管判定性問題確實(shí)是圖靈寫這篇論文的動(dòng)機(jī)，但是這篇長篇大論本身講的卻是可計(jì)算數(shù)。在圖靈的定義中，可計(jì)算數(shù)就是可以使用機(jī)器計(jì)算的數(shù)。論文前面60%的內(nèi)容都是圖靈對(duì)可計(jì)算數(shù)的探索，就算完全不了解希爾伯特在數(shù)理邏輯或判定性問題方面的研究，也能夠閱讀并理解這些內(nèi)容。

了解可計(jì)算數(shù)與“實(shí)數(shù)”的區(qū)別對(duì)于理解圖靈的觀點(diǎn)很重要。因此，本書利用前幾章介紹了數(shù)字分類的背景知識(shí)，數(shù)字包括整數(shù)、有理數(shù)、無理數(shù)、代數(shù)數(shù)和超越數(shù)，它們都可歸為實(shí)數(shù)。我盡可能不涉及比高中數(shù)學(xué)更復(fù)雜的知識(shí)。我知道，有些讀者離開快樂的高中生活已經(jīng)幾十年了，我要努力喚醒這些記憶。如果由于我本著這種教育熱情而做出一些冒犯讀者的解釋，我表示歉意。

盡管我覺得本書的讀者大多會(huì)是計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生、程序員或其他技術(shù)人員，但是我還是盡量讓非程序員的讀者也愿意讀，因此我定義了一些便于理解的術(shù)語。圖靈的論文被譽(yù)為“20世紀(jì)的一座知識(shí)地標(biāo)”⁵，我希望本書可以讓更多的讀者領(lǐng)略到這篇論文的風(fēng)采。

⁵ 這一說法是John P. Burgess在George S. Boolos、John P. Burgess和Richard C. Jeffrey所著的 Computability and Logic, fourth edition（Cambridge University Press，2002）一書的前言中提到的。

為了滿足不同讀者的需要，本書分成了四個(gè)部分。

第一部分“基礎(chǔ)”介紹閱讀圖靈論文所必須掌握的一些歷史和數(shù)學(xué)背景知識(shí)。

第二部分“可計(jì)算數(shù)”包含了圖靈論文的大部分內(nèi)容，也是關(guān)心圖靈機(jī)和可計(jì)算性相關(guān)問題的讀者最感興趣的部分。

第三部分“判定性問題”先簡要介紹了數(shù)理邏輯的背景知識(shí)，然后討論圖靈論文的剩余部分。

第四部分“題外話”討論了圖靈機(jī)為何成為人們理解計(jì)算機(jī)、人類意識(shí)和宇宙本身的必要工具。

第三部分的數(shù)學(xué)內(nèi)容肯定是比前幾章的難，并且講得比較快。對(duì)圖靈論文在數(shù)理邏輯方面的影響不感興趣的讀者甚至可以跳過第三部分，直接閱讀第四部分。

本書涉及數(shù)學(xué)中幾個(gè)大的研究領(lǐng)域，包括可計(jì)算性和數(shù)理邏輯。我僅僅把與理解圖靈論文最相關(guān)的那些主題和概念挑出來加以解釋，省去了很多細(xì)節(jié)，因此本書從深度和嚴(yán)格性上都無法取代那些可計(jì)算性和邏輯方面的專業(yè)書籍。想深入研究這些領(lǐng)域的讀者可以查閱參考文獻(xiàn)。

阿蘭·圖靈一生發(fā)表過近30篇論文和文章⁶，卻從未寫過書。其中的兩篇論文造就了他流芳百世的聲望?！癘n Computable Numbers”（“論可計(jì)算數(shù)”）當(dāng)然是第一篇。第二篇名為“Computing Machinery and Intelligence”（“計(jì)算機(jī)器和智能”，發(fā)表于1950年），這一篇的技術(shù)性不是很強(qiáng)，圖靈在文中首次提出了一種判斷人工智能的標(biāo)準(zhǔn)，在今天被稱為“圖靈測(cè)試”。總的來說，一臺(tái)機(jī)器如果可以騙得我們相信它是一個(gè)人，那么就可以說它是智能的。

⁶ 這些和其他文檔可以從The Collected Works of A.M. Turing（Amsterdam: Elsevier，1992，2001）的4卷中獲得。其中大部分重要資料由B. Jack Copeland收集到The Essential Turing（Oxford University Press，2004）和Alan Turing's Automatic Computing Engine（Oxford University Press，2005）中。前者包含了與圖靈機(jī)相關(guān)的文章和論文，后者是關(guān)于20世紀(jì)40年代中后期ACE計(jì)算機(jī)工程的。

圖靈機(jī)和圖靈測(cè)試是阿蘭·圖靈聲名不朽的兩大基石。初看上去，它們像是兩個(gè)完全不同的概念，但事實(shí)并非如此。圖靈機(jī)是以一種非常機(jī)械的方式展現(xiàn)人類如何進(jìn)行數(shù)學(xué)運(yùn)算的，圖靈測(cè)試則是對(duì)計(jì)算機(jī)能力的人為評(píng)估。在整個(gè)數(shù)學(xué)研究期間，圖靈都在探索人類思維和計(jì)算機(jī)器之間的關(guān)系，他所采用的研究方法至今仍很吸引人。

很多關(guān)于可計(jì)算性的教科書只討論圖靈的研究而不涉及圖靈這個(gè)人，它們可沒有勞神講述有關(guān)個(gè)人傳記的細(xì)節(jié)。不過，本書不會(huì)這么做。圖靈在二戰(zhàn)期間所做的密碼分析方面的秘密工作，他參與的影響力巨大的計(jì)算機(jī)工程，他對(duì)于人工智能的思索，他的性取向，他由于“嚴(yán)重猥褻”罪而被逮捕和起訴的經(jīng)歷，以及他在41歲時(shí)自殺身亡，所有這些事情都需要關(guān)注。

得益于英國數(shù)學(xué)家安德魯·霍奇斯（1949—　）撰寫的精彩傳記Alan Turing: The Enigma（《艾倫·圖靈傳：如謎的解謎者》，Simon & Schuster，1983年出版），我沒費(fèi)多大力氣就總結(jié)出了圖靈一生中的重要事件?；羝嫠箤?duì)圖靈感興趣的部分原因，在于他參與了20世紀(jì)70年代的同性戀解放運(yùn)動(dòng)?；羝嫠沟膫饔涍€給休·懷特摩爾的劇本Breaking the Code（《破解密碼》，1986）帶來了靈感，在舞臺(tái)上和在1996年改編的電視片中，阿蘭·圖靈的角色都是由德里克·雅克比扮演的。

如同早期的英國數(shù)學(xué)家、計(jì)算機(jī)先驅(qū)查爾斯·巴貝奇（1791—1871）和艾達(dá)·拉夫拉斯（1815—1852），圖靈也成為計(jì)算機(jī)時(shí)代的一個(gè)標(biāo)志。美國計(jì)算機(jī)協(xié)會(huì)每年都會(huì)為在計(jì)算機(jī)行業(yè)做出杰出貢獻(xiàn)的人頒發(fā)圖靈獎(jiǎng)，獎(jiǎng)金為10萬美元。現(xiàn)在還有一些用來組裝圖靈機(jī)的工具，比如“圖靈編程語言”（從Pascal衍生而來）和“圖靈的世界”軟件。

圖靈的名字幾乎成為計(jì)算機(jī)編程的通用代名詞。杜特尼把他的“計(jì)算機(jī)科學(xué)探索”一書命名為The Turing Omnibus（《圖靈選集》，計(jì)算機(jī)科學(xué)出版社，1989）。戴維德·波爾特把他編寫的一本關(guān)于“計(jì)算機(jī)時(shí)代的西方文化”的書命名為Turing's Man（《圖靈時(shí)代的人類》，北卡羅來納州大學(xué)出版社，1984）。布萊恩·羅特曼對(duì)傳統(tǒng)數(shù)學(xué)極限概念的評(píng)論文章Ad Infinitum（斯坦福大學(xué)出版社，1993）被幽默地加上了副標(biāo)題The Ghost in Turing's Machine（《圖靈機(jī)里的幽靈》）。

數(shù)學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域以外的學(xué)者也對(duì)阿蘭·圖靈感興趣。研究文集Novel Gazing: Queer Readings in Fiction（《凝神注視：論小說的另類解讀》）中最有特色的一篇文章就是由泰勒·科坦撰寫的The“Sinister Fruitiness”of Machines: Neuromancer, Internet Sexuality, and the Turing Test（《智能機(jī)器帶來的“陰暗苦果”：神經(jīng)漫游者、網(wǎng)絡(luò)性愛和圖靈測(cè)試》）?？铺共┦克f的Neuromancer指的是威廉·吉布森著名的“賽博朋克”小說Neuromancer（《神經(jīng)漫游者》）。在這部科幻小說里，有一個(gè)叫做圖靈警察局的組織，他們負(fù)責(zé)確保人工智能體不會(huì)試圖增強(qiáng)它們自身的智能。

圖靈還出現(xiàn)在很多小說的書名中。馬文·明斯基（麻省理工學(xué)院人工智能方向著名的研究者）與科幻小說家哈里·哈里森合寫了The Turing Option（《圖靈選擇》，華納圖書公司，1992）。伯克利計(jì)算機(jī)科學(xué)教授克里斯托斯·帕帕迪米特里歐參與創(chuàng)作了Turing（《圖靈》，一部關(guān)于計(jì)算的小說，麻省理工學(xué)院出版社，2003）。

玻利維亞小說家埃德蒙多·蘇丹寫了一本名為Turing's Delirium（《圖靈的狂熱》，英文版由麗莎·卡特翻譯，霍頓·米夫林出版公司，2006）的小說，在其中，一個(gè)外號(hào)叫圖靈的密碼專家發(fā)現(xiàn)了用他的技能為腐敗政府服務(wù)帶來的危險(xiǎn)。在珍娜·列文的小說A Madman Dreams of Turing Machines（《圖靈機(jī)狂人夢(mèng)》，Knopf出版社，2006）中，阿蘭·圖靈和庫爾特·哥德爾的生活被虛構(gòu)在了一起，他們穿越時(shí)空，產(chǎn)生了奇特的交織。

阿蘭·圖靈這個(gè)角色還出現(xiàn)在其他很多小說中，如尼爾·斯蒂芬森的Cryptonomicon（《編碼寶典》，Avon，1999），羅伯特·哈里斯的Enigma（《密碼迷情》，Hutchinson，1995），約翰·卡斯蒂的The Cambridge Quintet: A Work of Scientific Speculation（《劍橋五重奏：一部科學(xué)思考的著作》，Perseus圖書公司，1998），以及道格拉斯·侯世達(dá)的G?del, Escher, Bach⁷（Basic圖書公司，1979）。阿蘭·圖靈甚至為The Turing Test（《圖靈測(cè)試》，BBC， 2000）的一部分做了解說，這本書是保羅·倫納德寫的Doctor Who系列小說中的一本。

⁷ 中文版《哥德爾、埃舍爾、巴赫——集異璧之大成》由商務(wù)印書館1996年8月出版。——譯者注

人們以各種方式來表達(dá)對(duì)阿蘭·圖靈的尊敬當(dāng)然是好事，不過這樣一 來，圖靈的實(shí)際研究可能會(huì)被遺忘。我希望，就算那些正式研究過計(jì)算理論，并認(rèn)為自己完全了解圖靈機(jī)的人，也能在面對(duì)這個(gè)真正由大師自己構(gòu)建的圖靈機(jī)時(shí)發(fā)現(xiàn)不少令人驚奇的事物。

*　*　*

我在1999年就開始構(gòu)思這本書，當(dāng)時(shí)只寫了一點(diǎn)，然后在接下來的五年里時(shí)不時(shí)又寫上一些。2004～2005年基本完成了前11章。后面7章是在2007～2008年完成的，在此期間的寫作幾乎未中斷，唯一的中斷就是與我一生中最好的朋友，也是我的至愛迪爾德麗·辛諾特結(jié)婚（終于結(jié)婚啦）！

非常感謝倫敦?cái)?shù)學(xué)協(xié)會(huì)許可完整地再版阿蘭·圖靈的論文“On Computable Numbers, with an Application to the Entscheidungsproblem”。

沃爾特·威廉姆斯和拉里·史密斯審閱了本書的初稿，發(fā)現(xiàn)了一些錯(cuò)誤，并且提出了一些很有益的改進(jìn)建議。

非常感謝Wiley出版公司的同仁，正是他們的工作將我所鐘愛的想法真正出版成書?？死锼埂?韋伯負(fù)責(zé)督促這本書的出版，策劃編輯克里斯多夫· 里韋拉和制作編輯安吉拉·史密斯克服了很多版式和印刷方面的困難，技術(shù)編輯彼得·伯凡蒂幫助我認(rèn)真完成了技術(shù)相關(guān)的內(nèi)容。Wiley出版公司的很多幕后工作人員也都努力把這本書做得至臻至善。所有未被發(fā)現(xiàn)而遺留在書中的缺陷、瑕疵或隱藏的錯(cuò)誤，都只能歸咎于作者。

每位作者都是站在前人肩上的。選出的參考書目只列出了我所參考的眾多書籍中的一小部分。我還要感謝紐約公共圖書館，特別是科學(xué)、工業(yè)和商業(yè)圖書館的工作人員。為參考原始論文，我多次使用JSTOR，同時(shí)我發(fā)現(xiàn)維基百科、谷歌書籍搜索和Wolfram MathWorld也都很有用。

*　*　*

登錄網(wǎng)站www.TheAnnotatedTuring.com可以找到與本書相關(guān)的信息和資源。

查里斯·佩措爾德

紐約州紐約市和羅斯科

2008年5月