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

圖靈機正式面世80年︰「離地」研究為人類帶來了電腦
我們想讓你知道的是

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

唸給你聽
powered by Cyberon

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
一個圖靈機模型。

不同圖靈機分別,在於它們擁有不同的可能狀態以及指令集——事實上,我們只需要看一部圖靈機的指令集,就知道它可以有甚麼狀態,因此可以說,圖靈機的指令集(以及一開始時紙帶上的內容)決定了它如何運作。

這些看似非常簡陋的圖靈機其實可以做非常多事情,圖靈在論文中舉了兩個圖靈機作例子︰一個可以在紙帶上不斷印出「01010101….」,另一個可以印出「001011011101111...」。事實上,我們也能設計出會進行加法、減法、乘法、除法、比較兩個數字大小…的圖靈機(在圖靈機中,數字可用符號「1」的數量來表示,例如用「111」代表3、「1111111」代表7,數字與數字之間則用符號「0」去分隔)。

通用圖靈機

圖靈的〈論可計算數〉沒有在此打住,正如上文所述,一部圖靈機的指令集可以抽述了它如何運作,因此圖靈就想到把圖靈機(的指令集)編碼,換言之,用不同的數字就可以表述不同的圖靈機——就這樣,每個圖靈機都獲得一個標準編號。

下一步,圖靈構造了一部特別的圖靈機,稱為「通用圖靈機」。通用圖靈機可以「扮演」不同的圖靈機——只要輸入某部圖靈機M的標準編號,它就可以像M一樣印出相同的符號序列。

如果上面的句子太過抽象,不妨換個(靈異一點的)說法︰有了通用圖靈機以後,理論上我們不再需要製造其他圖靈機——因為其他圖靈機都可以由「硬件」變成「軟件」,「附上」通用圖靈機來運作。

對,那就是為何我們打開手機、電腦上的計算數件,便能夠使用計數機的功能——現代電腦某程度上是一部通用圖靈機(當然,電腦沒有無限長的紙帶)。通用圖靈機成為現代電腦的理論模型,圖靈這篇論文也奠定了電腦科學、可計算性理論(computability theory)等學科的基礎。

當然,由紙上理論代為現實,中間還有一大段歷史發展,圖靈亦有參與,在此先行略過。(停機問題也是〈論可計算〉的重要結果,篇幅所限同樣略過。)

丘奇—圖靈論題

在圖靈之前,數學家——特別是關心數理邏輯的數學家——已經在思考如何嚴格定義「機械程序」或者「演算法」,因為缺乏這個定義的話,界定「形式系統」時會出現一個問題︰怎樣的符號變換規則可以接受?

哥德爾(Kurt Gödel)在1931年證明其著名的不完備定理時,引入了(原始)遞歸函數的概念,以便從數學角度討論形式系統,其後他跟英年早逝的埃爾布朗(Jacques Herbrand)將之發展成廣義遞歸函數。但要直到圖靈的論文面世後,哥德爾才認為人們能「精確及毫無疑問充足」地定義形式系統。

文首提到比圖靈稍早解決判定問題的丘奇,在他1936年的論文中使用了λ演算(λ-calculus)去地義何謂「λ可計算函數」。而對於任何(以自然數為定義域的)函數f(x),如果存在一部可以順序印出f(0), f(1), f(2)…的圖靈機,那麼這個函數就稱為「圖靈可計算函數」。

丘奇和圖靈證明了這三種函數——廣義遞歸函數、λ可計算函數及圖靈可計算函數——等價,換言之,雖然它們有非常不同的定義,但實際上還是一樣。〈論可計算數〉發表以後,也有各種計算模型出現,但沒有一個能夠超越圖靈機——它們所定義的函數,都是可以用圖靈機(或λ演算、廣義遞歸函數)去定義。

丘奇及圖靈認為,任何可以計算的函數,都是λ可計算/圖靈可計算函數,這稱為「丘奇—圖靈論題」。他們把「可以計算的函數」這個直觀概念,跟數學上有嚴格定義的「λ可計算/圖靈可計算函數」劃上等號,由於論題涉及直觀概念,本身無法以數學證明。

根據理論電腦科學這80年來的發展,丘奇—圖靈論題幾乎無人質疑︰即使電腦速度突飛猛進,能夠完成各種以往無法想像的任務,現實中我們仍然未能找到一個超越圖靈機的計算模型(理論上倒有一些,但不包括現時的量子電腦模型)。

未來發展會怎樣?不知道,可能他日人工智能的數學家、邏輯學家會發現到一個超越圖靈機的計算模型——而我們無法理解?或者明天就有人發現了?(當然我認為這極不可能。)

沒有〈論可計算數〉,我們也許還有「電腦」可用,但那些「電腦」應會截然不同,發展也慢得多。在圖靈機面世80年的今日,我只想介紹這個非常「離地」卻對人類歷史有深刻影響的故事。

相關文章︰

或許你會想看
更多『評論』文章 更多『科學』文章 更多『Kayue』文章
Loader