論可計算數及其在判定問題上的應用
圖靈設想出最簡單的機器——一個在紙帶上讀寫的讀寫頭——以此定義了「計算」本身，並證明：有些問題，任何機器都永遠無法回答。
在任何電腦出現之前，圖靈就描述了一臺「能算一切」的最簡單的機器——並用它證明：有些問題，任何電腦都永遠無法回答。
把這個想法拆開看
想像一條長長的紙帶，分成一個個方格；一個小小的讀寫頭，一次能讀、寫一個方格；外加一本薄薄的規則手冊。每條規則都說：若你處在某某狀態、讀到某某符號，就寫下這個、向左或向右挪一格、並切換到那個狀態。整臺機器，就這麼多。圖靈的論斷令人吃驚：凡是能用一套確定程序算出來的，都能由這樣一臺簡單的機器做到。
接著是神來之筆。任何機器的規則手冊，本身也能寫成一串符號——於是它能被寫到一條紙帶上，餵給另一臺機器。圖靈造出一臺「通用」機：它讀入對任何別的機器的描述，然後表現得與那臺機器一模一樣。這就是軟體：同一臺設備，全看你裝入哪一份描述，便成了文字處理器、計算機，或一個遊戲。這一切，他在世人造出第一臺之前十年就已設想出來。
它從哪裡來
1935 年，22 歲的圖靈——劍橋國王學院的一名研究員——旁聽了馬克斯·紐曼關於數理邏輯諸多未決問題的講課。其中之一，便是希爾伯特的判定問題：它要找一套機械程序，能對任意一個數學命題，判定它是否由公理推得。圖靈把「機械」二字當了真：要回答它，他得先把「機器究竟能做什麼」說清楚。
他在 1936 年完成論文——隨後得知，美國邏輯學家阿隆佐·邱奇剛用一套全然不同的方法得到了同樣的結論。圖靈的工作是獨立的，且已在付印；他補上一篇附錄，證明兩條進路彼此吻合，不久便動身去普林斯頓，師從邱奇。他證明的核心意象——一個人被簡化為一名不知疲倦、只照規則辦事的抄寫員——在不到十五年裡，就變成了他當初只在頭腦裡想像的那臺真機器。
它為何重要
它一舉做成了兩件相反的事。它為「機器之所能」劃下一道清晰的界：證明某些再清楚不過的問題——比如「這個程式會不會停下來？」——並沒有一個通用的機械答案，於是「把數學完全自動化」的夢想，根本不可能。而就在同一筆之下，它描述了那臺通用機：證明了一臺通用設備，原則上可以運行任何程式。每一臺電腦，都是這一個想法的實現；它的界限與它的偉力，是在同一篇論文裡、被一同發現的。
一個類比
想像一位書記員坐在桌前，面前是一條沒有盡頭的紙帶，手邊是一本薄薄的規則手冊。他並不理解題目；他只是讀眼前這一格、查出對得上的那條規則、寫一筆、往旁邊挪一格，然後重複。現在請注意：規則手冊本身，也不過是寫出來的字。於是你大可把「任何另一位書記員的規則手冊」遞給他，請他照著模仿——一位書記員，便能頂替所有人。那個無解的問題，無非是：「給定一位書記員和他的起始頁，他到底會不會有放下鉛筆的一刻？」沒有哪本手冊能永遠答得出。試試下面這臺小機器——它走 14 步就停，可它的同類，也許會永遠跑下去。
它落在何處
這是本館「資訊」敘事的拱心石。喬治·布爾（1854）把邏輯變成了代數；庫爾特·哥德爾（1931）證明了：沒有任何形式系統能證明關於算術的全部真理——而圖靈的機器，把這條界限改寫成人人都能想像的樣子。他的通用機，正是馮·紐曼 1945 年報告變成真硬體的那張藍圖；而它來回搬運的那個「位元」，正是香農（1948）學會去度量的東西。十四年後，圖靈自己的 1950 年論文追問了續篇：不是這些機器不能做什麼，而是它們究竟能否思考。
開篇 · 可計算數
The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
§1–§2 · 計算機器
§6 · 通用計算機器
It is possible to invent a single machine which can be used to compute any computable sequence.
§11 · 判定問題
There can be no general process for determining whether a given formula U of the functional calculus K is provable.