這些看似非常簡陋的圖靈機其實可以做非常多事情，圖靈在論文中舉了兩個圖靈機作例子︰一個可以在紙帶上不斷印出「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年的今日，我只想介紹這個非常「離地」卻對人類歷史有深刻影響的故事。

相關文章︰

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