如何理解圖靈機？

1、小蟲的比喻

我們不妨考慮這樣一個問題。假設一個小蟲在地上爬，那么我們應該怎樣從小蟲信息處理的角度來建立它的模型？

首先，我們需要對小蟲所在的環(huán)境進行建模。我們不妨就假設小蟲所處的世界是一個無限長的紙帶，這個紙帶上被分成了若干小的方格，而每個方格都僅僅只有黑和白兩種顏色。很顯然，這個小蟲要有眼睛或者鼻子或者耳朵等等感覺器官來獲得世界的信息，我們不妨把模型簡化，假設它僅僅具有一個感覺器官：眼睛，而且它的視力短得可憐，也就是說它僅僅能夠感受到它所處的方格的顏色。因而這個方格所在的位置的黑色或者白色的信息就是小蟲的輸入信息。

另外，我們當然還需要為小蟲建立輸出裝置，也就是說它能夠動起來。我們?nèi)匀豢紤]最簡單的情況：小蟲的輸出動作就是往紙帶上前爬一個方格或者后退一個方格。

僅僅有了輸入裝置以及輸出裝置，小蟲還不能動起來，原因很簡單，它并不知道該怎樣在各種情況下選擇它的輸出動作。于是我們就需要給它指定行動的規(guī)則，這就是程序！假設我們記小蟲的輸入信息集合為I={黑色，白色}，它的輸出可能行動的集合就是：O={前移，后移}，那么程序就是要告訴它在給定了輸入比如黑***況下，它應該選擇什么輸出。因而，一個程序就是一個從I 集合到O 集合的映射。我們也可以用列表的方式來表示程序，比如： 程序1：

輸入輸出

黑色前移

白色后移

這個程序非常簡單，它告訴小蟲當讀到一個黑色方格的時候就往前走一個方格，當讀到一個白色方格的時候就后退一個格。

我們不妨假設，小蟲所處的世界的一個片斷是：黑黑黑白白黑白……，小蟲從左端開始。 那么小蟲讀到這個片斷會怎樣行動呢？它先讀到黑色，然后根據(jù)程序前移一個方格，于是就會得到另外一個黑色信息，這個時候它會根據(jù)程序再次前移一個方格，仍然是黑色，再前移，這個時候就讀到白色方格了，根據(jù)程序它應該后退一個格，這個時候輸入就是黑色了，前移，白色，后移……，可以預見小蟲會無限的循環(huán)下去。

然而，現(xiàn)實世界中的小蟲肯定不會這樣傻的在那里無限循環(huán)下去。我們還需要改進這個最簡

單的模型。首先，我們知道小蟲除了可以機械地在世界上移動以外，還會對世界本身造 ……

開始

成影響，因而改變這個世界。比如蟲子看到旁邊有食物，它就會把那個東西吃掉了。在我們這個模型中，也就相當于我們必須假設小蟲可以改寫紙帶上的信息。因而，小蟲可能的輸出動作集合就變成了：O={前移，后移，涂黑，涂白}。這個時候，我們可以把程序1改為比如： 程序2：

輸入輸出

黑前移

白涂黑

紙帶是黑黑白白黑……，小蟲會怎樣行動呢？下面的圖表示出了這個例子中每一步小蟲的位置（標有圓點的方格就是小蟲的當前位置），以及紙帶的狀況。

開始：小蟲在最左邊的方格，根據(jù)程序的第一行，讀入黑色應該前移。

第二步：仍然讀入黑，根據(jù)程序的第一行，前移。

第三步：這個時候讀入的是白色，根據(jù)程序的第二行，應該把這個方格涂黑，而沒有其他的動作。假設這張圖上方格仍然沒有涂黑，而在下一時刻才把它表示出來。

第四步：當前方格已經(jīng)是黑色的，因此小蟲讀入黑色方格，前移。

第五步：讀入白色，涂黑方格，原地不動。

第六步：當前的方格已經(jīng)被涂黑，繼續(xù)前移。

第七步：讀入黑色，前移

小蟲的動作還會持續(xù)下去……。我們看到，小蟲將會不停的重復上面的動作不斷往前走，并會把所有的紙帶涂黑。

顯然，你還可以設計出其他的程序來，然而無論你的程序怎么復雜，也無論紙帶子的情況如何，小蟲的行為都會要么停留在一個方格上，要么朝一個方向永遠運動下去，或者就是在幾個方格上來回打轉(zhuǎn)。然而，無論怎樣，小蟲比起真實世界中的蟲子來說，還有一個致命的弱點：那就是如果你給它固定的輸入信息，它都會給你固定的輸出信息！因為我們知道程序是固死的，因此，每當黑色信息輸入的時候，無論如何它都僅僅前移一個方格，而不會做出其他的反應。它似乎真的是機械的！

如果我們進一步更改小蟲模型，那么它就會有所改進，至少在給定相同輸入的情況下，小蟲會有不同的輸出情況。這就是加入小蟲的內(nèi)部狀態(tài)！我們可以作這樣的一個比喻：假設黑色方格是食物，蟲子可以吃掉它，而當吃到一個食物后，小蟲子就會感覺到飽了。當讀入的信息是白色方格的時候，雖然沒有食物但它仍然吃飽了，只有當再次讀入黑色時候它才會感覺到自己饑餓了。因而，我們說小蟲具有兩個內(nèi)部狀態(tài)，并把它內(nèi)部狀態(tài)的集合記為：S={饑餓，吃飽}。這樣小蟲行為的時候就會不僅根據(jù)它的輸入信息，而且也會根據(jù)它當前的內(nèi)部狀態(tài)來決定它的輸出動作，并且還要更改它的內(nèi)部狀態(tài)。而它的這一行動仍然要用程序控制，只不過跟上面的程序比起來，現(xiàn)在的程序就更復雜一些了，比如：

程序3：

輸入當前內(nèi)部狀態(tài)輸出下時刻的內(nèi)部狀態(tài)

黑饑餓涂白吃飽

黑吃飽后移饑餓

白饑餓涂黑饑餓

白吃飽前移吃飽

這個程序復雜多了，有四行，原因是你不僅需要指定每一種輸入情況下小蟲應該采取的動作，而且還要指定在每種輸入和內(nèi)部狀態(tài)的組合情況下小蟲應該怎樣行動?？纯次覀兊南x子在讀入黑白白黑白……這樣的紙帶的時候，會怎樣？仍然用下面的一系列圖來表示，灰色的圓點表示饑餓的小蟲，白色的圓點表示它吃飽了。為了清晰，我們把小蟲將要變成的狀態(tài)寫到了圖的下一行。

假定它仍然從左端開始，而且開始的時候小蟲處于饑餓狀態(tài)。這樣讀入黑色，當前饑餓狀態(tài)，根據(jù)程序第一行，把方格涂白，并變成吃飽（這相當于把那個食物吃了，注意吃完后，小蟲并沒動）。

第二步：當前的方格變成了白色，因而讀入白色，而當前的狀態(tài)是吃飽狀態(tài)，那么根據(jù)程序中的第四條前移，仍然是吃飽狀態(tài)；

第三步：讀入白色，當前狀態(tài)是吃飽，因而會重復第二步的動作。

涂白方格，變成吃飽

前移，仍然吃飽

前移，保持吃飽

第四步：仍然重復上次的動作。

第五步：讀入黑色，當前狀態(tài)是吃飽，這時候根據(jù)程序的第二行應該后移方格，并轉(zhuǎn)入饑餓狀態(tài)；

第六步：讀入白色，當前饑餓狀態(tài)，根據(jù)程序第三行應該涂黑，并保持饑餓狀態(tài)（各位注意，這位小蟲似乎自己吐出了食物?。?/p>

第七步，讀入黑色，當前饑餓，于是把方格涂白，并轉(zhuǎn)入吃飽狀態(tài)（呵呵，小蟲把剛剛自己吐出來的東西又吃掉了?。?/p>

第八步，讀入白色，當前吃飽，于是前移，保持吃保狀態(tài)。

這時候跟第四步的情況完全一樣了，因而小蟲會完全重復5、6、7、8步的動作，并永遠循環(huán)下去。似乎最后的黑色方格是一個門檻，小蟲無論如何也跨越不過去了。

小蟲的行為比以前的程序復雜了一些。盡管從長期來看，它最后仍然會落入機械的循環(huán)或者無休止的重復。然而這從本質(zhì)上已經(jīng)與前面的程序完全不同了，因為當你輸入給小蟲白色信息的時候，它的反應是你不能預測的！它有可能涂黑方格也有可能前移一個。當然前提是你不能打開小蟲看到它的內(nèi)部結(jié)構(gòu)，也不能知道它的程序，那么你所看到的就是一個不能預測的滿地亂爬的小蟲。如果小蟲的內(nèi)部狀態(tài)數(shù)再增多呢，那么它的行為會更加的不可預測！ 好了，如果你已經(jīng)徹底搞懂了我們的小蟲是怎么工作的，那么你已經(jīng)明白了圖靈機的工作原理了！因為從本質(zhì)上講，最后的小蟲模型就是一個圖靈機！