正文

忙碌的河狸

(2022-10-09 13:24:37) 下一個

人們可以很容易計算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)是不可計算,人們還是探討圖靈機計算程序,試圖寫出盡可能大的數。作
為遊戲,世界記錄還在不斷刷新。

 

[ 打印 ]
閱讀 ()評論 (0)
評論
目前還沒有任何評論
登錄後才可評論.