跳轉到

03.1 圖靈 1936：通用圖靈機的數學抽象#

一九三五年春天，劍橋國王學院年輕的數學家阿蘭·圖靈（Alan Turing）在倫敦出席了Max Newman 講授希爾伯特判定問題（Entscheidungsproblem）的系列講座。Newman 在課堂上說，判定問題的核心在於：是否存在一種機械的程序，能夠在有限步驟內判定任何一個數學命題的真偽？這個問題是德國數學家大衛·希爾伯特（David Hilbert）「數學基礎計畫」的最後一塊拼圖。

歷史的脈絡要拉回更早。一九三一年，庫爾特·哥德爾（Kurt Gödel）發表不完備定理，證明任何足夠豐富的一致數學系統都存在既無法證明也無法證偽的命題，摧毀了希爾伯特「完備性」的夢想。但希爾伯特問題還有一半未死：即使命題可能不可判定，「可判定性」本身是否可 definitional 化？要回答這個問題，數學家必須先回答一個更原始的疑問——什麼是「機械的程序」？

哥德爾用「可遞迴可枚舉函數」回答，普林斯頓的阿隆佐·邱奇（Alonzo Church）用 λ-演算回答。而圖靈給出了一個截然不同、卻影響最深遠的回答：他把「計算」還原為一個人在紙上做算術的最基本動作。

圖靈機的誕生#

圖靈想：一個計算員在紙上算數，其實只會做幾件事——看一眼紙上的格子、在腦中每次只考慮一個狀態、然後擦掉或寫下一個符號、向左或向右移動視線。把這些動作抽象化，就得到一台假想的機器：

  • 一條無限長的紙帶，分成一格格方格，可寫入有限種符號；
  • 一個讀寫頭，一次讀寫一格；
  • 一張有限的狀態表，依「當前狀態＋讀到什麼」決定「寫什麼、往哪移、下一狀態」。

這台機器笨拙至極，卻能計算邱奇-圖靈意義上「一切可計算之物」。更驚人的是第四章節的概念躍遷：圖靈證明可以造出一台「通用機器」（Universal Machine），它的紙帶上存放另一台機器的描述（狀態表的編碼），然後模擬那台機器的每一步。

這就是「一台機器讀取描述、執行任意機器」的想法——在數學上，這正是四十年後「儲存程式電腦」的雛形：程式與資料一樣，都是可以被讀取、被執行的資訊。圖靈不是在造電腦，他在證明定理；但定理裡藏著整個資訊時代的血統書。

一九三六年四月，圖靈向倫敦數學學會提交論文〈論可計算數及其在判定問題上的應用〉（On Computable Numbers, with an Application to the Entscheidungsproblem），十一月正式發表。證明的核心是「停機問題」（Halting Problem）：不存在任何演算法可以判定任意程式是否會停止——因為若存在，把「不停機」的判斷套回自身即產生對角矛盾。這是哥德爾自指結構的機器化版本。

邱奇與普林斯頓#

命運的巧合是：邱奇的博士學生幾乎同時證明了同樣的否定結果，而且邱奇的論文先發表。同為劍橋出身的紐曼讀了邱奇的文章後寄給圖靈，圖靈六週內補完了自己的證明，兩人路線被並稱「Church-Turing 命題」：凡「直觀可計算」者，即等同於圖靈機可計算者。

一九三六到一九三八，圖靈赴普林斯頓在邱奇門下攻讀博士。但他與邱奇的風格全然不同：邱奇嚴謹、拘謹、論文簡短到令學生苦惱；圖靈直覺、糾纏於具體構造、喜歡用手推演機器的每一步。馮·諾伊曼（John von Neumann）當時在普林斯頓，讀了圖靈的論文皮毛便看出其分量，後來甚至邀請他擔任自己的研究助理——被圖靈婉拒，他選擇回劍橋。

經濟與制度的力量也在此默默推動：普林斯頓的高等研究院以高薪網羅歐洲數學家；英國則以獎學金把青年送到新大陸。知識的流動靠的不是電腦，而是郵輪與獎學金。

性格與文化：跑步的孤僻天才#

圖靈畢生最鮮明的形象之一是跑步。在劍橋，他常獨自繞著河岸長跑；在普林斯頓，他沿著街道一圈圈地繞。一九四八年他跑出 2 小時 46 分的馬拉松成績，距當年奧運選拔標準只差幾分鐘，若非受傷幾乎可入選英國隊。跑步是他思考的方式，也是他與世界保持距離的方式——他從小就不是「合群」的人，劍橋國王學院的自由風氣、學生俱樂部的辯論與怪人才容得下他。

這份孤僻，日後成為著名的悲劇伏筆：他是同性戀，在戰後英國仍屬刑事罪的年代被迫接受化學閹割，一九五四年死於氰化物中毒，年僅四十一歲。但一九三六年那篇論文的價值，當時幾乎無人真正看見——它不被視為工程藍圖，而只是一篇解決邏輯問題的數學論文。

歷史的弔詭就在這裡：決定二十世紀技術路徑的，往往不是工程師，而是數學家先寫下「可行性上限」的證明。圖靈證出了「通用性」的存在與其極限（停機問題不可解），工程師於是知道不必也不該追求不可能的萬能解法，只需造出一台模擬一切的機器。思想先於機器，證明先於工程——這是電腦的第一條定律。