有個(gè)古老而經(jīng)典的邏輯游戲：如果一個(gè)人說(shuō)“我正在說(shuō)謊”湾揽，那么他到底在不在說(shuō)謊呢苦酱？如果他不在說(shuō)謊酥泞，那么“我正在說(shuō)謊”這句話(huà)就是真的伍宦；如果他在說(shuō)謊芽死，那么“我正在說(shuō)謊”這句話(huà)就是假的。無(wú)論從哪個(gè)方向推演次洼，得到的都是自相矛盾的結(jié)論关贵，我們無(wú)從判定他在不在說(shuō)謊。

這就是公元前4世紀(jì)卖毁，由哲學(xué)家歐布里德（Eubulides）提出的著名的說(shuō)謊者悖論揖曾。
與之類(lèi)似的，還有伯特蘭·羅素（Bertrand Russell）在1901年提出的羅素悖論亥啦，它的通俗化版本是流傳更廣的理發(fā)師悖論：如果一位理發(fā)師只給不為自己理發(fā)的人理發(fā)炭剪，那他給不給自己理發(fā)呢？

羅素悖論直接動(dòng)搖了整個(gè)數(shù)學(xué)大廈的根基——集合論翔脱。為使命題合理奴拦，當(dāng)那位理發(fā)師圈定服務(wù)對(duì)象的范圍時(shí)，必須把自己排除在外届吁。這也就意味著错妖，沒(méi)有包羅萬(wàn)象的集合——至少它不能輕易包含自己。

這些悖論都源自“罪惡”的自指——當(dāng)一套理論開(kāi)始描述自身疚沐，就難免要出現(xiàn)悖論暂氯。
即使再不情愿，人們也不得不承認(rèn)數(shù)學(xué)是不完美的亮蛔，至少它沒(méi)有自圓其說(shuō)的能力痴施。
盡管如此，仍有數(shù)學(xué)家想在限定的范圍內(nèi)負(fù)隅頑抗，他們找到一個(gè)完備的系統(tǒng)^[1]辣吃，尋求能夠判定命題真假的通用算法锉矢。這就是德國(guó)數(shù)學(xué)家大衛(wèi)·希爾伯特（David Hilbert）和威廉·阿克曼（Wilhelm Ackermann）在1928年提出的判定問(wèn)題（Entscheidungsproblem/decision problem）。

只可惜沒(méi)過(guò)幾年齿尽，這種可能性也被否定了沽损。

1936年，兩位年輕的數(shù)學(xué)家分別用不同的方法給出了判定問(wèn)題的解答循头。一位是來(lái)自美國(guó)的阿隆佐·邱奇（Alonzo Church）绵估，他引入了一種叫λ演算的方法，并最終證明沒(méi)有任何通用算法可以判定任意兩個(gè)λ表達(dá)式是否相等卡骂；另一位就是來(lái)自英國(guó)的艾倫·圖靈（Alan Turing）国裳，和枯燥的數(shù)學(xué)推理不同，他使用了一種更有趣全跨、更形象的模型缝左，邱奇給了它一個(gè)響亮的名字——圖靈機(jī)（Turing machine）。

圖靈早年經(jīng)歷

艾倫·麥席森·圖靈（Alan Mathison Turing）浓若，1912-1954渺杉，英國(guó)數(shù)學(xué)家、計(jì)算機(jī)學(xué)家挪钓、邏輯學(xué)家是越、密碼學(xué)家、哲學(xué)家碌上、理論生物學(xué)家倚评。（圖片來(lái)自維基百科）

1912年6月23日，圖靈出生于英國(guó)帕丁頓一個(gè)沒(méi)落的貴族家庭馏予，由于父母常年在印度工作天梧，他和年長(zhǎng)4歲的哥哥一起被寄養(yǎng)在一對(duì)軍人夫婦的家中。圖靈的童年十分平凡霞丧，和普通男孩一樣呢岗，經(jīng)歷過(guò)調(diào)皮搗蛋和孤僻寡言的的階段，他天性聰敏卻有著嚴(yán)重偏科的傾向蚯妇，許多教過(guò)他的老師對(duì)他的評(píng)價(jià)并不高敷燎。

10歲那年，圖靈接觸到一本改變了他一生的童書(shū)——《兒童必讀的自然奇跡》箩言，這本科普讀物打開(kāi)了一扇新世界的大門(mén)硬贯，圖靈發(fā)現(xiàn)門(mén)的那邊堆滿(mǎn)了一種對(duì)他來(lái)說(shuō)最有吸引力的知識(shí)——科學(xué)。他開(kāi)始瘋狂地尋找和自學(xué)有關(guān)科學(xué)的一切知識(shí)陨收，并用日用品做一些簡(jiǎn)單的化學(xué)實(shí)驗(yàn)饭豹。他很快意識(shí)到手頭的科普讀物過(guò)于淺顯鸵赖，妨礙了他了解事物背后更深層的原理。他甚至寫(xiě)信給父母討要真正的科學(xué)書(shū)籍拄衰，而不是兒童百科它褪。他寫(xiě)到：“《兒童必讀的自然奇跡》中說(shuō)，二氧化碳在血液里變成蘇打翘悉，又在肺里變回二氧化碳茫打。如果可以，請(qǐng)把蘇打的化學(xué)名稱(chēng)妖混，最好是化學(xué)式寄給我老赤，好讓我看看這個(gè)過(guò)程到底是怎么進(jìn)行的≈剖校”13歲時(shí)抬旺，他已經(jīng)對(duì)酒精等有機(jī)物的分子式和結(jié)構(gòu)式了如指掌。

1926年祥楣，聰明好學(xué)而又對(duì)科學(xué)知識(shí)近乎偏執(zhí)的圖靈考入了舍爾伯尼中學(xué)开财。開(kāi)學(xué)當(dāng)天正趕上英國(guó)大罷工，公共交通癱瘓误褪，圖靈竟用兩天時(shí)間靠自行車(chē)征服了到學(xué)校的60英里（近100公里）路程责鳍。這不是一次沖動(dòng)之舉，而是精心策劃之下的行動(dòng)振坚，當(dāng)?shù)貓?bào)紙還專(zhuān)門(mén)刊載了這一令人吃驚的事跡薇搁。

圖靈很有才斋扰，也很有執(zhí)行力渡八，卻在與人溝通上遇到了大麻煩。知子莫若母传货，圖靈的母親在為他尋找合適的中學(xué)時(shí)就一度擔(dān)心他沒(méi)法適應(yīng)公學(xué)^[2]生活屎鳍，成長(zhǎng)為高智商、低情商的怪人问裕。在講究教條與制度而不重視理性和科學(xué)的舍爾伯尼逮壁，圖靈顯得格格不入，被多數(shù)同學(xué)孤立和欺負(fù)粮宛，連老師也經(jīng)常拿他的小習(xí)慣開(kāi)涮窥淆，這對(duì)一個(gè)心智尚未成熟的男孩來(lái)說(shuō)非常可怕巍杈。他們的校長(zhǎng)倒看得十分透徹忧饭，曾警告圖靈的父母：“我希望他不要兩頭都落空。如果他要留在公學(xué)筷畦，就必須以好好接受我們的教育為目標(biāo)词裤；如果他只是想做科學(xué)家刺洒，那么呆在公學(xué)就是浪費(fèi)時(shí)間『鹕埃”

舍爾伯尼是當(dāng)時(shí)英國(guó)社會(huì)的一個(gè)縮影逆航，中學(xué)的經(jīng)歷也預(yù)示著圖靈不被理解的一生。

1931～1934年渔肩，成年后的圖靈在劍橋大學(xué)國(guó)王學(xué)院攻讀數(shù)學(xué)專(zhuān)業(yè)因俐。盡管這里的制度依舊古板，像個(gè)放大版的舍爾伯尼周偎，圖靈依舊孤僻女揭，但接觸到了世界頂級(jí)的數(shù)學(xué)家和一流的學(xué)術(shù)專(zhuān)著，他可以更專(zhuān)注于自己喜歡的領(lǐng)域栏饮，并包攬了許多數(shù)學(xué)方面的獎(jiǎng)項(xiàng)吧兔。畢業(yè)后，圖靈以?xún)?yōu)異的成績(jī)成為國(guó)王學(xué)院研究員袍嬉。他在希爾伯特的問(wèn)題上花費(fèi)了整整一年的時(shí)間境蔼，最終在1936年的《倫敦?cái)?shù)學(xué)協(xié)會(huì)會(huì)刊》上發(fā)表了那篇改變世界的論文——《論可計(jì)算數(shù)及其在判定問(wèn)題中的應(yīng)用》，提出了使其成為“計(jì)算機(jī)科學(xué)之父”的圖靈機(jī)伺通。

圖靈機(jī)

工作原理

圖靈機(jī)是圖靈受打字機(jī)的啟發(fā)而假想出來(lái)的一種抽象機(jī)器箍土，其處理對(duì)象是一條無(wú)限長(zhǎng)的一維紙帶。紙帶被劃分為一個(gè)個(gè)大小相等的小方格罐监，每個(gè)小方格可以存放一個(gè)符號(hào)（可以是數(shù)字吴藻、字母或其他符號(hào)）。有個(gè)貼近紙帶的讀寫(xiě)頭弓柱，可以對(duì)單個(gè)小方格進(jìn)行讀取沟堡、擦除和打印操作。為了讓讀寫(xiě)頭能訪(fǎng)問(wèn)到紙帶上的所有小方格矢空，可以固定紙帶航罗，讓讀寫(xiě)頭沿著紙帶左右移動(dòng)，每次移動(dòng)一格屁药，或者固定讀寫(xiě)頭粥血，讓紙帶左右移動(dòng)——后一種方式類(lèi)似當(dāng)時(shí)穿孔帶以及后來(lái)磁帶和磁盤(pán)的做法，但在純理論討論時(shí)為了方便說(shuō)明酿箭，我們通常選用前一種方式复亏。

圖靈機(jī)紙帶示意圖

那么讀寫(xiě)頭該如何移動(dòng)，移動(dòng)之前或移動(dòng)之后又該作何操作呢缭嫡？這取決于機(jī)器當(dāng)前的狀態(tài)缔御，以及讀寫(xiě)頭當(dāng)前所指小方格中的內(nèi)容，機(jī)器中有著一張應(yīng)對(duì)各種情況的策略表械巡。這就好比有一只小貓刹淌，你往它碗里放些食物饶氏，它會(huì)根據(jù)自己餓不餓以及食物的類(lèi)別判斷吃還是不吃，我們可以大體列出一張策略表：

小貓進(jìn)食策略表

在這個(gè)例子中有勾，小貓就好比圖靈機(jī)疹启，碗就是紙帶上的小方格，食物就是小方格中的符號(hào)蔼卡。當(dāng)然這只是一個(gè)簡(jiǎn)化的類(lèi)比喊崖，也有很多不挑食的小貓會(huì)吃白米飯，或者貪食的小貓即使吃飽了看見(jiàn)魚(yú)還是會(huì)繼續(xù)吃雇逞。在理想情況下荤懂，當(dāng)我們提供一排足夠多的碗，并在碗中放置更多種類(lèi)的食物和玩具塘砸，貓?jiān)谕肱c碗間來(lái)回走動(dòng)节仿，就更像一臺(tái)圖靈機(jī)了。

為了更精確地說(shuō)明掉蔬，我們構(gòu)造一臺(tái)簡(jiǎn)單的圖靈機(jī)廊宪，實(shí)現(xiàn)對(duì)紙帶上所有3位二進(jìn)制數(shù)的+1操作（超過(guò)3位的進(jìn)位將被丟棄），相鄰兩個(gè)二進(jìn)制數(shù)之間通過(guò)一個(gè)空的小方格隔開(kāi)女轿，形如下圖所示箭启，讀寫(xiě)頭從最右側(cè)二進(jìn)制數(shù)的最低位開(kāi)始掃描，遇到連續(xù)2個(gè)空方格時(shí)認(rèn)為已處理完所有數(shù)蛉迹，機(jī)器停機(jī)傅寡。

圖靈機(jī)示例紙帶

策略表如下表所示，其中E表示擦除北救、P表示打印荐操、L表示左移。

圖靈機(jī)示例策略表

該圖靈機(jī)有3種工作狀態(tài)：

1. S₁是+1狀態(tài)扭倾，也是機(jī)器的初始狀態(tài)淀零。如果讀寫(xiě)頭遇到的是0，則直接將0改為1即完成了+1任務(wù)膛壹，左移一格后進(jìn)入狀態(tài)S₂；如果遇到的是1唉堪，則將1改為0模聋，由于需要進(jìn)位，即對(duì)下一位+1唠亚，左移一格后仍留在狀態(tài)S₁链方；如果遇到的是一個(gè)空方格，即使當(dāng)前需要進(jìn)位灶搜，也不做處理（將進(jìn)位丟棄）祟蚀，左移一格后進(jìn)入狀態(tài)S₃工窍。
2. S₂是左移狀態(tài)，此時(shí)已實(shí)現(xiàn)當(dāng)前二進(jìn)制數(shù)的+1前酿，需要將讀寫(xiě)頭移到下一個(gè)數(shù)的最低位患雏。如果遇到0或1，說(shuō)明讀寫(xiě)頭還在當(dāng)前二進(jìn)制數(shù)上罢维，繼續(xù)左移淹仑；如果遇到空方格，后面等著它的可能是下一個(gè)二進(jìn)制數(shù)肺孵，也可能是永無(wú)止境的空方格匀借，左移一格之后進(jìn)入狀態(tài)S₃。
3. S₃是判斷狀態(tài)平窘，根據(jù)情況判斷是否還有二進(jìn)制數(shù)要處理吓肋。如果讀寫(xiě)頭遇到的是0或1，說(shuō)明當(dāng)前位置是一個(gè)新的二進(jìn)數(shù)的最低位瑰艘，直接交給S₁處理蓬坡；如果遇到的仍是空方格，說(shuō)明后續(xù)不再有數(shù)據(jù)磅叛，停機(jī)屑咳。

根據(jù)以上策略，該圖靈機(jī)處理紙帶的過(guò)程為：

如法炮制弊琴，我們可以設(shè)計(jì)出具有各種功能的圖靈機(jī)兆龙，而策略表的制定則類(lèi)似于編程。圖靈想到敲董，如果把策略表中的信息以統(tǒng)一的格式寫(xiě)成符號(hào)串（比如上表可以表達(dá)成S1/0/EP1L/S2 S1/1/EP0L/S1 S1//L/S3 ……）紫皇，然后放在紙帶的頭部，再設(shè)計(jì)一臺(tái)能在運(yùn)行伊始時(shí)從紙帶上讀取這些策略的圖靈機(jī)腋寨，那么針對(duì)不同的任務(wù)聪铺，就不需要設(shè)計(jì)不同的圖靈機(jī)，而只需改變紙帶上的策略即可萄窜。這種能靠紙帶定制策略的圖靈機(jī)铃剔，稱(chēng)為通用圖靈機(jī)UTM（universal Turing machine）。

不單是策略表查刻，其實(shí)用于描述圖靈機(jī)的所有信息（包括所使用的符號(hào)键兜、初始狀態(tài)等）都可以表達(dá)成紙帶上的符號(hào)串。這就意味著穗泵，一臺(tái)圖靈機(jī)可以成為另一臺(tái)圖靈機(jī)的輸入普气。

判定問(wèn)題的解答

在試想一下，在有些情況下佃延，一臺(tái)圖靈機(jī)如果長(zhǎng)時(shí)間沒(méi)有輸出結(jié)果现诀，那么它很可能陷入了死循環(huán)或永無(wú)止境的計(jì)算中夷磕。這是我們不愿看到的，因?yàn)闄C(jī)器可能運(yùn)行1分鐘后停機(jī)仔沿，也可能運(yùn)行10天半個(gè)月甚至幾十年才停機(jī)坐桩，亦或者永遠(yuǎn)也不會(huì)停機(jī)，這個(gè)很難靠人為判斷于未。假設(shè)我們構(gòu)建出一臺(tái)圖靈機(jī)H撕攒，它接收其他圖靈機(jī)及其輸入信息作為輸入，并能夠判定其是否會(huì)停機(jī)烘浦，就解決了上面的煩惱——構(gòu)建這樣的機(jī)器難度雖大抖坪，但理論上是可行的。

這就是著名的停機(jī)問(wèn)題（halting problem）闷叉。

H所處理的擦俐，本質(zhì)上正是一種判定問(wèn)題：某臺(tái)圖靈機(jī)在某輸入上是否會(huì)停機(jī)。只要找到一臺(tái)H判定不了的機(jī)器握侧，希爾伯特的美夢(mèng)就破滅了蚯瞧。

令H表現(xiàn)如下圖所示，如果其判定對(duì)象會(huì)停機(jī)則輸出1品擎，反之輸出0埋合。

圖靈機(jī)H運(yùn)行流程

我們?cè)贅?gòu)建一臺(tái)圖靈機(jī)G，其運(yùn)行流程如下圖所示萄传。如果H輸出1甚颂，說(shuō)明G會(huì)停機(jī)，但事實(shí)上它將陷入循環(huán)秀菱；如果H輸出0振诬，說(shuō)明G不會(huì)停機(jī)，但事實(shí)上它將停機(jī)衍菱。

圖靈機(jī)G運(yùn)行流程

悖論已經(jīng)出現(xiàn)赶么，H無(wú)法對(duì)G的停機(jī)問(wèn)題進(jìn)行判定。又一次歸因于尷尬的自指：當(dāng)一個(gè)系統(tǒng)強(qiáng)大到一定程度時(shí)脊串，終究會(huì)遇到無(wú)法處理自己的窘境辫呻。

因此，不存在一臺(tái)圖靈機(jī)洪规，可以判定任意圖靈機(jī)是否會(huì)停機(jī)印屁。圖靈機(jī)不是萬(wàn)能的，判定問(wèn)題的答案也是否定的斩例。而這個(gè)看似有點(diǎn)耍賴(lài)的證明方式，有著圖靈長(zhǎng)達(dá)36頁(yè)的數(shù)學(xué)論證支撐从橘。

深遠(yuǎn)的意義

圖靈的工作不僅回答了希爾伯特的問(wèn)題念赶，更參透了數(shù)學(xué)和計(jì)算機(jī)的本質(zhì)關(guān)系——計(jì)算機(jī)是為解決數(shù)學(xué)問(wèn)題而誕生的础钠，卻又基于數(shù)學(xué)，因而數(shù)學(xué)自身的極限也便框定了計(jì)算機(jī)的能力范圍叉谜。

圖靈雖然證明了沒(méi)有任何機(jī)器可以解決所有數(shù)學(xué)問(wèn)題旗吁，卻也證明了機(jī)器可以完成所有人類(lèi)能完成的計(jì)算工作，從如今的應(yīng)用看來(lái)停局，后一個(gè)結(jié)論的意義重大得多很钓。

從圖靈開(kāi)始，計(jì)算機(jī)有了真正堅(jiān)實(shí)的理論基礎(chǔ)董栽，更多人開(kāi)始投身計(jì)算機(jī)的理論研究码倦，而不僅是嘗試構(gòu)建一臺(tái)機(jī)器。從如今的應(yīng)用來(lái)看锭碳，圖靈機(jī)之于計(jì)算機(jī)領(lǐng)域的價(jià)值遠(yuǎn)高于數(shù)學(xué)領(lǐng)域袁稽，畢竟判定問(wèn)題還有λ演算和許多其他解答，但計(jì)算機(jī)的原始公式擒抛，只有圖靈機(jī)這一個(gè)推汽。

如今的所有通用計(jì)算機(jī)都是圖靈機(jī)的一種實(shí)現(xiàn)，兩者的能力是等價(jià)的歧沪。當(dāng)一個(gè)計(jì)算系統(tǒng)可以模擬任意圖靈機(jī)（或者說(shuō)通用圖靈機(jī)）時(shí)歹撒，我們稱(chēng)其是圖靈完備的（Turing complete）；當(dāng)一個(gè)圖靈完備的系統(tǒng)可以被圖靈機(jī)模擬時(shí)诊胞，我們稱(chēng)其是圖靈等效的（Turing equivalent）暖夭。圖靈完備和圖靈等效成為衡量計(jì)算機(jī)和編程語(yǔ)言能力的基礎(chǔ)指標(biāo)，如今幾乎所有的編程語(yǔ)言也都是圖靈完備的厢钧，這意味著它們可以相互取代鳞尔，一款語(yǔ)言能寫(xiě)出的程序用另一款也照樣可以實(shí)現(xiàn)。

后話(huà)

論文正式發(fā)表之前早直，圖靈只身前往美國(guó)普林斯頓寥假，在那里找到了領(lǐng)先一步發(fā)表成果的邱奇，并師從他繼續(xù)深造霞扬。1937年糕韧，圖靈嗅到了納粹德國(guó)引戰(zhàn)的可能，開(kāi)始把業(yè)余時(shí)間花在密碼學(xué)的研究上喻圃。1938年萤彩，圖靈在取得博士學(xué)位后返回了正在緊張備戰(zhàn)的英國(guó)，不多久斧拍，他便參與到政府的密碼破譯^[3]項(xiàng)目中雀扶，和全國(guó)各地頂尖的數(shù)學(xué)家們一起，在白金漢郡的布萊切利公館（Bletchley Park）中深居簡(jiǎn)出，左右世界戰(zhàn)爭(zhēng)的格局愚墓。

二戰(zhàn)時(shí)期予权，各國(guó)已經(jīng)使用無(wú)線(xiàn)電進(jìn)行作戰(zhàn)指揮，由于信號(hào)可以輕易被敵國(guó)接收浪册，需要對(duì)無(wú)線(xiàn)電內(nèi)容進(jìn)行加密扫腺，比如將“ABCD”改成“BCDE”發(fā)出去，當(dāng)然軍用的加密方式不會(huì)如此簡(jiǎn)單村象。當(dāng)時(shí)的德國(guó)使用一種叫謎機(jī)（Enigma machine）的加密機(jī)器笆环，按下某個(gè)字母的按鍵，其加密后對(duì)應(yīng)的字母小燈就會(huì)亮起。內(nèi)部的轉(zhuǎn)輪和接插線(xiàn)板將這種對(duì)應(yīng)關(guān)系隨意打亂，每按一次按鍵萧豆，轉(zhuǎn)輪就會(huì)轉(zhuǎn)動(dòng)一次，組合成新的對(duì)應(yīng)關(guān)系习绢，比如第一次按下A，D燈亮起蝙昙，再按一次A闪萄，亮起的可能是Z燈，毫無(wú)規(guī)律可循奇颠。更棘手的是败去，德軍幾乎每天都會(huì)變更其中的接線(xiàn)。

3轉(zhuǎn)輪謎機(jī)（圖片來(lái)自維基百科）

解密的方式是窮舉烈拒，即遍歷所有可能的對(duì)應(yīng)關(guān)系圆裕，直到找出有意義的關(guān)鍵詞，而這恰恰是機(jī)器最擅長(zhǎng)的事荆几。英國(guó)的同盟國(guó)波蘭在戰(zhàn)前就成功研制了破解謎機(jī)的炸彈機(jī)（bomba）吓妆，可惜德國(guó)在1938年年底將謎機(jī)上的轉(zhuǎn)輪從3個(gè)增加到了5個(gè)，解密的復(fù)雜度呈爆炸式增長(zhǎng)吨铸，針對(duì)3轉(zhuǎn)輪謎機(jī)設(shè)計(jì)的炸彈機(jī)還未在二戰(zhàn)發(fā)揮價(jià)值就已經(jīng)宣告報(bào)廢行拢。解決這個(gè)難題的關(guān)鍵人物正是圖靈，新建的炸彈機(jī)（bombe）成功破解了5轉(zhuǎn)輪謎機(jī)诞吱。其難度之大舟奠，大到英國(guó)首次利用破解的信息破壞德軍行動(dòng)時(shí)，德國(guó)的密碼專(zhuān)家首先排除了謎機(jī)被破解的可能性房维。

圖靈炸彈機(jī)（圖片來(lái)自維基百科）

隨后沼瘫，對(duì)密碼學(xué)有著深刻認(rèn)識(shí)的圖靈還探索出一種高效的解密算法，人稱(chēng)圖靈方法（Turingery）咙俩，該算法成為布萊切利破解德國(guó)密碼的核心理論耿戚。

布萊切利的工作是圖靈在短暫的一生中，為人類(lèi)所做的第二項(xiàng)偉大貢獻(xiàn)。他的成果使戰(zhàn)爭(zhēng)至少提前2年結(jié)束溅话，挽救了至少1400萬(wàn)人的生命晓锻。前英國(guó)首相溫斯頓·丘吉爾曾表示歌焦，二戰(zhàn)的勝利最該感謝的人就是圖靈飞几。

戰(zhàn)后，圖靈進(jìn)入國(guó)家物理研究所独撇，并設(shè)計(jì)了屬于最早一批電子計(jì)算機(jī)之一自動(dòng)計(jì)算機(jī)ACE（Automatic Computing Engine）屑墨，首次實(shí)現(xiàn)了他心目中的通用圖靈機(jī)。1950年3月10日纷铣，ACE的簡(jiǎn)化版Pilot ACE開(kāi)始運(yùn)行卵史，完整的ACE直到圖靈去世之后才建成。

Pilot ACE（圖片來(lái)自維基百科）

1948年搜立，圖靈成為曼徹斯特大學(xué)數(shù)學(xué)系講師以躯，并于次年擔(dān)任學(xué)校計(jì)算機(jī)實(shí)驗(yàn)室的副主任，負(fù)責(zé)計(jì)算機(jī)軟件的研究啄踊。他還成為計(jì)算機(jī)企業(yè)的顧問(wèn)忧设，幫助其研發(fā)商用電子計(jì)算機(jī)。1951年颠通，英國(guó)皇家學(xué)會(huì)將圖靈吸納為會(huì)員址晕。

這些年間，圖靈的主要智慧仍留給了數(shù)學(xué)和計(jì)算機(jī)的理論研究顿锰。1950年谨垃，第二篇影響世界的論文《計(jì)算機(jī)與智能》問(wèn)世，在那個(gè)電子計(jì)算機(jī)才剛剛起步的年代硼控，高瞻遠(yuǎn)矚的圖靈用一個(gè)問(wèn)題就叩開(kāi)了人工智能的大門(mén)：“機(jī)器會(huì)思考嗎刘陶？”文中提出了著名的圖靈測(cè)試（Turing test）：讓一臺(tái)機(jī)器躲在擋板后回答測(cè)試人員的提問(wèn)，看測(cè)試人員能否判斷自己面對(duì)的是機(jī)器還是真人牢撼。能否通過(guò)圖靈測(cè)試匙隔，是衡量機(jī)器智能程度的重要指標(biāo)。這位“人工智能之父”過(guò)于樂(lè)觀地預(yù)言：到2000年浪默，計(jì)算機(jī)應(yīng)該能“騙過(guò)”30%的測(cè)試人員牡直。

圖靈機(jī)、炸彈機(jī)纳决、人工智能……圖靈獻(xiàn)給世界太多偉大的作品碰逸，卻沒(méi)能在生前得到應(yīng)有的名譽(yù)乃至起碼的認(rèn)可。人們始終覺(jué)得他是個(gè)難以親近的怪人阔加，對(duì)其二戰(zhàn)時(shí)期涉密的功績(jī)更是一無(wú)所知饵史。1952年，他因同性戀的罪名被起訴，在坐牢和化學(xué)閹割之間胳喷，他無(wú)奈選擇了后者湃番，旁人的偏見(jiàn)和藥物的副作用使他承受著精神和肉體的雙重痛苦。1954年6月7日晚上吭露，他躺在家里因氰化物中毒離開(kāi)了人世吠撮，床頭放著一個(gè)咬過(guò)的蘋(píng)果，還有16天就是他42歲的生日讲竿。尸檢的結(jié)果認(rèn)定圖靈是通過(guò)毒蘋(píng)果自殺的泥兰，卻沒(méi)有對(duì)這個(gè)蘋(píng)果做氫化物檢測(cè)，他的母親和哥哥卻堅(jiān)持認(rèn)為這是一場(chǎng)化學(xué)實(shí)驗(yàn)導(dǎo)致的意外题禀，而真相只有圖靈自知鞋诗。

2009年，超過(guò)3萬(wàn)人在線(xiàn)請(qǐng)?jiān)笧閳D靈平反迈嘹，英國(guó)首相戈登·布朗代表政府公開(kāi)道歉削彬。2013年，英國(guó)女王伊麗莎白二世正式頒發(fā)皇家赦免秀仲，圖靈終于得到了遲來(lái)的公道融痛。
1966年，美國(guó)計(jì)算機(jī)協(xié)會(huì)ACM（Association for Computing Machinery）設(shè)立計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)項(xiàng)啄育，命名為圖靈獎(jiǎng)酌心。圖靈獎(jiǎng)素有“計(jì)算機(jī)界的諾貝爾獎(jiǎng)”之稱(chēng)，圖靈的名字當(dāng)之無(wú)愧挑豌。

2019年安券，英國(guó)的中央銀行——英格蘭銀行宣布，圖靈的肖像將出現(xiàn)在新版的50英鎊紙幣上氓英，以此紀(jì)念這位改變了國(guó)家乃至整個(gè)世界命運(yùn)的偉人侯勉。

參考文獻(xiàn)

• 本特利 P J. 計(jì)算機(jī)：一部歷史[M]. 顧紋天, 譯. 北京: 電子工業(yè)出版社, 2015.
• 張楨勝. 圖靈的“數(shù)字宇宙”：邏輯原理與哲學(xué)意蘊(yùn)[D]. 昆明: 云南師范大學(xué), 2018.
• 方弦. 計(jì)算的極限（零）：邏輯與圖靈機(jī)[EB/OL].
• Wikipedia. Entscheidungsproblem[EB/OL].
• Wikipedia. Alan Turing[EB/OL].
• 霍奇斯 A. 艾倫·圖靈傳：如謎的解謎者[M]. 孫天齊, 譯. 長(zhǎng)沙: 湖南科學(xué)技術(shù)出版社, 2012.
• Hodges A. Alan Turing: The Enigma[M]. Princeton: Princeton University Press, 2014.
• Turing A M. On Computable Numbers, with an Application to the Entscheidungsproblem[J]. Proceedings of the London Mathematical Society, 1936, 43(43):13-115.
• Wikipedia. Halting problem[EB/OL].
• Wikipedia. Turing completeness[EB/OL].

1. 邏輯學(xué)中的一階謂詞演算是完備的，感興趣的讀者可以深入了解铝阐。 ?

2. 公學(xué)是英國(guó)的公共學(xué)校址貌，是面向富裕家庭的精英學(xué)校，只招收中產(chǎn)和貴族階級(jí)的孩子徘键。 ?

3. 本書(shū)所提及的二戰(zhàn)期間的密碼（cipher）與現(xiàn)今我們登陸賬號(hào)所用的密碼（password）不是同一概念练对，前者是對(duì)明文按照一定規(guī)則轉(zhuǎn)換后生成的密文，后者則是通行口令吹害，切勿混淆螟凭。 ?