此文轉(zhuǎn)載览祖，結(jié)合《模仿游戲》觀看效果更佳。
作者：宋方敏（南京大學(xué)，計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室隐孽，南京，210093）
引言
美國 TIME 雜志在 1999 年出版專卷介紹 20 世紀(jì) 100 個最偉大的智者株扛，在計算機(jī)科學(xué)領(lǐng)域中英國數(shù)理邏輯學(xué)家 Alan Turing 列入其中（數(shù)學(xué)有 Kurt G?del护姆，物理有 Albert Einstein, 后來 Einstein 列為 The person of the 20th century）。由于 Turing 對于人類的極出貢獻(xiàn)先较，他成為20世紀(jì)最有影響科學(xué)家和思想家之一携冤。本文介紹 Alan Turing 的生平和主要工作，以此紀(jì)念計算機(jī)科學(xué)的奠基人闲勺。
Turing評說
在數(shù)理邏輯的神秘王國里曾棕，一個天才提出了質(zhì)疑和構(gòu)想——設(shè)計一臺能夠模擬人類思維演段的機(jī)器—— 一個天方夜譚？
如果 Turing 所做的一切只是回答了神秘的數(shù)理邏輯領(lǐng)域里的一個令人苦惱的問題的話菜循，那么就不會有什么理由讓外行人記住他翘地。但正相反，Turing 使用他那給整個世界帶來巨大影響的方法，向世人展示——“一個封閉的邏輯系統(tǒng)里的某些命題是不能在本系統(tǒng)內(nèi)得到證明的”——這一曾令 Kurt G?del 名聲大振的推論子眶。這個年輕而前衛(wèi)的劍橋大學(xué)學(xué)生所做的就是夢想著造一臺假想的機(jī)器——一臺簡潔而精巧瀑凝，打字機(jī)模樣的，可以掃描或讀入那些寫在（理論上）無限長的磁帶上的指令的機(jī)器臭杰。隨著掃描器在磁帶上移來移去——機(jī)器依據(jù)指令按序執(zhí)行或跳轉(zhuǎn)粤咪，從而，Turing 提出渴杆，機(jī)器執(zhí)行過程的輸出可以重現(xiàn)人類的思維寥枝。
這種受靈感啟發(fā)的思想實(shí)驗(yàn)中的機(jī)器，連同 Turing 的另一個想法磁奖，很快獲得了一個名字：Turing 機(jī)囊拜。因?yàn)榇艓系闹噶羁梢钥刂茩C(jī)器的行為，所以通過更換相應(yīng)的指令就可以讓這臺機(jī)器去完成所有這樣的機(jī)器所能完成的任務(wù)比搭。換句話說冠跷，通過掃描不同的磁帶，同樣的一臺機(jī)器既可以算題身诺，又能下棋蜜托，還會做其它的相對更自然的任一件事。于是霉赡，他的機(jī)器又贏得了一個更好聽的新名字：通用 Turing 機(jī)橄务。
隨著指令的運(yùn)行，這樣一臺十分原始的硬件組合可以完成令人驚訝的各種任務(wù)穴亏。這樣的想法聽起來可能嗎蜂挪？在 1937 年顯然是無法想象的。那一年嗓化，Turing 的學(xué)術(shù)論文 On Computable Numbers, with an Application to the Entscheidungsproblem發(fā)表在倫敦數(shù)學(xué)會學(xué)報上棠涮。但是 Turing 的想法被很少的讀者所理解,他們認(rèn)為這些構(gòu)思在理論上十分有趣和誘人，卻沒有人認(rèn)識到 Turing 的機(jī)器為后來的電子數(shù)字計算機(jī)勾畫出了藍(lán)圖刺覆。
由于今天的計算機(jī)繼承了如此之多的想法和技術(shù)上的創(chuàng)新严肪，以至于我們無論將發(fā)明計算機(jī)的功勞歸在誰的頭上都是魯莽的。但事實(shí)是隅津，每敲擊一次鍵盤或打開一扇窗口诬垂，抑或是運(yùn)行一個字處理程序都是在一臺 Turing 機(jī)的化身上工作。
Turing 1937 年的論文改變了他的一生伦仍，讓一個靦腆而脆弱的男人更多地被卷入到塵世中去结窘，最終走向一個悲劇式的結(jié)局。
Alan Mathison Turing 1912年生于倫敦充蓝，是這個家庭的第二個孩子隧枫。他的父親是印度 British Civil Service 的成員喉磁，但他的母親認(rèn)為這樣的環(huán)境不利于孩子的成長。于是 Alan 和哥哥在英國的一個領(lǐng)養(yǎng)家庭中度過了他們的童年,除了偶爾回家看看官脓，大部分時間和父母分開协怒。也許就是這其間 Turing 的孤獨(dú)感誘發(fā)了他一生對人腦機(jī)理的興趣——當(dāng)上帝賜予的這個世界顯得貧瘠和令人不滿的時候，怎樣創(chuàng)造一個屬于自己的世界呢卑笨？
Turing 從 13 歲起就讀于 Dorset 的 Sherbourne 小學(xué)孕暇，在那里，他已經(jīng)顯示出了自己的數(shù)學(xué)天賦赤兴，盡管他的卷子總是因?yàn)殡s亂無章而被批評妖滔。Turing 在讀小學(xué)的時候就發(fā)現(xiàn)了自己的同性戀傾向，并愛上了學(xué)校里的另一個小男孩——雖然 Turing 從未告訴過任何人——后來這個小男孩猝死于結(jié)核桶良。這一事件粉碎了 Turing 的宗教信仰座舍，使他成為了一個無神論者，并讓他堅信所有的現(xiàn)象都有一個客觀的解釋陨帆。機(jī)器沒有思想曲秉，而大腦中也沒有靈魂。那么疲牵，思維和意識又是從何而來呢承二？
在兩次向劍橋大學(xué) Trinity College 這所令全世界的數(shù)學(xué)家們神往的學(xué)府申請資助失敗之后，Turing 終于獲得了 King’s College 的資助瑰步。在諸如 John Maynard Keynes 以及 E.M. Forster 這些名家泰斗們的指引下矢洲，King’s College 為 Turing 提供了充分自由與寬松的環(huán)境璧眠。盡管他被 King’s College 的核心學(xué)術(shù)圈以行為不夠檢點(diǎn)的理由而拒之門外缩焦，Turing 還是得到了巨大的發(fā)展。并且當(dāng)他獲得了學(xué)位證書之后责静，Turing 成了 King’s College 的一名導(dǎo)師袁滥。而如果不是后來的 Turing 機(jī)的誕生和二次大戰(zhàn)的爆發(fā)，Turing 恐怕只會在數(shù)理邏輯的世界里慢條斯理灾螃、優(yōu)哉游哉地生活一輩子了题翻。
由于 Turing 發(fā)表的一系列論文，他被召入政府 Code and Cypher School腰鬼。這所學(xué)院在一個叫做 Bletchley Park 的維多利亞風(fēng)格的大廈里嵌赠。這里囫圇吞棗似的聚集了那些被認(rèn)為有可能攻破納粹通信密碼的人，包括數(shù)學(xué)家熄赡、國際象棋大師姜挺、古埃及研究學(xué)家等等。因?yàn)檫@項(xiàng)工程受到了嚴(yán)格的保密彼硫，Turing 在這里的工作直到他去世后才得以公之于眾炊豪。正如計算機(jī)的問世一般凌箕，Bletchley Park 的工作也是眾人共同智慧的結(jié)晶。而 Turing 的角色更是重中之重——他設(shè)計了一臺原始的類似計算機(jī)的機(jī)器词渤，用以高速破譯北大西洋上納粹 U-艇間通信的密碼牵舱。
二戰(zhàn)后，Turing 回到了劍橋缺虐，他希望能夠重新拾回他所向往的寧靜的研究生活芜壁。與此同時，國家物理實(shí)驗(yàn)室新近成立了一個數(shù)學(xué)分支——這個千載難逢的機(jī)遇使得 Turing 能夠設(shè)計出真正的 Turing machine（即ACE —— Automatic Computing Engine）—— Turing 欣然前往高氮。然而事實(shí)并不如人意沿盅，官僚主義、繁文縟節(jié)纫溃，事不關(guān)己腰涧、高高掛起之風(fēng)盛行于時。戰(zhàn)爭年代里的那種晨興夜寐紊浩、攻苦食淡的精神早已蕩然無存窖铡。Turing 的提議不是被束之高閣就是被全然否定。Turing 決定離開 NPL坊谁，而后他在劍橋小憩费彼，最終來到了曼徹斯特大學(xué)。這里的實(shí)驗(yàn)室正在根據(jù)他 1937 年提出的構(gòu)想建造一臺計算機(jī)口芍。
Turing 自發(fā)表第一篇論文以來箍铲，就一直致力于拓展其關(guān)于會思考的機(jī)器的設(shè)想。他甚至提出鬓椭，一臺會思考的機(jī)器可以學(xué)習(xí)并編制指令颠猴。1950 年，在著名的英國哲學(xué)期刊 Mind 上小染，Turing 提出了“模仿測試”的概念（后來被稱做“Turing 測試”）翘瓮。比如在一封閉的屋子里，一提問人可以向另一個人與一臺機(jī)器發(fā)問裤翩。若提問人不能通過二者的回答辨別出哪一個是人资盅，哪一個是機(jī)器的話，則這臺機(jī)器就被認(rèn)為能夠象人類一樣地“思考”踊赠。
Turing 在人工智能支持者的心目中仍是一位英雄——其原因部分來自于 Turing 對未來的一個樂觀的估計：“未來的某一天呵扛，女士們帶著她們的計算機(jī)在公園里散步，她們說：‘我的計算機(jī)告訴我這真是個快樂的早晨筐带！’”
不幸的是今穿，美好的憧憬總讓路于殘酷的現(xiàn)實(shí)。在曼徹斯特的時候烫堤，一天他因遭搶劫而報警荣赶，那時他正和另一個同性戀男子在一起凤价，而這個人很可能為罪犯所認(rèn)識。Turing 從不隱瞞自己的同性戀傾向拔创，但這次卻使他身陷囹圄利诺。同性戀在當(dāng)時的英國仍是極重的罪名，1952 年剩燥，Turing 被判決為“嚴(yán)重猥褻罪”慢逾。不久他被減刑，并被要求注射雌性荷爾蒙以去除其同性欲望灭红。一次侣滩，Turing 對他的朋友說：“我變得越來越有女人味了！”在 1954 年 6 月 7 日变擒，Turing 食注有氰化鉀的蘋果自盡, 當(dāng)時他只有 41 歲君珠。
Turing 機(jī)簡介
Alan Turing 在1936提出了非凡的 Turing 機(jī)概念，從而定義出可計算性娇斑，Turing 的思法是基于對人們用筆和紙來實(shí)現(xiàn)一個算法的分析策添，他把這樣的過程看作下列兩種非常簡單的動作。
（1）寫上或擦去某個符號毫缆。
（2）把注意從紙的某個部位轉(zhuǎn)移到另一個部位唯竹。
而在每個階段，算法說明下一次要做的動作苦丁。這樣就依賴于（a）行為者當(dāng)前觀注的紙上某個部位上的符號和（b）行為者思維的當(dāng)前狀態(tài)浸颓。為了達(dá)到實(shí)現(xiàn)算法的目的，假定這完全由此算法以及迄今為止的運(yùn)算記錄來確定旺拉。這可能為編入一個部分的記錄产上，但這不反映行為者的心情、智力和理解力账阻。而且由于行為者是有窮的蒂秘，故他只能處于有窮個互異狀態(tài)泽本。當(dāng)然行為者的狀態(tài)能轉(zhuǎn)為此階段已執(zhí)行的動作淘太。Turing 以此法設(shè)計一種有窮機(jī)器來執(zhí)行算法，后來這類機(jī)器被稱為 Turing 機(jī)规丽。
下面我們給出 Turing 機(jī)的定義蒲牧。一個 Turing 機(jī) 是一個有窮裝置其在一條紙帶上執(zhí)行運(yùn)算。這條紙帶向兩端無限延伸且在兩個方向上都已畫上了無窮多個方格赌莺。（參見圖１）
紙帶代表人類行為者算題時的紙冰抢，而每個方格代表即時運(yùn)作的一個部分。在運(yùn)算時只有有窮格被利用艘狭，但我們事先不知道要用多少個格子挎扰。紙帶是無窮的代表人類在計算時可無限量提供白紙翠订。在任何時刻，紙帶上的每個方格要么空白遵倦，要么含某個符號尽超，這些符號取自M的字母表固定的一列符號 梧躺。下以
表示空白且把
看作
似谁。屬于
的字母表。
有一個讀頭掠哥，它在任何時候都掃描著紙帶的單個方格巩踏。（參見圖２）
可在紙帶上進(jìn)行三種簡單動作：
- 擦去正被掃描方格的符號且把它換成
字母表中的另一符號。
- 把讀頭移至正被掃描方格的右邊的方格续搀。
- 把讀頭移至正被掃描方格的左邊的方格塞琼。
在任何給定時刻， 處于某個狀態(tài)禁舷，
的狀態(tài)總共有有窮個屈梁，可設(shè)為
，在運(yùn)作中榛了，
的狀態(tài)是可變的在讶。我們可設(shè)想
的當(dāng)前狀態(tài)
展示于
的外體上（參見圖2），認(rèn)為此
既部分指導(dǎo)當(dāng)今做了什么以及今后將做什么霜大。
在任何時刻 采取的行動取決于
的當(dāng)前狀態(tài)以及正被掃描的符號构哺，這樣的依賴關(guān)系被用
的說明來描述，
的說明
是由有窮個四元組構(gòu)成战坤，每個四元組呈下形：
這里
,
中的四元組
說明當(dāng)
處于狀態(tài)
且正掃描于
時
將采取的動作如下：
帶上運(yùn)算
1.1. 若則擦去
,同時在當(dāng)前方格中寫上
1.2. 若曙强，將讀頭向右移一格
1.3. 若，將讀頭向左移一格
轉(zhuǎn)成狀態(tài)
需要對每個對
至多存在一個呈形
的四元組于
為了進(jìn)行計算，必須為 提供一條紙帶以及確定
當(dāng)前所掃描的方格囊卜，而且指定
的初始狀態(tài)娜扇。然后，假設(shè)
當(dāng)前狀態(tài)為
且正掃描符號
, 若在
的說明
中栅组，有呈形
的四元組雀瓢，則
將如上所述地動作。這種動作將重復(fù)于新狀態(tài)和正被掃描的符號玉掸，
將盡可能地如此進(jìn)行下去刃麸。
的動作終止僅當(dāng)其狀態(tài)為
且正掃描著
使
中不存在呈形
的
元組，即
中無四元組其指示下一步做什么司浪，當(dāng)然這種情況永不發(fā)生泊业。
例 該 的一個 Turing 機(jī)其字母表為
且其可能狀態(tài)為
和
吁伺，
的說明為
假設(shè)為 提供的紙帶為
若為 提供的紙帶的每個方格為
或
智政，則
不停機(jī)。
由上例可看出箱蝠，Turing 機(jī) 是在紙帶上實(shí)行算法的一個裝置续捂，算法的全部內(nèi)容含于
的說明
中理論上，Turing 機(jī)被定義成某個
元組集合宦搬，而不是實(shí)際上構(gòu)造的物理 Turing 機(jī)牙瓢。
為了把 Turing 機(jī)當(dāng)作計算數(shù)論函數(shù)，我們首先在紙帶上表示數(shù)间校，例如設(shè) 的字母表中含
矾克，把
看作“小木棒”，用連續(xù)的
個“
”表示
憔足。
約定胁附，, 對于
元組
, 其對應(yīng)的帶表達(dá)式為
定義：設(shè) 為從
到
的部分函數(shù)，Turing 機(jī)
計算
指若為
提供上面的紙帶滓彰，初始狀態(tài)為
且箭頭標(biāo)出正掃描的方格控妻，則
對于 元部分函數(shù)
,
計算
指
始于狀態(tài)
且提供如下紙帶且由箭頭指出正被掃描的方格：
若 計算終止則
為帶上
的總數(shù)否則
無定義抬驴。
例 加法 可由如下的 Turing 機(jī)計算：
的字母表為
对雪，
的說明
為
情況１：
停。
情況２：
定義：一個部分?jǐn)?shù)論函數(shù)是 Turing 可計算的指存在 Turing 機(jī)其計算之藏斩。這樣就定義了什么是可計算的他匪。由以上知 是 Turing 的計算的菇存，事實(shí)上 Turing 的計算能力非常強(qiáng)大，一切的遞歸函數(shù)都是 Turing 可計算的邦蜜，可以證明任何一種程序設(shè)計語言所能計算的函數(shù)一定是 Turing 可計算的依鸥，為此現(xiàn)在人們接受 Church-Turing 論點(diǎn)：一切直覺可計算的函數(shù)是 Turing 可計算的。
Turing生平
1912--
Alan Turing 出生于 1912 年 6 月 23 日悼沈，倫敦贱迟。他的父親 Julius Mathison Turing，是印度 British Civil Service 成員井辆。他經(jīng)常在國外关筒。Alan 的母親 Ethel Sara Stoney 是 Madras 鐵路總工程師的女兒。Alan 的父母在印度相遇杯缺，并在那兒結(jié)了婚。當(dāng) Alan 大約一歲時睡榆，他的母親在印度與丈夫相聚萍肆。而 Alan 留在了英國袍榆，與這個家庭的朋友待在一起。之后, Alan 被送入學(xué)校塘揣，但這似乎沒有使其受到任何好處包雀，因此，幾個月后亲铡，他離開了學(xué)校才写。接下來，他又被送往 Hazlehurst Preparatory 學(xué)校奖蔓，在那兒赞草，他在許多課程上獲得了中上的成績，但他相當(dāng)有主見吆鹤。在學(xué)習(xí)生涯中他對棋類產(chǎn)生了興趣厨疙，并且加入了辯論社。
1926--
他通過了常規(guī)入學(xué)考試疑务，隨后進(jìn)入了學(xué)校沾凄。1926 年，Turing 恰遇大罷工知允，當(dāng)罷工正進(jìn)行中撒蟀，他騎車 60 英里從家來到學(xué)校。雖然母親堅定的認(rèn)為他必須接受公立學(xué)校的教育温鸽，但 Turing 發(fā)現(xiàn)他很難成為學(xué)校所期望的那樣牙肝。許多有獨(dú)創(chuàng)思想的思想家發(fā)現(xiàn)學(xué)校是一個幾乎無法理解的過程，Turing 便是一例嗤朴。他的天賦驅(qū)使他朝自己的方向發(fā)展而無需老師配椭。
Turing 因書法而被批評，為英語而奮爭雹姊，甚至在數(shù)學(xué)上他采用自己的方法而不用老師所教授的解題法股缸。在 Sherborne 期間，盡管是非常規(guī)的方法吱雏，Turing 仍然贏得了幾乎所有的數(shù)學(xué)獎敦姻。從早期起，Turing 就對化學(xué)中的一個課題很感興趣歧杏，他按自己的日程安排做試驗(yàn)镰惦，這使得他的老師很不高興。 Turing 的校長認(rèn)為：如果他留在公立學(xué)校,他必須以接受教育為目標(biāo)犬绒。如果他僅想成為科學(xué)專家旺入，在公立學(xué)校就是浪費(fèi)時間。這話遠(yuǎn)超出了對 Turing 自身的意義，他說明了圖靈所遇到的學(xué)校體制茵瘾。雖然礼华，他的老師可能并不清楚他在自學(xué)些什么,但 Turing 在校期間學(xué)習(xí)了深奧的數(shù)學(xué)知識。他閱讀了 Einstein 的關(guān)于相對論的論文拗秘，還通過 Eddington 的“物質(zhì)世界的性質(zhì)”了解量子力學(xué)圣絮。
1928 年，發(fā)生了影響 Turing 一生的事雕旨。他與 Christopher Morcom 年長其一歲的學(xué)生扮匠，產(chǎn)生了親密的友誼，并且兩人共同工作于科學(xué)事業(yè)凡涩。也許棒搜，這是 Turing 第一次找到一位有共同思想的人⊥徽眨可是 Morcom 于1930年2月去世帮非。這對 Turing 是一個沉重的打擊。在 Morcom 生病期間讹蘑，Turing 就有死亡的預(yù)感末盔。他感到這是科學(xué)無法解釋的。之后座慰，他寫到：這些事實(shí)是不難解釋的陨舱，但我感到驚奇！
1931--
盡管學(xué)校這幾年的艱難版仔，Turing 仍然在 1931 年進(jìn)入了劍橋皇家學(xué)院學(xué)習(xí)數(shù)學(xué)游盲。這并非易事。1929 年蛮粮，Turing 參加了獎學(xué)金考試益缎，他贏得了一個展現(xiàn)機(jī)會而非獎學(xué)金。因?qū)@一結(jié)果的不滿然想，Turing 在第二年又參加了考試莺奔，這一次他獲得了獎學(xué)金。劍橋較其他學(xué)校對像這樣的非常規(guī)學(xué)生而言是一個相對較舒適的環(huán)境变泄。他現(xiàn)在更能探索自己的思想令哟，在 1933 年他讀了 的數(shù)學(xué)哲學(xué)入門。同時妨蛹，他讀了 Neumann 關(guān)于量子力學(xué)的 1932 年的文章屏富。這是一個其一生反復(fù)研究過的課題。
1933 年蛙卤，Turing 開始對數(shù)理邏輯感興趣狠半。Turing 讀了一篇關(guān)于“數(shù)學(xué)和邏輯”的文章。他提出數(shù)學(xué)的純邏輯的觀點(diǎn)是不足的，數(shù)學(xué)命題具有多種解釋典予，邏輯只是一種甜滨。1933 年乐严，德國希特勒上臺瘤袖，英國爆發(fā)了反戰(zhàn)運(yùn)動。Turing 加入了反戰(zhàn)運(yùn)動昂验，但他沒有隨波逐流去信仰某些主義捂敌。Turing 畢業(yè)於 1934 年，在 1935 年的春天,他參加了 Max Mewman 的關(guān)于數(shù)學(xué)基礎(chǔ)的高級教程既琴。這一課程研究了 G?del 不完全性結(jié)果和 Hilbert 的可判定性問題占婉。某種意義上來說，可判定性是一個簡單的問題甫恩，亦即給定一個數(shù)學(xué)命題逆济，是否能找到一個決定命題是真或假的算法。對于大多數(shù)命題來說磺箕，尋找這樣一個算法是簡單的奖慌。真正的難點(diǎn)在于證明對于確定的命題，這樣的算法不存在松靡。當(dāng)給出了一個解決某一問題的算法简僧，很明顯它確實(shí)是一個算法，然而沒有關(guān)于算法的足夠嚴(yán)謹(jǐn)?shù)亩x使得可證明算法的不存在性雕欺。Turing 開始對這些問題進(jìn)行研究岛马。1935 年，圖靈因一篇關(guān)于高斯的誤差函數(shù)（證明概率理論的基本結(jié)果屠列，亦即中心極限定理）的論文而當(dāng)選為劍橋皇家學(xué)院的成員啦逆。雖然中心極限定理已被發(fā)現(xiàn)，但 Turing 并不知道笛洛，他獨(dú)立的發(fā)現(xiàn)了它夏志。1936 年, Turing 成為一位 Smith 獎得主。
1937--
現(xiàn)在撞蜂，Turing 在劍橋的成就被用來說明他在概率理論上的工作盲镶。然而，自從他參加了 Newman 的課程后蝌诡，他就開始做可判定性問題的研究了溉贿。1936 年,他發(fā)表了On Computable Numbers, with an Application to the Entscheidungsproblem 的學(xué)術(shù)文章。在這篇論文中浦旱，Turing 引入了抽象機(jī)的概念（現(xiàn)被稱為 Turing 機(jī)）宇色。Turing 機(jī)利用有限的規(guī)則（由一張有限表給出）及從帶子上讀入一個符號，從一種狀態(tài)轉(zhuǎn)換到另一狀態(tài)。Turing 機(jī)可輸入或刪除帶子上的一個字符宣蠕。Turing 寫到：記錄下的一些字符將會形成正在計算的實(shí)數(shù)的小數(shù)的數(shù)字序列例隆。其他的則只是一些粗略的符號用來”協(xié)助存儲”，應(yīng)被刪除抢蚀。
他將可計算數(shù)定義為小數(shù)擴(kuò)展位可通過 Turing 機(jī)從空白帶子產(chǎn)生的實(shí)數(shù)镀层。他指出那即可計算的，但由于僅可數(shù)的實(shí)數(shù)是可計算的皿曲，多數(shù)實(shí)數(shù)是不可計算的唱逢，因此，他給出了不可計算的數(shù)的描述屋休，并指出由于他在限定條件下描述了一個不能在限定條件下描述的數(shù)坞古，從而，這顯得有些矛盾劫樟。但 Turing 明白這顯然的矛盾的根源痪枫。給定指令表的 Turing 機(jī)是否輸出無限序列的數(shù)（用另一 Turing 機(jī)實(shí)現(xiàn)）是無法判決的。
雖然叠艳，這篇論文包含著對數(shù)學(xué)和計算機(jī)科學(xué)均有相當(dāng)價值的觀點(diǎn)奶陈，但在倫敦數(shù)學(xué)會學(xué)報上發(fā)表它卻不是那么容易的。原因是 Alonzo Church 於 1936 年在美國數(shù)學(xué)期刊上發(fā)表了一個初等數(shù)論不可解問題虑绵，同樣證明對于算術(shù)無判定過程尿瞭。Turing 的方法與 Church 有相當(dāng)?shù)牟顒e，但在倫敦數(shù)學(xué)會期刊出版它之前翅睛，Newman 為此費(fèi)盡唇舌声搁。Turing 的修改稿提到了 Church 的結(jié)果于 1936 年 4 月首次完成，同年 8 月修改的論文捕发，這篇修改稿於 1937 年發(fā)表疏旨。
與 Church 討論的好處在于，1936 年 Turing 成為普林斯頓大學(xué)的研究生扎酷。在普林斯頓 Church 的指導(dǎo)下, Turing 了解了研究的方法檐涝。1938 年,他返回英國。1937 年法挨，Turing 回英國度暑假邂逅 Wittgenstein谁榜。他在普林斯頓的工作主要是基于序數(shù)的邏輯系統(tǒng)，發(fā)表于 1939 年凡纳。Newman 認(rèn)為：這篇論文充滿了有趣的設(shè)想和觀點(diǎn)……他展現(xiàn)了 Turing 的直覺及數(shù)學(xué)證明方面的東西窃植。
在這篇論文發(fā)表之前，Turing 發(fā)表了兩篇更常規(guī)的數(shù)學(xué)論題方面的論文荐糜。一篇是討論通過有限群逼近 Lie 群的方法巷怜，另一篇證明了擴(kuò)展群的結(jié)果并給出了更簡單和系統(tǒng)的方法葛超。（Reinhold Baer 首次證明了這一結(jié)果），Turing 在 Turing 機(jī)上的工作最引人注目的是在現(xiàn)實(shí)技術(shù)所能構(gòu)造之前延塑，他已描述了現(xiàn)代計算機(jī)绣张。他在 1936 年的論文中證明通用 Turing 機(jī)的存在：能用來做任何特殊目的的機(jī)器的工作，亦即若有恰當(dāng)?shù)闹噶钶斎牍卮蛇M(jìn)行任何計算侥涵。
盡管對 Turing 來說，“計算機(jī)”是一個執(zhí)行計算的人豫缨，但我們必須從他對廣義 Turing 機(jī)的描述中看到我們今天的計算機(jī)加裝有程序的帶子即 Turing 機(jī)独令。在普林斯頓期間端朵，Turing 設(shè)想過構(gòu)造計算機(jī)好芭。1938 年，他一回到劍橋就開始構(gòu)造 analogue mechanical device 用來研究 Riemann 猜想冲呢，這是當(dāng)今許多人認(rèn)為的最難解決的數(shù)學(xué)問題舍败。然而，在國家密碼機(jī)構(gòu)邀請他回來破譯德國密碼之后敬拓，他的工作呈現(xiàn)出新的面貌邻薯。
1939--
當(dāng) 1939 年二戰(zhàn)爆發(fā)，Turing 立即在政府設(shè)在 Bletchley 公園的譯碼和解碼部門進(jìn)行工作乘凸。雖然官方對在那里開展的工作進(jìn)行了嚴(yán)格的保密厕诡，但現(xiàn)在大部分內(nèi)幕已被公開。Turing在密碼學(xué)和計算機(jī)方面的天才幫助破譯小組破譯了不少密碼营勤，拯救了無數(shù)士兵的生命灵嫌。那一段時間對于他是一生中最快樂的時間, 充分發(fā)揮了他的才能。
Turing 和另一位數(shù)學(xué)家 Welchman 一起在波蘭數(shù)學(xué)家早期工作的基礎(chǔ)上發(fā)展了 Bombe 機(jī)葛作，這臺機(jī)從 40 年代末對所有從 Luftwaffe 的密碼機(jī)發(fā)出的消息進(jìn)行了譯碼寿羞。德國海軍的密碼機(jī)的編碼很難被破譯，但這正是 Turing 所感興趣的挑戰(zhàn)赂蠢。在 1941 年中期绪穆，Turing 在統(tǒng)計學(xué)和信息捕獲方面的進(jìn)展，使得德國海軍的信號在 Bletchley 被破譯虱岂。
從 1942 年 11 月到 1943 年 3 月 Turing 在美國進(jìn)行解碼和一個語音保密系統(tǒng)的研究工作玖院。德國人加密方式的改變意味著 Bletchley 失去了破譯消息的能力。盡管 Turing 并沒有直接參與到成功破譯更多的密碼工作中第岖，但他的思想的重要性在這項(xiàng)工作中得到充分體現(xiàn)难菌。1945 年, Turing 由于在戰(zhàn)爭中所作出的貢獻(xiàn)而獲得了 OBE 獎。
1946--
二戰(zhàn)后扔傅，Turing 被倫敦國家物理實(shí)驗(yàn)室邀請去參與計算機(jī)的設(shè)計试读。他在 1946 年提交了一份關(guān)于自動計算機(jī)器的報告钩骇。用現(xiàn)代人的觀點(diǎn)看來慢叨，Turing 當(dāng)時所提出的設(shè)想是一份有關(guān)計算機(jī)的原始的詳細(xì)設(shè)計轩拨。他為 ACE(自動計算機(jī)器)設(shè)計的存儲器的大小被當(dāng)時大多數(shù)人認(rèn)為是毫無希望和過于夸張的，以至于在這個項(xiàng)目被批準(zhǔn)前被耽誤了好一陣。
在 1947 到 1948 學(xué)年 Turing 回到了劍橋，在那里他的研究興趣不再是計算機(jī)和數(shù)學(xué)了，令人驚奇的是，他竟然研究神經(jīng)學(xué)和生理學(xué)。在這期間轧钓，他并沒有忘了計算機(jī)而柑，而且他還為計算機(jī)編寫代碼涩澡。不過他的學(xué)術(shù)研究太廣泛了，二戰(zhàn)后他還認(rèn)真研究了人類學(xué)宪郊。Walton 運(yùn)動俱樂部記錄表明店枣，Turing 作為會員曾贏得了 3 英里和 10 英里的冠軍钧唐。1947 年他參加了 A.A.A 馬拉松比賽爬范，獲得第 15 名。
1948 年 Newman 成為曼徹斯特大學(xué)的數(shù)學(xué)教授弱匪，在那里他為 Turing 提供學(xué)者基金萧诫。于是 Turing 從國家物理實(shí)驗(yàn)室回到了曼徹斯特镀裤。Newman 寫到：期望 Turing 能領(lǐng)導(dǎo)開展該項(xiàng)目中的數(shù)學(xué)工作傅联。一段時間能繼續(xù)工作下去，為已建造好的機(jī)器設(shè)計例行程序疚察，然后當(dāng)這些工作穩(wěn)定后比驻，繼續(xù)數(shù)論分析方面的一般性問題研究。工作從由 FC Williams 和 T Kilburn 提出的計算機(jī)的構(gòu)造開始衅枫。
1950--
1950 年嫁艇，Turing 在計算機(jī)和人工智能方面作出了極為卓越的成就。1950 年弦撩，Turing 發(fā)表了里程碑式的論文“機(jī)器能思考嗎步咪？”，他預(yù)測了隨著計算機(jī)發(fā)展將會出現(xiàn)的問題益楼。他研究了人工智能領(lǐng)域的核心問題猾漫。時至今日人們還用他發(fā)表的這篇論文中所提出的 Turing 測試來嘗試回答電腦是否具有智能点晴。
Turing 沒有忘記判定性問題是他那些具有深遠(yuǎn)意義的數(shù)學(xué)論文的起點(diǎn)。群論中的一個主要問題是：在一個有限群中給定任意一個字悯周，是否存在一個算法判定這個字等于單位粒督。Post 已經(jīng)證明半群中不存在這樣一個算法。雖然一開始 Turing 已經(jīng)證明了對于群有同樣一個結(jié)論禽翼，但在就對他證明做一個討論會上屠橄，他發(fā)現(xiàn)了一個錯誤。他從自己不完善的證明中發(fā)現(xiàn)一個消去的半群有不可解字問題闰挡。Turing 在1950 年發(fā)表了這個結(jié)果锐墙。1957 年勃恩通過 Turing 的這篇論文中的思想證明了存在一個有不可解字問題的群。
主要因?yàn)樵谒?1936 年提出的“Turing機(jī)”方面所做的工作长酗，Turing 在1951年當(dāng)選為倫敦皇家學(xué)院的會員溪北。到 1951 年為止，他致力于將數(shù)學(xué)應(yīng)用到生物組織研究中去夺脾。1952 年他公布了在地貌形成方面之拨，關(guān)于在有機(jī)生命體中模式和組織的演化的一部分研究工作。
1952--
1952 年 Turing 在警察局報告一宗同性戀事件的細(xì)節(jié)時被捕咧叭，他被指控違反了英國同性戀法令蚀乔。而他去警察局是因?yàn)樗獾搅死账鳌?952 年 3 月 31 日，他作為一位同性戀者被審判佳簸，他認(rèn)為他自己沒錯乙墙，未給自己辯護(hù)。然而生均，他被判為有罪。當(dāng)時腥刹，他只有兩條路可走：坐牢或注射激素马胧。他選擇了后者，并繼續(xù)他廣泛的學(xué)術(shù)研究衔峰。
他不僅在地貌形成的研究中有進(jìn)一步進(jìn)展佩脊，而且他還在量子理論和相對論的研究中提出了新的思想，即用旋量來表示初等粒子垫卤。在 Bletchley 公園的譯碼工作成了圖靈在 GCHQ 進(jìn)行譯碼和人工智能研究工作的基礎(chǔ)威彰。在冷戰(zhàn)期間，譯碼成為一項(xiàng)重要的工作穴肘，Turing 繼續(xù)為 GCHQ 工作歇盼，盡管他在曼徹斯特的同事還沒完全意識到這一點(diǎn)。在他被定罪后评抚，他失去了安全保障豹缀。但更糟糕的是伯复，安全部門的官員將他這位知識淵博，在 GCHQ 開展工作的學(xué)者定為安全方面的危險分子邢笙。由于學(xué)術(shù)需要啸如，Turing 有許多外國同事，但警察開始調(diào)查他的國外來訪者氮惯。1953 年Turing 在希臘的一次度假引起了安全人員的恐慌叮雳。1954 年 6 月 7 日，Turing 在寓所身亡妇汗，他的床頭有一個咬了一半的蘋果帘不，經(jīng)解剖，發(fā)現(xiàn)是劇毒氰化物致死铛纬，那個蘋果是在氰化物溶液中浸泡過的厌均，經(jīng)調(diào)查，Turing 為自殺告唆，但他母親始終認(rèn)為這是一個偶然事件棺弊。
結(jié)束語
Turing 不僅是一位數(shù)學(xué)家、邏輯學(xué)和計算機(jī)科學(xué)家擒悬，而且他更是一位哲學(xué)家模她，科學(xué)哲學(xué)家，他問出：“什么是計算”以及“機(jī)器能思考嗎”使我們受到哲學(xué)精神的震撼懂牧，他雖然是這個塵世的匆匆過客侈净，但他是勇敢的智者，他的發(fā)明將影響人類的思維僧凤，他是歐洲上空劃過的燦爛的流星畜侦。他是人類歷史上的大智者。人們將永遠(yuǎn)懷念他躯保，美國 ACM 設(shè) Turing 獎旋膳，以此紀(jì)念。
