/ 通用圖靈機發(fā)明者 /
圖靈從小就表現(xiàn)出了過人的才華,對數(shù)字和智力游戲十分著迷,之后便一發(fā)不可收。
1931 年,圖靈進入劍橋大學學習數(shù)學。1934 年以優(yōu)異成績畢業(yè)后,圖靈他在概率論方面的貢獻,被選為劍橋大學國王學院的研究員。
在數(shù)學家看來,解決問題的“有效”方法,其實就是僅需要一個人類數(shù)學文員(mathematical clerk)死記硬背就能搞定的方法。在圖靈生活的那個年代,那些死記硬背的工人實際上被稱為“人類計算機”,他們完成了一些后來由電子計算機完成的工作。
決策問題(The Entscheidungsproblem)尋求一種有效的方法來解決基本數(shù)學問題,即判斷哪些數(shù)學命題在給定的形式數(shù)學系統(tǒng)中是可證明的,哪些是不可證明的。判斷這一點的方法被稱為決策方法。
1936 年,圖靈的開創(chuàng)性論文《論可計算數(shù)及其在判定問題中的應用》
(On Computable Numbers, with an Application to the Entscheidungsproblem)
被美國數(shù)理邏輯學家阿隆佐·邱奇(Alonzo Church)推薦發(fā)表。
在論文中,圖靈提出了著名的“圖靈機”的設想,將邏輯中的任意命題用一種通用的機器來表示和計算,并能按照一定的規(guī)則推導出結論,其推斷結果通俗來講則是:圖靈機能計算的函數(shù)就是可計算的函數(shù),反之則是不可計算的函數(shù)。
邱奇是圖靈之后的博士導師,盡管他早于圖靈得出了相同的結論,但圖靈的論證更易于理解和直觀,通用(圖靈)機的概念也更新穎。圖靈的方法對新興的計算科學有著深遠的意義。
1937-1938 年,圖靈在普林斯頓大學度過了大部分時間,在邱奇的指導下獲取了博士學位。圖靈的論文介紹了超計算的概念,在圖靈機加上了預言機,讓研究圖靈機無法解的問題變得可能。
/ 密碼破譯者 /
從普林斯頓大學畢業(yè)后,圖靈回到了倫敦大學國王學院,隨后加入了英國政府通信總部。
而在此幾周之前,波蘭政府向英國和法國提供了波蘭破解德國軍方用于加密無線電通信的主要密碼機 Enigma 的細節(jié)。