引言

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

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

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

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

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

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

圖靈論文的內容會像下面這樣表示。

為了避免混淆，我們會更多地提及可計算序列，而非可計算數。

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

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

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

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

圖靈的論文分散在本書的第4~15章，其修訂內容在第16章。他的論文分為11個部分和一個附錄，對應到本書的頁碼是：

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

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

盡管我覺得本書的讀者大多會是計算機科學專業的學生、程序員或其他技術人員，但是我還是盡量讓非程序員的讀者也愿意讀，因此我定義了一些便于理解的術語。圖靈的論文被譽為“20世紀的一座知識地標”，我希望本書可以讓更多的讀者領略到這篇論文的風采。

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

第一部分“基礎”介紹閱讀圖靈論文所必須掌握的一些歷史和數學背景知識。

第二部分“可計算數”包含了圖靈論文的大部分內容，也是關心圖靈機和可計算性相關問題的讀者最感興趣的部分。

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

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

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

本書涉及數學中幾個大的研究領域，包括可計算性和數理邏輯。我僅僅把與理解圖靈論文最相關的那些主題和概念挑出來加以解釋，省去了很多細節，因此本書從深度和嚴格性上都無法取代那些可計算性和邏輯方面的專業書籍。想深入研究這些領域的讀者可以查閱參考文獻。

阿蘭·圖靈一生發表過近30篇論文和文章，卻從未寫過書。其中的兩篇論文造就了他流芳百世的聲望。“On Computable Numbers”（“論可計算數”）當然是第一篇。第二篇名為“Computing Machinery and Intelligence”（“計算機器和智能”，發表于1950年），這一篇的技術性不是很強，圖靈在文中首次提出了一種判斷人工智能的標準，在今天被稱為“圖靈測試”。總的來說，一臺機器如果可以騙得我們相信它是一個人，那么就可以說它是智能的。

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

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

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

如同早期的英國數學家、計算機先驅查爾斯·巴貝奇（1791—1871）和艾達·拉夫拉斯（1815—1852），圖靈也成為計算機時代的一個標志。美國計算機協會每年都會為在計算機行業做出杰出貢獻的人頒發圖靈獎，獎金為10萬美元。現在還有一些用來組裝圖靈機的工具，比如“圖靈編程語言”（從Pascal衍生而來）和“圖靈的世界”軟件。

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

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

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

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

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

人們以各種方式來表達對阿蘭·圖靈的尊敬當然是好事，不過這樣一來，圖靈的實際研究可能會被遺忘。我希望，就算那些正式研究過計算理論，并認為自己完全了解圖靈機的人，也能在面對這個真正由大師自己構建的圖靈機時發現不少令人驚奇的事物。

* * *

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

非常感謝倫敦數學協會許可完整地再版阿蘭·圖靈的論文“On Computable Numbers, with an Application to the Entscheidungsproblem”。

沃爾特·威廉姆斯和拉里·史密斯審閱了本書的初稿，發現了一些錯誤，并且提出了一些很有益的改進建議。

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

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

* * *

登錄網站www.TheAnnotatedTuring.com可以找到與本書相關的信息和資源。

查里斯·佩措爾德

紐約州紐約市和羅斯科

2008年5月