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