1936 年今日 圖靈機論文宣讀，作者僅 24 歲

1936 年 11 月 12 日，Alan Turing 的論文在倫敦數學會宣讀

1936 年 11 月 12 日，英國數學家 Alan Turing 的論文「On Computable Numbers, with an Application to the Entscheidungsproblem」在倫敦數學會宣讀。據論文刊出時的頁首註明，這篇論文在 1936 年 5 月 28 日收稿，11 月 12 日宣讀。當時 Alan Turing 是劍橋大學 King's College 的院士，年僅 24 歲。

據英國劍橋的計算機歷史中心 Centre for Computing History 整理，論文其後分兩部分刊於《倫敦數學會會刊》，第一部分在 1936 年 11 月 30 日刊出，第二部分在 12 月 23 日刊出。

一條紙帶、一個讀寫頭、一套指令

論文描述一部抽象的「計算機器」，只有三個部分：一條分成格子、向兩邊無限延伸的紙帶，作為機器的記憶；一個沿紙帶移動、能在格子讀寫符號的讀寫頭；以及一套決定讀寫頭如何運作的指令。

據 Centre for Computing History 的介紹，機器看似簡單，Alan Turing 卻證明它足以執行任何演算法，無論多複雜。論文其中一節題為「The universal computing machine」，這部機器今天一般稱為「通用圖靈機」，其概念是所有電腦的基礎。

論文回答了數學家 Hilbert 的問題

論文的標題提到「Entscheidungsproblem」，即德國數學家 David Hilbert 提出的「判定問題」：是否存在一套通用方法，能判斷任何數學命題可否被證明。Alan Turing 在論文中寫道，他證明了這個問題「沒有解」。

論文同時承認，美國數學家 Alonzo Church 在一篇近期論文中提出「effective calculability」的概念，與他的「computability」等價但定義方式很不同，並就判定問題得出相近結論。據 Wikipedia，Alan Turing 其後在 1938 年取得普林斯頓大學博士學位，二戰期間在 Bletchley Park 主管 Hut 8，破解德國海軍的 Enigma 密碼。

來源

• On Computable Numbers, with an Application to the Entscheidungsproblem（論文原文轉錄，經倫敦數學會許可）
• Alan Turing invents the principle of the modern computer（Centre for Computing History）
• Alan Turing（Wikipedia）