忙碌的河狸

人們可以很容易計算4乘以3(4X3=12)，但是機器是怎樣計算4乘以3？圖靈(TURING)提
出一個計算模型(圖靈機)，它可以做這種計算。圖靈機由一條無限長度的紙帶子(帶
子上劃分成許多格子)，讀寫頭，控製器和字母組等組成。讀寫頭有讀寫功能：可以
從帶子上讀出數據，也可以往帶子上寫數據。控製器的功能是：把讀寫頭向左(或向
右)移動一格和改變圖靈機的工作狀態。設想我們要計算4乘以3，我們用一元數(
“1”)來表示數字，即4可以表示為4個1，4乘以3就可以如此表示在紙帶上(我們用
X分隔兩數字)：

1111X111

一圖靈機計算程序是這樣的：把讀寫頭向左移動至第一個空格，然後寫入*號：

*1111X111

然後把讀寫頭向右移動至第一個1，將1寫為空格：

*1111X11

然後把讀寫頭向左移動至X左邊第一個1，將1寫為A：

*111AX11

然後把讀寫頭向左移動至第一個空格，將1寫入空格：

1*111AX11

重複上述小循環，我們得到：

1111*AAAAX11

然後將A改為1：

1111*1111X11

重複上述大循環，我們得到：

111111111111*AAAAX

最後抹掉*AAAAX，我們得到計算結果12：

111111111111

上述圖靈機計算程序看起來很笨拙，但的確是在計算。圖靈機計算模型雖然簡單，
但它的功能和每秒運算數億次的電子計算機是一樣的。而且至今人們還沒有找到比
圖靈機功能更強的計算模型。

1962年，美國俄亥俄州立大學RADO教授提出“忙碌的河狸”問題：給出一N個狀態的
圖靈機，T(N)，從讀入空白紙帶(上麵全是“0”)開始，然後不斷向紙帶寫出1；在
圖靈機停止時，紙帶上的1的最大數目M是多少？即

M(N) = MAX(ONES IN T(N) )

這時，圖靈機的工作就像忙碌的河狸。當N比較大時，上述函數是不可計算的。這是
一個觀念上的突破。以往人們認為，隻要函數是準確定義的，它總是可以計算的。

假設B是一可以計算M(N)的圖靈機，它有Q個狀態。於是B應該從紙帶上讀入整數N然
後寫出M(N)。N和M(N)可以是二進製數。設A是一可以轉換空白紙帶到整數N的圖靈機，
它有LOG(N)個狀態(這裏LOG是對數)。設C是一可以轉換二進製數到一元數(“1”)的
圖靈機，它有R個狀態。於是三個圖靈機並在一起，ABC，是一可以從讀入空白紙帶
開始而計算M(N)的圖靈機，但它隻有LOG(N)+Q+R個狀態。又設X是一可以計算M(N)的
圖靈機，它有N個狀態。於是對於任何N，隻要 N > LOG(N)+Q+R，ABC可以和X一樣計
算M(N)，但有較少的狀態。實際上，這是不可能的，因為M(N)是單調增函數。所以
B是不存在的，M(N)是不可計算的。

盡管M(N)是不可計算，人們還是探討圖靈機計算程序，試圖寫出盡可能大的數。作
為遊戲，世界記錄還在不斷刷新。