圖靈機正式面世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及◻（空格）。圖靈把指令限制在這個形式︰

• 當處於Ａ狀態並讀取到符號Ｘ時，寫入符號Ｙ，移動讀寫頭，並轉至Ｂ狀態。

以下是一些例子︰

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

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

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年的今日，我只想介紹這個非常「離地」卻對人類歷史有深刻影響的故事。

相關文章︰

• 數學家哈代的金句與「無用」的數學
• 西方邏輯學簡史︰由亞里士多德到二十世紀
• 用邏輯系統就能判斷論證對確嗎