深入理解運算原理｜從簡單的機器到無所不能的程式

四處皆通用

|

263

這意謂著規則 110 可以執行循環標籤系統的模擬物，而這個模擬物又正在執行一般標籤

系統的模擬物，而要再次強調的是，這個一般標籤系統的模擬物，還正在執行通用圖靈

機的模擬物；雖然這不是實現通用運算有效率的作法，但依然讓人對這類簡單的細胞自

動機的技術，有著印象深刻結果。

沃夫瑞的 2, 3 圖靈機

為了完成我們簡單通用系統的旋風之旅，這裡有個比規則 110 更簡單的例子：

沃夫瑞

的

2, 3

圖靈機

（

Wolfram's 2,3 Turing machine

）。它的名稱來自它自己的兩種狀態和 3 個

字元（

a

、

b

、空白），也就是說它只有 6 條規則：

這種圖靈機很罕見的原因在於它沒有接受狀態，所以它永遠不會停止，但

這主要是技術細節。我們還是可以從不會停止的機器得到結果，作法是觀

察某些行為（例如磁帶上特定的字元模式的外觀），並將這些視為目前磁

帶包含有用輸出的指示。

沃夫瑞的 2, 3 圖靈機似乎沒有足夠的能力來支援通用運算，但在 2007 年，沃夫瑞研

究公司對外公佈，任何能證明沃夫瑞的 2, 3 圖靈機是通用的人，即可獲得 25,000 美

元的獎金，而在當年稍後，艾力斯 • 史密斯（Alex Smith）因為成功證明而要求

這筆獎金。和規則 110 相同的是，史密斯證明了這部機器可以模擬任何循環標籤系

統；他的證明非常詳細，而且也可以在沃夫瑞研究公司的網站完整看到（

http://www.

wolframscience.com/prizes/tm23/

）。