圖靈的秘密

前言

引　　言研究過(guò)計(jì)算機(jī)的歷史、技術(shù)或理論的人，都會(huì)接觸到“圖靈機(jī)”這個(gè)概念。在1936年，為幫助解決數(shù)理邏輯中的一個(gè)問題，英國(guó)數(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ī)，但由于其自身極其簡(jiǎn)單而大放異彩。最基本的圖靈機(jī)只能進(jìn)行一些簡(jiǎn)單的操作。如果連這些操作都不能做，那么這臺(tái)機(jī)器干脆什么都別做了。然而，只要將這些簡(jiǎn)單的操作組合起來(lái)，圖靈機(jī)就能夠進(jìn)行現(xiàn)代數(shù)字計(jì)算機(jī)可以執(zhí)行的任何計(jì)算。撥開云霧見天日，通過(guò)考查計(jì)算機(jī)的原始基礎(chǔ)，我們就能夠更好地理解數(shù)字計(jì)算機(jī)的能力和局限性，這二者同樣重要。盡管有人早就論證過(guò)計(jì)算機(jī)可以做什么，但在這種論證出現(xiàn)多年之前，圖靈就證明了計(jì)算機(jī)永遠(yuǎn)都做不到的事。圖靈機(jī)仍然是被闡述和探討的熱門話題，你可以試試用喜愛的網(wǎng)絡(luò)搜索引擎搜索“圖靈機(jī)”。然而，我猜很少有人會(huì)閱讀阿蘭·圖靈描述他這項(xiàng)創(chuàng)造的原始論文?；蛟S，這與論文的標(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ì)繁冗的德國(guó)數(shù)學(xué)問題有基本的了解?？焖贋g覽這篇論文（其中還用到了德國(guó)哥特式字體來(lái)表示機(jī)器狀態(tài)）也無(wú)法讓人消除這種擔(dān)心。今天的讀者還能手捧70年前倫敦?cái)?shù)學(xué)學(xué)會(huì)集刊中的文章，并堅(jiān)持看到有所收獲，甚至十分滿意嗎？這本書要講的正是這篇論文。它包含了圖靈原版36頁(yè)的論文 “On Computable Numbers， with an Application to the Entscheidungsproblem”和增補(bǔ)的3頁(yè)修訂 ，并輔以背景材料和大量注解。閱讀圖靈的原版論文就是在探索他構(gòu)建圖靈機(jī)的思維過(guò)程，就像在他充滿想象、內(nèi)容豐富的思想中進(jìn)行一次奇特的旅行。圖靈機(jī)不僅對(duì)計(jì)算產(chǎn)生了深遠(yuǎn)的影響，還深深影響了我們對(duì)數(shù)學(xué)局限性、人類思維方式，甚至宇宙本質(zhì)的理解。（當(dāng)然，圖靈的論文中并沒有出現(xiàn)“圖靈機(jī)”這個(gè)術(shù)語(yǔ)，他稱之為“計(jì)算機(jī)器”。不過(guò)，早在1937年 人們就開始使用“圖靈機(jī)”這種說(shuō)法，并且至今仍是標(biāo)準(zhǔn)術(shù)語(yǔ)。）我在對(duì)圖靈論文進(jìn)行注釋的過(guò)程中，發(fā)現(xiàn)用解釋和闡述頻繁打斷他的敘述還是很有用的。我努力做到（但并沒有完全做到）不打斷他的某一整句話。大部分情況下，我會(huì)在討論中保留圖靈自己的術(shù)語(yǔ)和符號(hào)，不過(guò)有時(shí)，雖然圖靈沒有采用某個(gè)術(shù)語(yǔ)，如果我覺得這個(gè)術(shù)語(yǔ)在解釋其工作時(shí)很有用，也會(huì)引入這些術(shù)語(yǔ)。圖靈論文的內(nèi)容會(huì)像下面這樣表示。為了避免混淆，我們會(huì)更多地提及可計(jì)算序列，而非可計(jì)算數(shù)。我們（指出版商和我）努力保留圖靈原始論文的字體和版式， 除非有一些奇怪的表示方法（比如冒號(hào)前加空格）在現(xiàn)代文字處理軟件中總報(bào)錯(cuò)。原稿中所有的行間距也得以保留。圖靈的論文中存在一些印刷錯(cuò)誤、技術(shù)性錯(cuò)誤和理論上的疏漏，盡管我沒有在原文中加以修正，但會(huì)在評(píng)注中一一指出。圖靈對(duì)他自己論文內(nèi)容的引用，仍沿用原發(fā)表期刊中的頁(yè)碼，我沒有修改這些引用，不過(guò)在評(píng)注中指出了被引用部分在本書中的頁(yè)碼。偶爾，你會(huì)在圖靈的論文中發(fā)現(xiàn)一個(gè)括起來(lái)的數(shù)字，例如：如果用數(shù)字代替這些字母，如在§5中，那么我們可以得到這個(gè)完全格局的數(shù)字表示，也可以稱作它的描述數(shù)。這是原論文的分頁(yè)處以及標(biāo)注的頁(yè)碼。我這本書的腳注采用的是圓圈編號(hào)，而圖靈論文的腳注使用符號(hào)標(biāo)注，并寫在陰影部分。如果只保留本書陰影部分的英文內(nèi)容，再組合起來(lái)，得到的就是完整的圖靈論文，而我這個(gè)勞而無(wú)功的作者只能欲哭無(wú)淚了。更有趣的閱讀方式是，先讀本書，再讀沒有被我打斷的圖靈論文。圖靈的論文分散在本書的第4~15章，其修訂內(nèi)容在第16章。他的論文分為11個(gè)部分和一個(gè)附錄，對(duì)應(yīng)到本書的頁(yè)碼是：1. 計(jì)算機(jī)器　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　582. 定義　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　633. 計(jì)算機(jī)器示例　　　　　　　　　　　　　　　　　　　　　　　　　　　 694. 縮略表　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　995. 可計(jì)算序列的枚舉　　　　　　　　　　　　　　　　　　　　　　　1186. 通用計(jì)算機(jī)器　　　　　　　　　　　　　　　　　　　　　　　　　　　 1307. 通用機(jī)的詳細(xì)描述　　　　　　　　　　　　　　　　　　　　　　　1368. 對(duì)角線法的應(yīng)用　　　　　　　　　　　　　　　　　　　　　　　1589. 可計(jì)算數(shù)的范疇　　　　　　　　　　　　　　　　　　　　　　　　17510. 大量可計(jì)算數(shù)的示例　　　　　　　　　　　　　　　　　　　　21911. 在判定性問題中的應(yīng)用　　　　　　　　　　　　　　　　　　　　　244附錄　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　274圖靈寫這篇論文的最初動(dòng)機(jī)是想解決德國(guó)數(shù)學(xué)家大衛(wèi)·希爾伯特（1862—1943）構(gòu)想的一個(gè)問題。希爾伯特想尋找一種通用的方法來(lái)判定數(shù)理邏輯中的任意命題是否可證。尋找這種“通用的方法”被稱為判定性問題。盡管判定性問題確實(shí)是圖靈寫這篇論文的動(dòng)機(jī)，但是這篇長(zhǎng)篇大論本身講的卻是可計(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ù)、無(wú)理數(shù)、代數(shù)數(shù)和超越數(shù)，它們都可歸為實(shí)數(shù)。我盡可能不涉及比高中數(shù)學(xué)更復(fù)雜的知識(shí)。我知道，有些讀者離開快樂的高中生活已經(jīng)幾十年了，我要努力喚醒這些記憶。如果由于我本著這種教育熱情而做出一些冒犯讀者的解釋，我表示歉意。盡管我覺得本書的讀者大多會(huì)是計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生、程序員或其他技術(shù)人員，但是我還是盡量讓非程序員的讀者也愿意讀，因此我定義了一些便于理解的術(shù)語(yǔ)。圖靈的論文被譽(yù)為“20世紀(jì)的一座知識(shí)地標(biāo)” ，我希望本書可以讓更多的讀者領(lǐng)略到這篇論文的風(fēng)采。為了滿足不同讀者的需要，本書分成了四個(gè)部分。第一部分“基礎(chǔ)”介紹閱讀圖靈論文所必須掌握的一些歷史和數(shù)學(xué)背景知識(shí)。第二部分“可計(jì)算數(shù)”包含了圖靈論文的大部分內(nèi)容，也是關(guān)心圖靈機(jī)和可計(jì)算性相關(guān)問題的讀者最感興趣的部分。第三部分“判定性問題”先簡(jiǎn)要介紹了數(shù)理邏輯的背景知識(shí)，然后討論圖靈論文的剩余部分。第四部分“題外話”討論了圖靈機(jī)為何成為人們理解計(jì)算機(jī)、人類意識(shí)和宇宙本身的必要工具。第三部分的數(shù)學(xué)內(nèi)容肯定是比前幾章的難，并且講得比較快。對(duì)圖靈論文在數(shù)理邏輯方面的影響不感興趣的讀者甚至可以跳過(guò)第三部分，直接閱讀第四部分。本書涉及數(shù)學(xué)中幾個(gè)大的研究領(lǐng)域，包括可計(jì)算性和數(shù)理邏輯。我僅僅把與理解圖靈論文最相關(guān)的那些主題和概念挑出來(lái)加以解釋，省去了很多細(xì)節(jié)，因此本書從深度和嚴(yán)格性上都無(wú)法取代那些可計(jì)算性和邏輯方面的專業(yè)書籍。想深入研究這些領(lǐng)域的讀者可以查閱參考文獻(xiàn)。阿蘭·圖靈一生發(fā)表過(guò)近30篇論文和文章 ，卻從未寫過(guò)書。其中的兩篇論文造就了他流芳百世的聲望?！癘n Computable Numbers”（“論可計(jì)算數(shù)”）當(dāng)然是第一篇。第二篇名為“Computing Machinery and Intelligence”（“計(jì)算機(jī)器和智能”，發(fā)表于1950年），這一篇的技術(shù)性不是很強(qiáng)，圖靈在文中首次提出了一種判斷人工智能的標(biāo)準(zhǔn)，在今天被稱為“圖靈測(cè)試”?？偟膩?lái)說(shuō)，一臺(tái)機(jī)器如果可以騙得我們相信它是一個(gè)人，那么就可以說(shuō)它是智能的。圖靈機(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é)。不過(guò)，本書不會(huì)這么做。圖靈在二戰(zhàn)期間所做的密碼分析方面的秘密工作，他參與的影響力巨大的計(jì)算機(jī)工程，他對(duì)于人工智能的思索，他的性取向，他由于“嚴(yán)重猥褻”罪而被逮捕和起訴的經(jīng)歷，以及他在41歲時(shí)自殺身亡，所有這些事情都需要關(guān)注。得益于英國(guó)數(shù)學(xué)家安德魯·霍奇斯（1949—?。┳珜懙木蕚饔汚lan Turing： The Enigma（《艾倫·圖靈傳：如謎的解謎者》，Simon & Schuster，1983年出版），我沒費(fèi)多大力氣就總結(jié)出了圖靈一生中的重要事件?；羝嫠箤?duì)圖靈感興趣的部分原因，在于他參與了20世紀(jì)70年代的同性戀解放運(yùn)動(dòng)?；羝嫠沟膫饔涍€給休·懷特摩爾的劇本Breaking the Code（《破解密碼》，1986）帶來(lái)了靈感，在舞臺(tái)上和在1996年改編的電視片中，阿蘭·圖靈的角色都是由德里克·雅克比扮演的。如同早期的英國(guó)數(shù)學(xué)家、計(jì)算機(jī)先驅(qū)查爾斯·巴貝奇（1791—1871）和艾達(dá)·拉夫拉斯（1815—1852），圖靈也成為計(jì)算機(jī)時(shí)代的一個(gè)標(biāo)志。美國(guó)計(jì)算機(jī)協(xié)會(huì)每年都會(huì)為在計(jì)算機(jī)行業(yè)做出杰出貢獻(xiàn)的人頒發(fā)圖靈獎(jiǎng)，獎(jiǎng)金為10萬(wàn)美元。現(xiàn)在還有一些用來(lái)組裝圖靈機(jī)的工具，比如“圖靈編程語(yǔ)言”（從Pascal衍生而來(lái)）和“圖靈的世界”軟件。圖靈的名字幾乎成為計(jì)算機(jī)編程的通用代名詞。杜特尼把他的“計(jì)算機(jī)科學(xué)探索”一書命名為The Turing Omnibus（《圖靈選集》，計(jì)算機(jī)科學(xué)出版社，1989）。戴維德·波爾特把他編寫的一本關(guān)于“計(jì)算機(jī)時(shí)代的西方文化”的書命名為Turing’s Man（《圖靈時(shí)代的人類》，北卡羅來(lái)納州大學(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（《凝神注視：論小說(shuō)的另類解讀》）中最有特色的一篇文章就是由泰勒·科坦撰寫的The“Sinister Fruitiness”of Machines： Neuromancer， Internet Sexuality， and the Turing Test（《智能機(jī)器帶來(lái)的“陰暗苦果”：神經(jīng)漫游者、網(wǎng)絡(luò)性愛和圖靈測(cè)試》）。科坦博士所說(shuō)的Neuromancer指的是威廉·吉布森著名的“賽博朋克”小說(shuō)Neuromancer（《神經(jīng)漫游者》）。在這部科幻小說(shuō)里，有一個(gè)叫做圖靈警察局的組織，他們負(fù)責(zé)確保人工智能體不會(huì)試圖增強(qiáng)它們自身的智能。圖靈還出現(xiàn)在很多小說(shuō)的書名中。馬文·明斯基（麻省理工學(xué)院人工智能方向著名的研究者）與科幻小說(shuō)家哈里·哈里森合寫了The Turing Option（《圖靈選擇》，華納圖書公司，1992）。伯克利計(jì)算機(jī)科學(xué)教授克里斯托斯·帕帕迪米特里歐參與創(chuàng)作了Turing（《圖靈》，一部關(guān)于計(jì)算的小說(shuō)，麻省理工學(xué)院出版社，2003）。玻利維亞小說(shuō)家埃德蒙多·蘇丹寫了一本名為Turing’s Delirium（《圖靈的狂熱》，英文版由麗莎·卡特翻譯，霍頓·米夫林出版公司，2006）的小說(shuō)，在其中，一個(gè)外號(hào)叫圖靈的密碼專家發(fā)現(xiàn)了用他的技能為腐敗政府服務(wù)帶來(lái)的危險(xiǎn)。在珍娜·列文的小說(shuō)A Madman Dreams of Turing Machines（《圖靈機(jī)狂人夢(mèng)》，Knopf出版社，2006）中，阿蘭·圖靈和庫(kù)爾特·哥德爾的生活被虛構(gòu)在了一起，他們穿越時(shí)空，產(chǎn)生了奇特的交織。阿蘭·圖靈這個(gè)角色還出現(xiàn)在其他很多小說(shuō)中，如尼爾·斯蒂芬森的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）的一部分做了解說(shuō)，這本書是保羅·倫納德寫的Doctor Who系列小說(shuō)中的一本。人們以各種方式來(lái)表達(dá)對(duì)阿蘭·圖靈的尊敬當(dāng)然是好事，不過(guò)這樣一來(lái)，圖靈的實(shí)際研究可能會(huì)被遺忘。我希望，就算那些正式研究過(guò)計(jì)算理論，并認(rèn)為自己完全了解圖靈機(jī)的人，也能在面對(duì)這個(gè)真正由大師自己構(gòu)建的圖靈機(jī)時(shí)發(fā)現(xiàn)不少令人驚奇的事物。*　*　*我在1999年就開始構(gòu)思這本書，當(dāng)時(shí)只寫了一點(diǎn)，然后在接下來(lái)的五年里時(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)站可以找到與本書相關(guān)的信息和資源。查里斯·佩措爾德紐約州紐約市和羅斯科2008年5月

內(nèi)容概要

　　在數(shù)字計(jì)算機(jī)出現(xiàn)之前，阿蘭?圖靈就預(yù)想了它們的功能和通用性……也證明了哪些事是計(jì)算機(jī)永遠(yuǎn)做不了的。
　　由Windows編程大師Charles Petzold耗時(shí)多年編寫的這本書剖析了現(xiàn)代計(jì)算機(jī)原理開山之作、阿蘭?圖靈流芳百世的論文
“On Computable Numbers, with an Application to the
Entscheidungsproblem”。圖靈在其中描述了一種假想的計(jì)算機(jī)器，探索了其功能和內(nèi)在的局限性，由此建立了現(xiàn)代程序設(shè)計(jì)和可計(jì)算性的基礎(chǔ)。這本書也像是一本小說(shuō)，行文間穿插講述了圖靈的成長(zhǎng)經(jīng)歷和教育背景，以及他跌宕起伏的一生，包括破解德國(guó)恩尼格密碼的傳奇經(jīng)歷，他對(duì)人工智能的探索，他的性取向，以及最終因同性戀的罪名而在41歲時(shí)自殺的悲慘結(jié)局。全書完整揭示了阿蘭?圖靈非凡、傳奇而悲劇的一生，是了解圖靈的思想和生平的極好著作。
阿蘭·圖靈（1912—1954）是英國(guó)數(shù)學(xué)家、邏輯學(xué)家，被稱為計(jì)算機(jī)科學(xué)之父、人工智能之父，是計(jì)算機(jī)邏輯的奠基者，提出了“圖靈機(jī)”和“圖靈測(cè)試”等重要概念。為紀(jì)念他在計(jì)算機(jī)領(lǐng)域的卓越貢獻(xiàn)，美國(guó)計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立圖靈獎(jiǎng)，此獎(jiǎng)項(xiàng)被譽(yù)為計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)。

作者簡(jiǎn)介

　　Charles Petzold
　Windows編程大師、世界頂級(jí)技術(shù)作家、微軟資深MVP，擁有25年的Windows編程經(jīng)驗(yàn)。1994年5月，Petzold作為唯一的作家，獲得由微軟公司和Window
Magazine授予的Windows 先鋒獎(jiǎng)（僅7人獲獎(jiǎng)），直到今天，他依然是Windows GDI
程序設(shè)計(jì)首席技術(shù)作家。他出版過(guò)十幾本著作，其中包括Win32 API編程經(jīng)典《Windows程序設(shè)計(jì)》、《編碼》等。
 　歷屆圖靈獎(jiǎng)得主名單
 　◎ 1966 A. J. Perlis
 　高級(jí)編程技術(shù)和編譯器架構(gòu)
 　◎ 1967 Maurice V. Wilkes
 　設(shè)計(jì)出第一臺(tái)具有內(nèi)置存儲(chǔ)程序的計(jì)算機(jī)EDSAC
 　◎ 1968 Richard W. Hamming
 　數(shù)值方法、自動(dòng)編碼系統(tǒng)、錯(cuò)誤檢測(cè)及錯(cuò)誤校驗(yàn)碼
 　◎ 1969 Marvin Minsky
 　創(chuàng)造、推進(jìn)和提升人工智能
 　◎ 1970 J. H. Wilkinson
 　利用數(shù)值分析方法來(lái)促進(jìn)高速數(shù)字計(jì)算機(jī)的應(yīng)用
 　◎ 1971 John McCarthy
 　人工智能
 　◎ 1972 Edsger W. Dijkstra
 　編程語(yǔ)言
 　◎ 1973 Charles W. Bachman
 　數(shù)據(jù)庫(kù)
 　◎ 1974 Donald E. Knuth
 　算法分析和程序設(shè)計(jì)語(yǔ)言，“計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)”叢書
 　◎ 1975 Allen Newell和Herbert A. Simon
 　人工智能、人類認(rèn)知心理學(xué)和表處理
 　◎ 1976 Michael O. Rabin和Dana S. Scott
 　非確定性機(jī)器
 　◎ 1977 John Backus
 　可用的高級(jí)編程系統(tǒng)設(shè)計(jì)
 　◎ 1978 Robert W. Floyd
 　軟件編程的算法，語(yǔ)法分析理論、編程語(yǔ)言的語(yǔ)義和算法分析等多項(xiàng)計(jì)算機(jī)子學(xué)科的創(chuàng)立
 　◎ 1979 Kenneth E. Iverson
 　程序設(shè)計(jì)語(yǔ)言理論、交互系統(tǒng)及APL
 　◎ 1980 C. Antony R. Hoare
 　編程語(yǔ)言的定義和設(shè)計(jì)
 　◎ 1981 Edgar F. Codd
 　數(shù)據(jù)庫(kù)管理系統(tǒng)的理論和實(shí)踐
 　◎ 1982 Stephen A. Cook
 　奠定了NP完全性理論的基礎(chǔ)
 　◎ 1983 Dennis M. Ritchie和Kenneth L. Thompson
 　一般操作系統(tǒng)理論，對(duì)UNIX操作系統(tǒng)的推廣
 　◎ 1984 Niklaus E.Wirth
 　開發(fā)了EULER、ALGOL-W、MODULA和PASCAL等一系列嶄新的計(jì)算機(jī)語(yǔ)言
 　◎ 1985 Richard M. Karp
 　算法理論
 　◎ 1986 John E. Hopcroft和Robert E. Tarjan
 　在算法及數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和分析中取得了決定性成果
 　◎ 1987 John Cocke
 　編譯器的理論和設(shè)計(jì)，大系統(tǒng)體系結(jié)構(gòu)，精簡(jiǎn)指令集計(jì)算機(jī)的開發(fā)
 　◎ 1988 Ivan E. Sutherland
 　計(jì)算機(jī)圖形學(xué)
 　◎ 1989 William V. Kahan
 　數(shù)值分析
 　◎ 1990 Fernando J. Corbato
 　組織通用、大規(guī)模、分時(shí)和資源共享的兼容分時(shí)系統(tǒng)和Multics的開發(fā)
 　◎ 1991 Robin W.Milner
 　可計(jì)算函數(shù)邏輯（LCF）、ML和并行理論（CCS）
 　◎ 1992 Butler Lampson
 　分布式個(gè)人計(jì)算機(jī)系統(tǒng)
 　◎ 1993 Jurlis Hartmanis和Richard E. Stearns
 　奠定了計(jì)算復(fù)雜性理論的基礎(chǔ)
 　◎ 1994 Raj Reddy和Edward Feigenbaum
 　對(duì)大型人工智能系統(tǒng)的開拓性研究
 　◎ 1995 Manuel Blum
 　奠定了計(jì)算復(fù)雜性理論的基礎(chǔ)，密碼術(shù)及程序校驗(yàn)
 　◎ 1996 Amir Pnueli
 　在計(jì)算中引入時(shí)序邏輯、程序及系統(tǒng)檢驗(yàn)
 　◎ 1997 Douglas Engelbart
 　提出交互計(jì)算概念并創(chuàng)造出實(shí)現(xiàn)這一概念的重要技術(shù)
 　◎ 1998 James Gray
 　數(shù)據(jù)庫(kù)和事務(wù)處理
 　◎ 1999 Frederick P. Brooks, Jr.
 　計(jì)算機(jī)體系結(jié)構(gòu)、操作系統(tǒng)、軟件工程
 　◎ 2000 姚期智（Andrew Chi-Chih Yao）
 　計(jì)算理論方面的基礎(chǔ)性工作
 　◎ 2001 Ole-Johan Dahl和Kristen Nygaard
 　面向?qū)ο蟪绦蛟O(shè)計(jì)思想
 　◎ 2002 Ronald L. Rivest、Adi Shamir和Leonard M.
Adelman
 　公共密鑰算法（RSA）
 　◎ 2003 Alan Kay
 　發(fā)明第一個(gè)完全面向?qū)ο蟮膭?dòng)態(tài)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言Smalltalk
 　◎ 2004 Vinton G. Cerf和Robert E. Kahn
 　在互聯(lián)網(wǎng)方面的開創(chuàng)性工作
 　◎ 2005 Peter Naur
 　Algol 60語(yǔ)言
 　◎ 2006 Frances E. Allen
 　編譯器優(yōu)化理論和實(shí)踐（她是圖靈獎(jiǎng)第一位女性得主）
 　◎ 2007 Edmund M. Clarke、Allen Emerson和Joseph
Sifakis
 　將模型校驗(yàn)推廣成軟硬件工業(yè)中廣泛采用的高效校驗(yàn)技術(shù)
 　◎ 2008 Barbara Liskov
 　編程語(yǔ)言和系統(tǒng)設(shè)計(jì)的實(shí)踐與理論基礎(chǔ)
 　◎ 2009 Charles P. Thacker
 　第一臺(tái)現(xiàn)代個(gè)人計(jì)算機(jī)Alto之父
 　◎ 2010 Leslie L.Valiant
 　人工智能、自然語(yǔ)言處理和手寫識(shí)別等大量革新技術(shù)
 　◎ 2011 Judea Pearl
 　通過(guò)或然性積分和隨機(jī)推理對(duì)人工智能做出貢獻(xiàn)

書籍目錄

第一部分　基　　礎(chǔ)
第1章　這個(gè)墓穴埋葬著丟番圖　　
第2章　無(wú)理數(shù)和超越數(shù)　　
第3章　幾個(gè)世紀(jì)以來(lái)的發(fā)展　　
第二部分　可計(jì)算數(shù)
第4章　圖靈的學(xué)業(yè)　　
第5章　運(yùn)作的機(jī)器　　
第6章　加與乘　　
第7章　子程序　　
第8章　萬(wàn)物皆數(shù)字　　
第9章　通用機(jī)　　
第10章　計(jì)算機(jī)與可計(jì)算性　　
第11章　機(jī)器與人　　
第三部分　判定性問題
第12章　邏輯與可計(jì)算性　　
第13章　可計(jì)算函數(shù)　　
第14章　主要證明　　
第15章　λ演算　　
第16章　對(duì)連續(xù)統(tǒng)的設(shè)想　　
第四部分　題外話
第17章　萬(wàn)物皆是圖靈機(jī)？　　
第18章　長(zhǎng)眠的丟番圖　　
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   一種可行的方法是，依次計(jì)算每一項(xiàng)的第一位，直到某一項(xiàng)的第一位數(shù)字為0，然后，再依次計(jì)算每一項(xiàng)的第二位，直到某一項(xiàng)的前兩位數(shù)字均為0，依此類推。這顯然是一個(gè)很復(fù)雜的過(guò)程，特別是你不想機(jī)器在計(jì)算得到結(jié)果后再擦除結(jié)果的任意位時(shí)。 執(zhí)行正弦函數(shù)只是一個(gè)問題，輸入從哪里來(lái)呢？ 或許我們的直覺是讓機(jī)器的使用者以某種方式“鍵入”機(jī)器需要計(jì)算的角。這顯然是受現(xiàn)在的交互式計(jì)算機(jī)和屏幕計(jì)算器的啟發(fā)，但是為了接受這種形式的輸入，需要重新設(shè)計(jì)圖靈機(jī)。這比目前我們所做的工作量更大。第二種觀點(diǎn)是將函數(shù)的輸入“硬編碼”在機(jī)器內(nèi)部。例如，我們可以設(shè)計(jì)一臺(tái)專門計(jì)算37.85°的正弦值的機(jī)器。盡管這樣會(huì)把機(jī)器限制為只能求解某一個(gè)角度的正弦值，但是我們還是希望設(shè)計(jì)出的這種機(jī)器易于修改，從而可以計(jì)算其他角度的正弦值。 第三種方法是把角度編碼到紙帶上。機(jī)器讀取這個(gè)輸入，計(jì)算正弦值，然后再把結(jié)果打印到紙帶上。（我猜你喜歡這么做！我也是。） 第四種方法是讓機(jī)器自己產(chǎn)生輸入。例如，機(jī)器首先計(jì)算角度為0°的正弦值，然后計(jì)算角度為1°的正弦值，再計(jì)算角度為2°的正弦值，等等，并把每個(gè)結(jié)果都打印在紙帶上，最后會(huì)得到一張包含很多角度正弦值的“表”。這種方法要求機(jī)器計(jì)算得到的每個(gè)結(jié)果都只包含有限個(gè)數(shù)位。 第五種方法需要兩臺(tái)不同的機(jī)器。第一臺(tái)機(jī)器計(jì)算實(shí)數(shù)，第二臺(tái)計(jì)算該數(shù)的正弦值。我說(shuō)兩臺(tái)機(jī)器的時(shí)候，實(shí)際上是指可以實(shí)現(xiàn)兩臺(tái)機(jī)器邏輯的一臺(tái)機(jī)器。我們已經(jīng)遇到過(guò)以這種方式結(jié)合的機(jī)器。在第8節(jié)中（本書第166～167頁(yè)），圖靈把一臺(tái)判定機(jī)器D和通用機(jī)u結(jié)合起來(lái)，構(gòu)造成機(jī)器H來(lái)分析標(biāo)準(zhǔn)描述。這種做法的好處是，我們可以“插入”不同的第一臺(tái)機(jī)器來(lái)計(jì)算不同角度的正弦值。 這些做法都是有問題的。一個(gè)大問題是正弦函數(shù)的輸入和輸出都是實(shí)數(shù)（至少理論上是這樣的），而實(shí)數(shù)包含無(wú)限位。鍵入一個(gè)有無(wú)限位的數(shù)或?qū)⑦@樣的數(shù)編碼在紙帶上都是不可能的。 事實(shí)上，即使你將角度限制在簡(jiǎn)單的、可以表示成有限的十進(jìn)制數(shù)的范圍內(nèi)，正弦函數(shù)需要的也是弧度制的角度。180°對(duì)應(yīng)π個(gè)弧度，因此看上去很簡(jiǎn)單的10°其實(shí)是π／18個(gè)弧度——個(gè)包含無(wú)限個(gè)十進(jìn)制位數(shù)的超越數(shù)。

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    圖靈的秘密 PDF格式下載

---