圖靈機正式面世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

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