艾倫·麥席森·圖靈

1912年生於英國倫敦。艾倫·麥席森·圖靈少年時就表現出獨特的直覺創造能力和對數學的愛好。

1926年，他考入倫敦有名的舍本(Sherborne)公學，受到良好的中等教育．他在中學期間表現出對自然科學的極大興趣和敏銳的數學頭腦。

1927年末，年僅15歲的圖靈為了幫助母親理解愛因斯坦的相對論，寫了愛因斯坦的一部著作的內容提要，表現出他已具備非同凡響的數學水平和科學理解力。他對自然科學的興趣使他在1930年和1931年兩次獲得他的一位同學莫科姆的父母設立的自然科學獎，獲獎工作中有一篇論文題為“亞硫酸鹽和鹵化物在酸性溶液中的反應”，受到政府派來的督學的讚賞，對自然科學的興趣為他後來的一些研究奠定了基礎，他的數學能力使他在念中學時獲得過國王愛德華六世數學金盾獎章。

1931年，圖靈考入劍橋大學國王學院，由於成績優異而獲得數學獎學金。在劍橋，他的數學能力得到充分的發展。

1935年，他的第一篇數學論文“左右殆周期性的等價”發表於《倫敦數學會雜誌》上。同一年，他還寫出“論高斯誤差函數”一文。這一論文使他由一名大學生直接當選為國王學院的研究員，並於次年榮獲英國著名的史密斯(Smith)數學獎，成為國王學院聲名顯赫的畢業生之一。

1936年5月，圖靈向倫敦權威的數學雜誌投了一篇論文，題為《論數字計算在決斷難題中的應用》。該文於1937年在《倫敦數學會文集》第42期上發表后，立即引起廣泛的注意。在論文的附錄里他描述了一種可以輔助數學研究的機器，後來被人稱為“圖靈機”，這個設想最牛的地方在於，它第一次在純數學的符號邏輯，和實體世界之間建立了聯繫，後來我們所熟知的電腦，以及還沒有實現的“人工智慧”，都基於這個設想。這是他人生第一篇重要論文，也是他的成名之作。

1937年，圖靈發表的另一篇文章“可計算性與λ可定義性”則拓廣了丘奇(Church)提出的“丘奇論點”，形成“丘奇-圖靈論點”，對計算理論的嚴格化，對計算機科學的形成和發展都具有奠基性的意義。

1936年9月，圖靈應邀到美國普林斯頓高級研究院學習，並與丘奇一同工作。

在美國期間，他對群論作了一些研究，並撰寫了博士論文。1938年在普林斯頓獲博士學位，其論文題目為“以序數為基礎的邏輯系統”，1939年正式發表，在數理邏輯研究中產生了深遠的影響。

1938年夏，圖靈回到英國，仍在劍橋大學國王學院任研究員，繼續研究數理邏輯和計算理論，同時開始了計算機的研製工作。

第二次世界大戰打斷了圖靈的正常研究工作，1939年秋，他應召到英國外交部通信處從事軍事工作，主要是破譯敵方密碼的工作。

1945年，圖靈結束了在外交部的工作，他試圖恢復戰前在理論計算機科學方面的研究，並結合戰時的工作，具體研製出新的計算機來。這一想法得到當局的支持。同年，圖靈被錄用為泰丁頓(Teddington)國家物理研究所的研究人員，開始從事“自動計算機”(ACE)的邏輯設計和具體研製工作。這一年，圖靈寫出一份長達50頁的關於ACE的設計說明書。這一說明書在保密了27年之後，於1972年正式發表。在圖靈的設計思想指導下，1950年制出了ACE樣機，1958年製成大型ACE機。人們認為，通用計算機的概念就是圖靈提出來的。

1945年到1948年，他在英國國家物理實驗室工作，負責自動計算引擎的研究。

1948年，圖靈接受了曼徹斯特大學的高級講師職務，並被指定為曼徹斯特自動數字計算機(Madam)項目的負責人助理，具體領導該項目數學方面的工作．作為這一工作的總結。

1949年成為曼徹斯特大學計算機實驗室的副主任，負責最早的真正意義上的計算機——“曼徹斯特一號”的軟體理論開發，因此成為世界上第一位把計算機實際用於數學研究的科學家。

1950年，圖靈編寫並出版了《曼徹斯特電子計算機程序員手冊》(The programmers’handbook for the Manchester electronic computer)。這期間，他繼續進行數理邏輯方面的理論研究。並提出了著名的“圖靈測試”。

1950年，他提出關於機器思維的問題，他的論文“計算機和智能(Computingmachiery and intelligence)，引起了廣泛的注意和深遠的影響。1950年10月，圖靈發表論文《機器能思考嗎》。這一劃時代的作品，使圖靈贏得了“人工智慧之父”的桂冠。

1951年，由於在可計算數方面所取得的成就，成為英國皇家學會會員，時年39歲。

1952年，他辭去劍橋大學國王學院研究員的職務，專心在曼徹斯特大學工作．除了日常工作和研究工作之外，他還指導一些博士研究生，還擔任了製造曼徹斯特自動數字計算機的一家公司——弗蘭蒂公司的顧問。

1952年，圖靈的同性伴侶協同一名同謀一起闖進了圖靈的房子實施盜竊。圖靈為此而報警。但是警方的調查結果使得他被控以“明顯的猥褻和性顛倒行為”（同性戀）。他沒有申辯，並被定罪。在著名的公審后，他被給予了兩個選擇：坐牢或荷爾蒙療法。他選擇了荷爾蒙注射，並持續了一年。在這段時間裡，藥物產生了包括乳房不斷發育的副作用。

1954年6月7日，圖靈被發現死於家中的床上，床頭還放著一個被咬了一口的蘋果。警方調查后認為是劇毒的氰化物中毒，調查結論為自殺。當時圖靈41歲。

家族成員里有三位當選過英國皇家學會會員，祖父還曾獲得劍橋大學數學榮譽學位。圖靈的父親J·M·圖靈早年就讀於牛津大學科帕斯克斯蒂學院歷史系，後來從政，被派往印度，擔任民政部的官員。圖靈的母親E·S·斯托尼(Stoney)生於一個鐵路工程師家庭，曾就讀於巴黎大學文理學院，圖靈是次子。

圖靈在科學、特別在數理邏輯和計算機科學方面，他的一些科學成果，構成了現代計算機技術的基礎。

一般遞歸函數雖給出了可計算函數的嚴格數學定義，但在具體的計算過程中，就某一步運算而言，選用什麼初始函數和基本運算仍有不確定性。為消除所有的不確定性，圖靈在他的“論可計算數及其在判定問題中的應用”一文中從一個全新的角度定義了可計算函數。他全面分析了人的計算過程，把計算歸結為最簡單、最基本、最確定的操作動作，從而用一種簡單的方法來描述那種直觀上具有機械性的基本計算程序，使任何機械(能行)的程序都可以歸約為這些動作。這種簡單的方法是以一個抽象自動機概念為基礎的，其結果是：演演算法可計算函數就是這種自動機能計算的函數。這不僅給計算下了一個完全確定的定義，而且第一次把計算和自動機聯繫起來，對後世產生了巨大的影響，這種“自動機”後來被人們稱為“圖靈機”。

圖靈機是一種自動機的數學模型，它是一條兩端(或一端)無限延長的紙帶，上面劃成方格，每個方格中可以印上某字母表中的一個字母(亦可為空格，記為S0)；又有一個讀寫頭，它具有有限個內部狀態。任何時刻讀寫頭都注視著紙帶上的某一個方格，並根據注視方格的內容以及讀寫頭當時的內部狀態而執行變換規則所規定的動作。每個圖靈機都有一組變換規則，它們具有下列三種形狀之一：qiaRqi，qiaLqi，qiabqj

意思是：當讀寫頭處於狀態qi時如果注視格的內容為字母a則讀寫頭右移一格，或左移一格，或印下字母b(即把注視格的內容由a改成b．a，b可為S0)。

圖靈把可計算函數定義為圖靈機可計算函數。1937年，圖靈在他的“可計算性與λ可定義性”一文中證明了圖靈機可計算函數與λ可定義函數是等價的，從而拓廣了丘奇論點，得出：演演算法(能行)可計算函數等同於一般遞歸函數或λ可定義函數或圖靈機可計算函數．這就是“丘奇-圖靈論點”，相當完善地解決了可計算函數的精確定義問題，對數理邏輯的發展起了巨大的推動作用。

圖靈機的概念有十分獨特的意義：如果把圖靈機的內部狀態解釋為指令，用字母表的字來表示，與輸出字輸入字同樣存貯在機器里，那就成為電子計算機了。由此開創了“自動機”這一學科分支，促進了電子計算機的研製工作．

與此同時，圖靈還提出了通用圖靈機的概念，它相當於通用計算機的解釋程序，這一點直接促進了後來通用計算機的設計和研製工作，圖靈自己也參加了這一工作。

在給出通用圖靈機的同時，圖靈就指出，通用圖靈機在計算時，其“機械性的複雜性”是有臨界限度的，超過這一限度，就要靠增加程序的長度和存貯量來解決．這種思想開啟了後來計算機科學中計算複雜性理論的先河。

所謂“判定問題”指判定所謂“大量問題”是否具有演演算法解，或者是否存在能行性的方法使得對該問題類的每一個特例都能在有限步驟內機械地判定它是否具有某種性質(如是否真，是否可滿足或是否有解等，隨大量問題本身的性質而定)的問題。

判定問題與可計算性問題有密切的聯繫，二者可以相互定義：對一類問題若能找到確定的演演算法以判定其是否具有某種性質，則稱這類問題是能行可判定的，或可解的；否則是不可判定的，或不可解的。二者又是有區別的：判定問題是要確定是否存在一個演演算法，使對一類問題的每一個特例都能對某一性質給以一個“是”或“否”的解答；可計算性問題則是找出一個演演算法，從而求出一些具體的客體來。

圖靈在判定問題上的一大成就是把圖靈機的“停機問題”作為研究許多判定問題的基礎，一般地，把一個判定問題歸結為停機問題：“如果問題A可判定，則停機問題可判定．”從而由“停機問題是不可判定的”推出“問題A是不可判定的”。

所謂停機指圖靈機內部達到一個結果狀態、指令表上沒有的狀態或符號對偶，從而導致計算終止。在每一時刻，機器所處的狀態，紙帶上已被寫上符號的所有格子以及機器當前注視的格子位置，統稱為機器的格局。圖靈機從初始格局出發，按程序一步步把初始格局改造為格局的序列。此過程可能無限制繼續下去，也可能遇到指令表中沒有列出的狀態、符號組合或進入結束狀態而停機。在結束狀態下停機所達到的格局是最終格局，此最終格局(如果存在)就包含機器的計算結果。所謂停機問題即是：是否存在一個演演算法，對於任意給定的圖靈機都能判定任意的初始格局是否會導致停機？圖靈證明，這樣的演演算法是不存在的，即停機問題是不可判定的，從而使之成為解決許多不可判定性問題的基礎。

1937年，圖靈用他的方法解決了著名的希爾伯特判定問題：狹謂詞演算(亦稱一階邏輯)公式的可滿足性的判定問題。他用一階邏輯中的公式對圖靈機進行編碼，再由圖靈機停機問題的不可判定性推出一階邏輯的不可判定性。他在此處創用的“編碼法”成為後來人們證明一階邏輯的公式類的不可判定性的主要方法之一。

在判定問題上，圖靈的另一成果是1939年提出的帶有外部信息源的圖靈機概念，並由此導出“圖靈可歸約”及相對遞歸的概念。運用歸約和相對遞歸的概念，可對不可判定性與非遞歸性的程度加以比較。在此基礎上，E．波斯特(Post)提出了不可解度這一重要概念，這方面的工作後來有重大的進展。

圖靈參與解決的另一個著名的判定問題是“半群的字的問題”，它是圖埃(Thue)在1914年提出來的：對任意給定的字母表和字典，是否存在一種演演算法能判定兩個任意給定的字是否等價[給出有限個不同的稱為字母的符號，便給出了字母表，字母的有限序列稱為該字母表上的字。把有限個成對的字(A1，B1)，…，(An，Bn)稱為字典．如果兩個字R和S使用有限次字典之後可以彼此變換，則稱這兩個字是等價的]1947年，波斯特和A．A．馬爾科夫(Markov)用圖靈的編碼法證明了這一問題是不可判定的。1950年，圖靈進一步證明，滿足消元律的半群的字的問題也是不可判定的。

圖靈在第二次世界大戰中從事的密碼破譯工作涉及到電子計算機的設計和研製，但此項工作嚴格保密。直到70年代，內情才有所披露。從一些文件來看，很可能世界上第一台電子計算機不是ENIAC，而是與圖靈有關的另一台機器，即圖靈在戰時服務的機構於1943年研製成功的CO-LOSSUS(巨人)機，這台機器的設計採用了圖靈提出的某些概念。它用了1500個電子管，採用了光電管閱讀器；利用穿孔紙帶輸入；並採用了電子管雙穩態線路，執行計數、二進位算術及布爾代數邏輯運算，巨人機共生產了10台，用它們出色地完成了密碼破譯工作．

戰後，圖靈任職於泰丁頓國家物理研究所(Teddington National Physical Laboratory)，開始從事“自動計算機”(Automatic Computing Engine)的邏輯設計和具體研製工作。1946年，圖靈發表論文闡述存儲程序計算機的設計。他的成就與研究離散變數自動電子計算機（Electronic Discrete Variable Automatic Computer）的約翰·馮·諾伊曼（John von Neumann）同期。圖靈的自動計算機與諾伊曼的離散變數自動電子計算機都採用了二進位，都以“內存儲存程序以運行計算機”打破了那個時代的舊有概念。

1949年，圖靈成為曼切斯特大學（University of Manchester ）計算實驗室的副院長，致力研發運行Manchester Mark 1型號儲存程序式計算機所需的軟體。1950年他發表論文《計算機器與智能》（Computing Machinery and Intelligence），為後來的人工智慧科學提供了開創性的構思。提出著名的“圖靈測試”，指出如果第三者無法辨別人類與人工智慧機器反應的差別，則可以論斷該機器具備人工智慧。

1956年圖靈的這篇文章以“機器能夠思維嗎？”為題重新發表．此時，人工智慧也進入了實踐研製階段。圖靈的機器智能思想無疑是人工智慧的直接起源之一。而且隨著人工智慧領域的深入研究，人們越來越認識到圖靈思想的深刻性：它們如今仍然是人工智慧的主要思想之一。

從1952年直到去世，圖靈一直在數理生物學方面做研究。他在1952年發表了一篇論文《形態發生的化學基礎》(The Chemical Basis of Morphogenesis)。他主要的興趣是斐波那契葉序列，存在於植物結構的斐波那契數。他應用了反應-擴散公式，如今已經成為圖案形成範疇的核心。他後期的論文都沒有發表，一直等到1992年《艾倫·圖靈選集》出版，這些文章才見天日。

1945年到1948年，圖靈在國家物理實驗室，負責自動計算引擎（ACE）的工作。1949年，他成為曼徹斯特大學計算機實驗室的副主任，負責最早的真正的計算機---曼徹斯特一號的軟體工作。在這段時間，他繼續作一些比較抽象的研究，如“計算機械和智能”。圖靈在對人工智慧的研究中，提出了一個叫做圖靈試驗的實驗，嘗試定出一個決定機器是否有感覺的標準。

圖靈試驗由計算機、被測試的人和主持試驗人組成。計算機和被測試的人分別在兩個不同的房間里。測試過程由主持人提問，由計算機和被測試的人分別做出回答。觀測者能通過電傳打字機與機器和人聯繫（避免要求機器模擬人外貌和聲音）。被測人在回答問題時儘可能表明他是一個“真正的”人，而計算機也將儘可能逼真的模仿人的思維方式和思維過程。如果試驗主持人聽取他們各自的答案后，分辨不清哪個是人回答的，哪個是機器回答的，則可以認為該計算機具有了智能。這個試驗可能會得到大部分人的認可，但是卻不能使所有的哲學家感到滿意。圖靈試驗雖然形象描繪了計算機智能和人類智能的模擬關係，但是圖靈試驗還是片面性的試驗。通過試驗的機器當然可以認為具有智能，但是沒有通過試驗的機器因為對人類了解的不充分而不能模擬人類仍然可以認為具有智能。圖靈試驗還有幾個值得推敲的地方，比如試驗主持人提出問題的標準，在試驗中沒有明確給出；被測人本身所具有的智力水平，圖靈試驗也疏忽了；而且圖靈試驗僅強調試驗結果，而沒有反映智能所具有的思維過程。所以，圖靈試驗還是不能完全解決機器智能的問題。例如：質問者可以說：“我聽說，上午一頭犀牛在一個粉紅色的氣球中沿著密西西比河飛。你覺得怎樣？”(你們可以想像該電腦的肩頭上泛出的冷汗：)電腦也許謹慎地回答： “我聽起來覺得這不可思議，”到此為止沒有毛病。質問者又問：“是嗎？我的叔叔試過一回，順流、逆流各一回，它只不過是淺色的並帶有斑紋。這有什麼不可思議的?”很容易想像，如果電腦沒有合適的“理解”就會很快地暴露了自己、在回答第一個問題時，電腦的記憶庫非常有力地想列犀牛沒有翅膀，甚至可以在無意中得到“犀牛不能飛”，或者這樣回答第二個問題“犀牛沒有斑紋”。下一回質問者可以試探真正無意義的問題．譬如把它改變成“在密西西比河下面”，或者“在一個粉紅色的氣球之外”．或者“穿一件粉紅色衣服”，再去看看電腦是否感覺到真正的差別。其實，要求電腦這樣接近地模仿人類，以使得不能和一個人區分開實在是太過分了。一些專家認為，我們不該以電腦能否思維為目標，而是以能多大程度地模仿人類思維為目標；然後，讓設計者再朝著這個目標努力。1952年，圖靈寫了一個國際象棋程序。可是，當時沒有一台計算機有足夠的運算能力去執行這個程序，他就模仿計算機，每走一步要用半小時。他與一位同事下了一盤，結果程序輸了。後來美國新墨西哥州洛斯阿拉莫斯國家實驗室的研究群根據圖靈的理論，在MANIAC上設計出世界上第一個電腦程序的象棋。

2012年6月23號是圖靈誕辰100年紀念日，BBC在發表了一系列的紀念性文章，其中就有圖靈獎獲得者、Google資深副總裁兼首席網際網路專家文特·瑟夫的這些評價：圖靈不但以破譯密碼而名聞天下，他在人工智慧和計算機等領域也作出了重要貢獻，他常被認為是現代計算機科學的創始人。戰爭結束后，在曼徹斯特大學工作的他研製了“曼徹斯特馬克一號”———著名的現代計算機之一。1999年，他被《時代》雜誌評選為20世紀100個最重要的人物之一。

2012年，是一個偉人的百年誕辰。即使我們把所有崇高的致意奉獻給他都不為過。他就是艾倫·圖靈。100年前，艾倫·圖靈誕生在一個文化和科技水平都與如今完全不同的時代里，但這並不影響他成為今天最偉大最值得紀念的人之一。他為計算機領域奠定了不可埋沒的基礎，沒有他就沒有計算機的今天。

英國首相卡梅倫：圖靈在破解二戰德軍密碼、拯救國家上發揮了關鍵作用，是一個“了不起的人”。

2009年，英國計算機科學家康明（John Graham-Cumming）發起了為圖靈平反的在線請願，截止到2009年9月10日請願簽名人數已經超過了3萬，為此，當時的英國政府及首相戈登布朗不得不發表正式的道歉聲明。

2012年12月，霍金、納斯（Paul Nurse，諾貝爾醫學獎得主）、里斯（Martin Rees，英國皇家學會會長）等11位重要人士致函英國首相卡梅倫，要求為其平反。

2013年12月24日，在英國司法大臣克里斯・格雷靈（Chris Grayling）的要求下，英國女王終於向圖靈頒發了的皇家赦免。英國司法部長宣布，“圖靈的晚年生活因為其同性取向而被迫蒙上了一層陰影，我們認為當時的判決是不公的，這種歧視現象如今也已經遭到了廢除。為此，女王決定為這位偉人送上赦免，以此向其致敬。”

為了紀念他對計算機科學的巨大貢獻，由美國計算機協會（ACM）於1966年設立一年一度的圖靈獎，以表彰在計算機科學中做出突出貢獻的人，圖靈獎被喻為“計算機界的諾貝爾獎”。

多年來，包括霍金在內的著名科學家，不斷力促英國政府特赦這位“現代最傑出的數學家之一”。

2009年9月11日晚，英國首相布朗代表英國政府向已經逝去55年的英國著名數學家、德國密碼的破譯者艾倫·麥席森·圖靈作出了明確的道歉。這位二戰時期的密碼破譯者因同性戀被判“化學閹割”，55年前自盡身亡。

布朗表示，圖靈所受到的對待是“駭人聽聞的”和“完全不公平的”，英國對這位傑出數學家的虧欠是巨大的。布朗說，他為作出正式的道歉感到自豪。“你沒有得到更好的對待，我們深感抱歉”。由布朗簽署的聲明發布在唐寧街十號網站上。

2013年12月24日，英國女王伊麗莎白二世簽署對圖靈定性為“嚴重猥褻”的赦免，並立即生效。司法大臣克里斯·格雷林說圖靈應被當之無愧地“記住並認可他對戰爭無與倫比的貢獻”，而不是對他後來刑事定罪。在2013年8月女王正式宣告赦免圖靈。

2012年6月15-16日，33點陣圖靈獎獲得者首次共聚舊金山，來紀念艾倫·圖靈100周年誕辰。他們一同回顧了圖靈的偉大貢獻和計算機科學在過去幾十年的發展，並暢談了對未來的思考。

2021年3月25日，英格蘭銀行發布新版50英鎊紙幣。艾倫·圖靈將成為2021年新一代英鎊上的圖案。艾倫·圖靈被稱為計算機科學之父，人工智慧之父。

《艾倫·圖靈傳》是英國作家安德魯·霍奇斯編寫的，已由湖南科學技術出版社於2012年12月出版，是公認的最權威的圖靈傳記。作者安德魯·霍奇斯是牛津大學的數學家，也是一位同性戀者，他收集了大量史料，寫成這本圖靈傳。