2013年9月30日 星期一

杜林

生平

Alan Mathison Turing 1912年生於倫敦,是這個家庭的第二個孩子。他的父親是印度Bri tish Civil Service的成員,但他的母親認為這樣的環境不利於孩子的成長。於是Alan和哥哥在英國的一個領養家庭中度過了他們的童年,除了偶爾回家看看,大部分時間和父母分開。

杜林機器與杜林測試

1936年時,杜林提出了一個假想性的計算工具,稱為杜林機器(Turing machine),這個機器有一個長條型、無窮多格的儲存磁帶,每一格位置是空白或一個符號;附帶在磁帶上的是一個可讀寫的磁頭,它可以在磁帶的格子往左或往右,並在每次移動時讀、寫或擦拭該格子;還有一個有限狀態控制機,可運用狀態的改變,配合目前磁頭所在的位置,來決定這些移動讀寫的動作。

這樣一個簡單的機器,它的運算功力竟然相當於今天的數位計算機,換句話說,目前數位計算機可以運算的方法,我們都可以在杜林機器上實現,很神奇吧!

杜林當初也用這個抽象型的機器,證明了某些命題的不可決定性,這在數學及邏輯領域上,都算是二十世紀裡很重要的里程碑。

杜林獎

象徵最崇高學術桂冠的諾貝爾獎,從1901年開始頒發,根據瑞典發明家諾貝爾的遺囑,設有物理、化學、生理醫學、文學及和平等五個獎項;自1969年起,增設了經濟學諾貝爾獎。不知您是否曾有這樣的疑問,為什麼諾貝爾獎沒有數學獎項呢?

坊間流傳的說法是,當初諾貝爾的夫人,曾經和瑞典一位很有成就的數學家米塔雷符勒有過一段婚外情,所以諾貝爾決定不設數學獎項。


英國數學家亞蘭杜林(Alan Turing,1912-1954),雖然無緣在有生之年得到諾貝爾獎,但後人為了紀念他在數位計算理論貢獻而設立的杜林獎(Turing Award),已被公認是計算機科學領域最崇高的獎項。

杜林獎從1966年開始頒發,受獎人都是對計算機科學有深遠影響的大師級學者。例如,在計算複雜度理論上有卓越貢獻的庫克(Cook)、C程式語言的創始人理奇(Ritchie)、Unix作業系統製作人湯普生(Thompson)及資料庫管理系統的先驅卡德(Codd)等。