圖靈機正式面世80年︰「離地」研究為人類帶來了電腦

圖靈機正式面世80年︰「離地」研究為人類帶來了電腦

我們想讓你知道的是

80年前,圖靈發表〈論可計算數及其在判定問題上的一個應用〉,對電腦發展影響深遠。

1936年11月30日出版的《倫敦數學學會會刊》(Proceedings of the London Mathematical Society),有一篇標題看來平平無奇的文章︰〈論可計算數及其在判定問題上的一個應用〉(On computable numbers, with an application to the Entscheidungsproblem),作者是圖靈(Alan Turing)。

2012年,圖靈誕生100周年,學界將該年訂為「圖靈年」,舉辦活動以紀念其重大貢獻。2014年電影《模仿遊戲》亦講述了圖靈於二戰時協助破解德軍密碼的故事(雖然忽略了波蘭數學家的貢獻),相信不少人對圖靈的名字、貢獻及其因同性戀傾向被迫害的經歷略有所聞。

圖靈的眾多貢獻當中,最為重要的正是1936年這份論文,因為在文中他首次提出「圖靈機」這個概念——文中他稱為a-機器,a代表「自動」(automatic)——為現代電腦、電腦科學及計算理論奠下數學基礎。

當然,除圖靈以外,他之前及之後均有不少人對電腦發展貢獻良多。不過今日——〈論可計算數〉第一部份發表80周年(第二部份於同年12月23日發表),讓我們先看一看他的「圖靈機」為何如此重要。

數學基礎

一切源自一個貌似非常「離地」、與現實毫不相干的問題︰我們如何確定數學知識可靠?

19世紀,數學發展越來越抽象,因此亦出現了各種公理系統——公理是指被視作「不證自明」的命題,數學家以公理為基礙,再用邏輯推論出不同數學定理。但到了20世紀初,有批數學家(以及關心數學的哲學家)開始擔心數學知識不夠穩固,他們想確保由特定公理出發,不會推論出矛盾——假如有矛盾的話,數學就完了。

他們不是杞人憂天,當時集合論中出現了數個悖論,或會導致數學出現矛盾。幸運的話,有些悖論可以透過引入新概念去解決,例如自數學界出現「極限」的嚴格定義後,甚少人會認為「亞基里斯永遠無法追上烏龜」的芝諾悖論是個問題。

那個時候這批數學家大概分成三派,其中一派是數學家希爾伯特(David Hilbert)主導的「形式主義」。簡略來說,形式主義者希望藉由把數學還原成純粹符號的形式系統,再用(有限制的)數學去證明這個系統不會出現「0=1」之類的矛盾句,從而確保數學不會產生矛盾。

羅素(Bertrand Russell)及懷海德(Alfred Whitehead)三大冊《數學原理》(Principia Mathematica),則是從邏輯主義出發,嘗試以邏輯公理推導出整個數學系統——他們想的是,既然邏輯不可能自相矛盾,只要證明數學是由邏輯延伸出來,就可以確保數學一致。

兩人終告失敗(原因並非本文重點),不過書中改良自弗雷格(Gottlob Frege)的邏輯系統,促進了數理邏輯發展。其後邏輯學家整理出一套現稱為「一階邏輯」的系統,包含若干邏輯公理和推導規則,由此出發可以推導出不少已知的邏輯定理,是個很好用的系統。

判定問題

回到希爾伯特,他想完全將數學化約成一個僅有符號的形式系統(這方面羅素及懷海德貢獻了不少),只要按照規則,完全不懂數學、不知道符號意義的人也可以推演出「數學定理」,這樣就可以撇除人為錯誤(例如受直覺誤導)。

他又希望找到一套清晰的判定程序,去確認如何判斷一個邏輯公式是否屬於邏輯系統的定理,假如成功,下一個目標自然是判斷數學命題是否數學定理——這樣數學家就不用再苦苦思索那些懸而未決的數學猜想,只要一起運行這個「判定程序」,就可以獲得答案,簡單直接。

不過,希爾伯特於1928年提出的這個「判定問題」(Entscheidungsproblem),在1935至1936年期間,分別由數學家丘奇(Alonzo Church)及圖靈獨立得出答案︰不可能。

要解決判定問題,首先需要釐清一個概念︰何謂「清晰的判定程序」?當然,有一些條件非常明顯,例如程序必須是有限的——僅包含有限條規則、能夠在有限時間完成。程序當中的規則也必須極之簡單,以符合希爾伯特的要求。

舉個例,假如我要教一位小學生判定一個數字以否質數,可以利用他懂得「整數」、「除數」、「餘數」和「比較大小」等概念,去讓他按照程序執行,然後他就會發現7是質數、8不是質數、9不是質數…

但希爾伯特所要求的還要更少——執行規則的人只能夠辨認符號(不會把不同的符號混淆)、抄寫符號、按照規則把符號串轉換等,甚至不懂「加減乘除」等基本數學運算,也不會知道數學符號的意思。

圖靈機

終於回到圖靈的論文,在〈論可計算數〉中他設想以下一部機器,包含以下部份︰

  • 一條紙帶,這條紙帶分成一格一格的(好吧聽起來的確有點像廁紙),每格可以印一個符號。第一格的編號為0,然後是1、2、3…沒有盡頭,以 ◻ 表示空格。
  • 可以在紙帶上左右移動的讀寫頭,它每次能夠讀取所處位置那一格的內容(同一時間只可讀取一格),亦可以改變其內容——改寫其他符號或變成空格。
  • 會存在機器目前狀態(state)的狀態暫存器,每部機器的可能狀態數目有限,其中一個稱為「開始狀態」,就是機器一開始時所處的狀態。
  • 儲存所有規則的指令集,機器會根據其目前狀態以及讀寫頭當時讀取的方格內容來執行指令,進行下一步動作。

上述4個部份當中,決定機器如何運作的是指令集及狀態。為方便說明,以下機器的狀態以顏色表示,而符號只有0、1及◻(空格)。圖靈把指令限制在這個形式︰

  • 當處於A狀態並讀取到符號X時,寫入符號Y,移動讀寫頭,並轉至B狀態。

以下是一些例子︰

  • 當處於紅色狀態並讀取到符號0時,寫入符號1,讀寫頭左移一格,並轉至藍色狀態。
  • 當處於黃色狀態並讀取到符號1時,寫入符號1(即維持原狀),讀寫頭留在原處,並維持在紅色狀態。
  • 當處於藍色狀態並讀取到符號0時,清除符號(變成空格◻),讀寫頭右移一格,並轉至黃色狀態。

如果沒有適用的指令時,這部設想中的機器——後世稱為圖靈機——就會停止運作。

Turing_Machine_Model_Davey_2012
Photo Credit: Rocky Acosta, CC BY 3.0
一個圖靈機模型。

猜你喜歡

Tags: