圖靈在學校也學到了一個與此相關的前沿思想。這是由德國數學家大衛·希爾伯特（David Hilbert）在1928年提出的挑戰。這項挑戰稱為“判定問題”（Entscheidungs problem）。希爾伯特想知道的是，一個命題的真假能否自動判定。他的問題是，對于給定的數學語言，有沒有什么方法或者程序可以讓機器判定某件事情的真假，并將結果顯示出來。這樣一來，你就可以告訴這臺神秘的機器，你輸入的語言符合邏輯，讓它判斷下面這句話是正確還是錯誤：如果所有的姐妹都是女性，而莎拉是你的姐妹，那么莎拉是男性。于是機器就會稍加思考，然后輸出結果“錯誤”。或者你可以告訴機器，你輸入的語言是算術語言，讓它判斷下面這句話是正確還是錯誤：“任何大于1的整數都可以通過質數相乘求得。”于是機器又會思考一番，輸出結果“正確”。
雖然這聽起來頗為實用，但真正的挑戰在于：這種自動化的方法或機器是否有可能存在？自動判定簡單的句子似乎并不是遙不可及的事情，但如果是用復雜的數學語言寫成的高難度句子，是否仍有可能加以判定？這種萬能的真理說明者是否真有可能存在？
永不停機的圖靈機
圖靈把接下來幾個月的時間都撲在了這個問題上。年僅23歲的他或許資歷尚淺，但他有一顆極富創造力的頭腦，很快就想出了一些絕妙的點子。他所遇到的第一個問題，就是如何構想這個神秘的進程或機器。那個時候，電子學還沒有創立，世界上最復雜的電氣系統是前不久才問世的自動電話交換機——它們體型龐大，足以占滿一座寬敞的大廳。當時的機器只能做一件事情，那就是它們被設計出來做的事情。但是希爾伯特提出的挑戰是制造一臺萬能機，這臺機器必須通曉任何數學語言，能夠看懂人們用數學語言表述出來的任何命題。要做到這一點，它必須能夠按照任何順序進行任何可能的數學運算，從而給操作者留出充分的余地改變問題，改編機器的程序。
當時沒有任何機器能做到這一點，于是圖靈構想了一臺能做到這一點的機器。他想象的是一臺理論計算機。
在1935年，如果你去翻閱詞典，查找計算機的定義，就會查到這樣的解釋：“執行計算工作的人”。年輕的艾倫·圖靈所構想出來的機器可以將人們以往用紙筆進行的運算過程全部自動化。這臺機器運作起來就像一個玩家在玩棋盤游戲——比如“大富翁”。它設有內存，而內存這個概念放到大富翁游戲棋中，就相當于棋子的位置、棋盤上的房子和玩家的資產。機器可以進入不同的運行狀態，就像游戲當中會出現不同的場景。它的狀態可以發生改變，好比玩家按照特定的規則推動游戲的進展。它需要來自外部的指令，遵守特定的規則，以改變運行狀態，好比玩家擲出骰子以后，如果走到標有“入獄”的棋格，就得把棋子送進“監獄”。但是，與棋盤游戲不同的是，圖靈機遵守的規則可以改變。事實上，規則可以由操作者輸入，并儲存到內存中（這就好比我們在棋盤上寫下新的規則）。不僅如此，隨著機器運行狀態的改變，它所遵循的規則還可以進一步發生改變。（好比一個棋格上原本寫著“免費停車場”，后來被改成“走進這個格子你就輸了”）。在游戲規則會發生改變的情況下玩棋盤游戲，顯然是一個高難度的挑戰！但是試想一下，如果可以改變規則，那么整個游戲的性質都有可能發生改變，比如大富翁可以變成蛇梯棋，國際象棋可以變成西洋跳棋。
當然，圖靈所指的并不是棋盤游戲。他想象的不是棋盤，而是一臺能從紙帶上讀取信息的機器。根據即時讀取的指令，機器可以將紙帶左移、右移，或在紙帶上讀取信息、輸出結果。不過，不管我們打什么樣的比方來理解圖靈機的運行機制，它的能力是始終如一的。圖靈機是一臺理論計算機。由于它可以完成任何可能的數學運算，現代計算機能做的事情都難不倒它（只不過它的運算速度要遲緩許多）。
雖然這臺奇怪的新機器終究只是紙上談兵的假想機，但是這已經足夠了，因為圖靈只是想從理論上解決希爾伯特提出的問題而已。或許頗具諷刺意味的是，圖靈雖然提出了關于通用計算機的思想，但卻并不急著證明他的機器可以解決判定問題。相反，他想證明判定問題不可能得到解決，進而說明有些問題在數學上根本不可判定。
為了做到這一點，圖靈首先假想他的小計算機正在根據紙帶上的信號執行一個運算，接著他提出了一個問題：有沒有什么方法可以判斷這臺機器究竟是會陷入死循環，不停地計算下去；還是會停止計算，給出結果呢？看起來死循環的可能性很大，方法很簡單，比方說在紙帶A點上寫上“移動到B點”，在B點上則寫上“移動到A點”。
這個問題放到今天也很有現實意義，因為計算機一旦陷入死循環，或許就會“死機”，什么事情也做不了，這是我們不希望看到的。好比我們在自動取款機上輸入PIN碼（個人識別密碼）以后，機器應該吐錢出來，而不是一動不動，什么反應也沒有！
圖靈認為，要想判斷他的機器會不會停機，那就需要再構造一臺圖靈機，以對第一臺機器進行檢測，因為他知道，他假想的機器在理論上可以進行任何數學運算。于是他假想出第二臺圖靈機，如果檢測到第一臺圖靈機永不停機，那么第二臺機器就會停機，然后輸出“不停機”；如果檢測到第一臺圖靈機停了機，那么第二臺機器就會一直運轉下去。
現在，腦筋急轉彎的地方來了。假如第二臺機器反觀自身，判斷自己會不會停止計算，那會發生什么情況？圖靈對此進行了設想，他突然發現了一個悖論：如果機器檢測到自己會永不停機，那么它就會停機，然后輸出“不停機”；如果機器檢測到自己停了機，那么它就會一直運轉下去。這在邏輯上是不可能的，由此證明，有些圖靈機是不可判定的——我們永遠也無法判斷它們會不會停機。
盡管這樣說或許令人費解、甚至不可思議，但是不可判定或不可計算的問題的確大量存在——自此之后，這樣的事實一直讓計算機程序員備受困擾。圖靈的研究結果表明，有些數學問題是計算機無法解決的，這與計算機的運算能力、運算速度和內存容量無關。
1936年，正當年輕的圖靈準備將這個振奮人心的成果公諸于世時，他偶然讀到了美國數學家阿隆佐·邱奇（Alonzo Church）前不久發表的論文。那時候，全世界有好多數學家正在著手解決希爾伯特的判定問題。其中有的數學家——比如哥德爾——已經開始有了重要的研究成果。邱奇采用的方法與圖靈截然不同，他需要創立新的數學概念和語言，以表述有關函數和演算過程的思想。他使用了自己創立的新語言——稱為λ演算，并在哥德爾的基礎上擴展了研究范圍。研究結果表明，沒有任何通用的算法可以判定任意兩個λ表達式是否相等。也就是說，有些事情永遠無法用數學方法加以判定——要想解決判定問題是不可能的。邱奇就這樣率先攻克了希爾伯特挑戰，他發表研究成果的時間只比圖靈早了幾個星期。
接下來幾年里，還有其他描述算法的理論被相繼提出，但它們都是等價的。邱奇的λ演算是經典的理論，它已成為計算機科學的寶貴工具，可用于對軟件問題進行形式證明（7）。時至今日，它的地位依然舉足輕重。不過，圖靈機顯然是概念方面的贏家。或許正是因為簡潔易懂，圖靈的計算機思想已成為理論計算機科學的基礎。時至今日，連“可計算性”的定義都是根據他的思想界定出來的。“邱奇—圖靈論題”（Church—Turing thesis ）得到了廣泛接受，該論題認為，任何可計算的問題都可以由圖靈機計算。
圖靈的貢獻
1936年，由于志同道合，圖靈決定去美國普林斯頓大學投奔邱奇，他在那里師從邱奇，完成了博士學業。
阿隆佐·邱奇自己的經歷就帶有傳奇色彩。他在高中時由于氣槍事故，導致一只眼睛失明，后來又因為這只眼睛失明而不小心被有軌電車撞倒，因緣際會，與照看他的護士墜入愛河，步入婚姻的殿堂。邱奇平時為人彬彬有禮，衣著干凈整潔，宗教信仰堅定不移，有一些出了名的怪癖，喜歡閱讀和收藏科幻小說，如果發現書中有錯誤，他會在目錄頁用鉛筆修改，或者致信作者予以糾正。每次講座開始之前，他都會按部就班地把黑板擦得纖塵不染，擦拭次數非得是偶數，而且一般都要用到肥皂和水。擦完黑板后，他會耐心地等待水跡風干，要不然不會開講。每次開講都是長篇大論，好像在看著書稿直接念一樣。如果被人打斷，他會很不自然地停下來。平時說話很少不用邏輯論證。有傳言說，邱奇連吃早飯的方式都很有邏輯：“先把牛奶倒進空碗里，放適量的糖，用早餐勺攪拌均勻，然后放一兩勺麥片。吃完這點麥片后，再接著放一兩勺，邊吃邊放。這樣一來，糖就會在牛奶中充分溶解，分布均勻，而且麥片也不會泡得太軟。”
圖靈從來沒有變得像邱奇那么愛干凈，不過他也培養了一些高度邏輯化的習慣，而且這些習慣有時顯得很古怪。博士畢業回國后，圖靈喜歡戴著防毒面罩騎車，以預防花粉癥。如果他發現自行車經常在他踩14圈以后掉鏈子，他就會每踩完13圈以后下車調整鏈子。
1938年，圖靈回國后不久，便受到政府代碼及加密學校（8）（Government Code and Cypher School）的邀請，協助軍方破解德國的著名密碼系統——“恩尼格瑪”（9）（Enigma）。1939年英國宣戰后，圖靈開始在這家位于布萊切利公園的密碼破譯機構全職工作。他很喜歡這份工作，因為它充滿挑戰，而且工作環境又好。1940年，他發明了一臺破譯機——名為“炸彈機”（Bombe，得名于波蘭的一臺破譯機），成功破解了德國空軍傳遞的所有“恩尼格瑪”加密情報。
到了1941年年中，德國海軍的“恩尼格瑪”加密情報也被全部破譯。1942年至1943年3月，圖靈在美國協助破譯工作；盡管德軍升級了密碼，但事實證明，圖靈的思想又一次成為了最得力的破譯工具。
據估計，圖靈的貢獻使密碼破譯工作縮短了兩年。這份功勞可謂功德無量，要知道，戰爭期間每年就有1100萬人死亡。據說溫斯頓·丘吉爾曾盛贊圖靈，說他的工作為二戰的勝利做出了最杰出的個人貢獻。對于一位性格略有些古怪的極客來說，這已經是很高的贊譽了！圖靈因為二戰時期的杰出功勞獲得了英王授予的不列顛帝國勛章（OBE），但是由于情報工作的保密性，他的功勞在接下來的三十年里一直不為人知。
二戰結束后，圖靈繼續發揮自己的才思，開展富有開創性的研究工作。他構想了世界上最早的計算機之一——自動計算機（Automatic Computing Engine，簡稱ACE）。當他知道恩師馬克斯·紐曼當上曼徹斯特大學（Manchester University）教授后，自己也進入了曼徹斯特大學，擔任講師的工作。任教期間，他一方面繼續開展數學研究工作，另一方面擴展了興趣范圍，研究了神經科學、個體發生學（10）和量子理論。圖靈是人工智能研究領域的先驅之一（我們會在后面的章節提到他的好幾個思想）。1951年，他因為圖靈機的研究工作而當選為倫敦皇家學會（Royal Society of London）的成員。他的大學同事并不知道，他在任教期間依然供職于英國通信總部（GCHQ，相當于國家安全局），繼續參與密碼破譯的工作，直到冷戰爆發。
1952年，圖靈向警方報告了一起入室盜竊案。他承認，行竊的人正是他以前的同性伴侶的朋友。但是同性戀在當時是非法的，因此圖靈被控以嚴重猥褻罪而遭到起訴。審訊期間，他的老朋友馬克斯·紐曼為他出庭作證，但是于事無補。圖靈不幸被定罪，他的選擇只有兩個，要么坐牢，要么接受“化學閹割”——注射女性荷爾蒙（雌激素）。他選擇了注射雌激素，為此不得不遭受乳房發育等藥物副作用的傷害。他不再具備參與保密工作的資格，不能再為英國政府通信總局工作。他的一舉一動——無論是外出度假，還是與外國科學家開展合作——都在國安人員的密切監視之下。
圖靈繼續開展研究，發表了更多關于個體發生學、量子理論和相對論的論文。他四處旅行，游歷了巴黎、雅典和科孚島（Corfu，位于希臘西北部，愛奧尼亞群島之一）。但他并不快樂。1954年，圖靈被發現死在家中，身邊放著咬了一口的蘋果。此前他一直在做電解實驗，身上可能殘留了化學物質，而蘋果表面檢測出了氰化鉀。圖靈的母親和他在通信總部的幾名同事認為，這是一起事故。警方的調查結論稱，他的死因是自殺。