圖靈機的組成：

1.一條無限長的紙帶 TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0，1，2，。.. ，紙帶的右端可以無限伸展。

2.一個讀寫頭 HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，并能改變當前格子上的符號。

3.一套控制規則 TABLE。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態寄存器的值，令機器進入一個新的狀態。

4.一個狀態寄存器。它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，并且有一個特殊的狀態，稱為停機狀態。參見停機問題。

關于圖靈機的模型介紹

圖靈機的模型介紹雖然有些無趣，不過請堅持看下去，我會在下面運用大家比較好理解的形式重新解釋的。在這里你僅僅需要認識它的輪廓。一個圖靈機是形如下面的一個裝置：

這個裝置由下面幾個部分組成：一個無限長的紙帶，一個讀寫頭。（中間那個大盒子），內部狀態（盒子上的方塊，比如A，B，E，H ），另外，還有一個程序對這個盒子進行控制。這個裝置就是根據程序的命令以及它的內部狀態進行磁帶的讀寫、移動。它工作的時候是這樣的：從讀寫頭在紙帶上讀出一個方格的信息，并且根據它當前的內部狀態開始對程序進行查表，然后得出一個輸出動作，也就是是否往紙帶上寫信息，還是移動讀寫頭到下一個方格。程序也會告訴它下一時刻內部狀態轉移到哪一個。

具體的程序就是一個列表，也叫做規則表，是這樣的：

當前內部狀態s 輸入數值i 輸出動作o 下一時刻的內部狀態s‘

B 1 前移C

A 0 往紙帶上寫1 B

C 0 后移A

… … … …

因此，圖靈機只要根據每一時刻讀寫頭讀到的信息和當前的內部狀態進行查表就可以確定它下一時刻的內部狀態和輸出動作了。

圖靈機就是這么簡單！不可思議吧？而只要你變化它的程序（也就是上面的規則表），那么它就可能為你做任何計算機能夠完成的工作。因此可以說，圖靈機就是一個最簡單的計算機模型！

也許，你會覺得圖靈機模型太簡單，怎么可能完成計算機的復雜任務呢？問題的關鍵是如何理解這個模型。
#e#

如何理解圖靈機？

1、小蟲的比喻

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

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

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

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

輸入輸出

黑色前移

白色后移

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

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

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

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

開始

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

輸入輸出

黑前移

白涂黑

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

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

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

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

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

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

第六步：當前的方格已經被涂黑，繼續前移。

第七步：讀入黑色，前移

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

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

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

程序3：

輸入當前內部狀態輸出下時刻的內部狀態

黑饑餓涂白吃飽

黑吃飽后移饑餓

白饑餓涂黑饑餓

白吃飽前移吃飽

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

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

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

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

涂白方格，變成吃飽

前移，仍然吃飽

前移，保持吃飽

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

第五步：讀入黑色，當前狀態是吃飽，這時候根據程序的第二行應該后移方格，并轉入饑餓狀態；

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

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

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

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

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

2、如何理解圖靈機模型

剛才用小蟲說明了圖靈機的工作原理，相信你的第一個反映就是，這樣的模型太簡單了！他根本說明不了現實世界中的任何問題！下面，我就要試圖說服你，圖靈機這個模型是偉大的！ 首先，我想說的是，其實我們每一個會決策、會思考的人就可以被抽象的看成一個圖靈機。 前移，保持吃飽

涂白，轉入吃飽

前移，保持吃飽

后移，變成饑餓

涂黑，保持饑餓

為什么可以做這種抽象呢？首先我們可以考慮擴展剛才說的小蟲模型。因為小蟲模型是以一切都簡化的前提開始的，所以它的確是太太簡單了。然而，我們可以把小蟲的輸入集合、輸出行動集合、內部狀態集合進行擴大，這個模型就一下子實用多了。首先，小蟲完全可以處于一個三維的空間中而不是簡簡單單的紙帶。并且小蟲的視力很好，它一下子能讀到方圓500米的信息，當然，小蟲也可以擁有其他的感覺器官，比如嗅覺、聽覺等等，而這些改變都僅僅是擴大了輸入集合的維數和范圍，并沒有其他更本質的改變。同樣道理，小蟲可能的輸出集合也是異常的豐富，它不僅僅能移動自己，還可以盡情的改造它所在的自然界。進一步的，小蟲的內部狀態可能非常的多，而且控制它行為的程序可能異常復雜，那么小蟲會有什么本事呢？這就很難說了，因為隨著小蟲內部的狀態數的增加，隨著它所處環境的復雜度的增加，我們正在逐漸失去對小蟲行為的預測能力。但是所有這些改變仍然沒有逃出圖靈機的模型：輸入集合、輸出集合、內部狀態、固定的程序！就是這四樣東西抓住了小蟲信息處理的根本。

我們人能不能也被這樣的抽象呢？顯然，輸入狀態集合就是你所處的環境中能夠看到、聽到、聞到、感覺到的所有一起，可能的輸出集合就是你的每一言每一行，以及你能夠表達出來的所有表情動作。內部狀態集合則要復雜得多。因為我們可以把任意一個神經細胞的狀態組合看作是一個內部狀態，那么所有可能的神經細胞的狀態組合將是天文數字！

似乎你會說，這個模型根本不對，還有很多思維本質的東西沒有概括進去。比如記憶問題，人有記憶，圖靈機有么？其實，只要圖靈機具有了內部狀態，它就相應的具有了記憶。比如上面講到的具有饑餓和吃飽兩種狀態的小蟲就會記住它所經歷過的世界：如果吃到食物就用吃飽狀態來“記住”吃過的食物。什么是記憶呢？假如你經歷了一件事情并記住了它，那么只要你下一次的行動在相同條件下和你記住這件事情之前的行動不一樣了，就說明該事情對你造成了影響，也就說明你確實記住了它。

學習的問題反映在模型中了么？學習是怎么回事兒呢？似乎圖靈機模型中不包括學習，因為學習就意味著對程序的改變，而圖靈機是不能在運行過程中改變它的程序的。然而，我們不難假設，你實際上并不能打開一個人的腦袋來看，所以它的實際程序規則你是不知道的。很有可能一個圖靈機的規則沒有改變，只不過激活了它的某些內部狀態，因而它的行為發生了本質上的變化，盡管給它相同的輸入，它給出了完全不同的輸出，因而在我們看來，它似乎會學習了！而實際上，這個圖靈機的程序一點都沒變。

還有很多很多現象似乎都能被圖靈機包括，什么是人類的情緒、情感？你完全可以把它看作是某種內部狀態，因而處于心情好的情緒下，你的輸入輸出是一套規則，而心情不好的時候則完全是另一套。這仍然沒有逃出圖靈機的模型范圍。

接下來的問題就是我們人的思維究竟是不是和圖靈機一樣遵循固定的程序呢？這個問題似乎初看是不可能的，因為人的行為太不固定了！你不可預言它！然而我會爭辯道，無論如何神經元傳遞信息、變化狀態的規律都是固定的，可以被程序化的，那么作為神經元的整體：腦的運作必然也要遵循固定的規則也就是程序了。那么，如果是這樣，正如圖靈相信的，

人腦也不會超越圖靈機這個模型，所以，人工智能也必然是可能的！然而，我認為針對這個問題的答案很有可能沒有這么簡單，我們將在最后詳細討論這個問題。

無論如何，我相信你已經能夠體會到了，圖靈機模型實際上是非常強有力的！

計算與圖靈機

1、什么是計算

說了這么多，雖然也許你已經了解到了圖靈機的威力，也許還將信將疑，然而，你肯定仍然看不出來圖靈機和計算有什么關系。而實際上，圖靈機是一個理論計算機模型，它最主

要的能耐還是在于計算上！所以，下面我們就來看看什么是計算！

我可以先給出一個很摩登的對計算概念的理解：廣義上講，一個函數變化如把x 變成了f（x）就是一個計算！如果我們把一切都看作是信息，那么更精確的講，計算就是對信息的變換！如果采用這種觀點，你會發現，其實自然界充滿了計算！如果我們把一個小球扔到地上，小球又彈起來了，那么大地就完成了一次對小球的計算。因為你完全可以把小球的運動都抽象成信息，它無非是一些比如位置、速度、形狀等等能用信息描述的東西嘛，而大地把小球彈起來就無非是對小球的這些信息進行了某種變換，因而大地就完成了一次計算！你可以把整個大地看作是一個系統，而扔下去的小球是對這個系統的輸入，那么彈回來的小球就是該系統的輸出，因而也可以說，計算就是某個系統完成了一次從輸入到輸出的變換！

這樣理解不要緊，你會發現，現實世界到處都是計算了！因為我們完全可以把所有的自然界存在的過程都抽象成這樣的輸入輸出系統，所有的大自然存在的變量都看作是信息，因而計算無處不在！也的確，正是采取了這樣的觀點，國外才有可能發明什么DNA 計算機、生物計算機、量子計算機這些新鮮玩藝！因為人家把DNA 的化學反應、量子世界的波函數變換都看作是計算了，自然就會人為地把這些計算組合起來構成計算機了。然而，似乎我們的理論家們還在力圖證明關于圖靈機的某個定理呢，卻完全沒有意識到計算其實就是這樣簡單！

下面回到圖靈機！為什么說圖靈機是一個計算的裝置呢？很簡單，圖靈機也是一個會對輸入信息進行變換給出輸出信息的系統。比如前面說的小蟲，紙帶上的一個方格一個方格的顏色信息就是對小蟲的輸入，而小蟲所采取的行動就是它的輸出。不過這么看，你會發現，似乎小蟲的輸出太簡單了。因為它僅僅就有那么幾種簡單的輸出動作。然而，不要忘了，復雜性來源于組合！雖然每一次小蟲的輸出動作很簡單，然而當把所有這些輸出動作組合在一起，就有可能非常復雜！比如我們可以把初始時刻的紙帶看作是輸入信息，那么經過任意長的時間比如說100年后，小蟲通過不斷的涂抹紙帶最后留下的信息就是輸出信息了。那么小蟲完成的過程就是一次計算。事實上，在圖靈機的正規定義中，存在一個所謂的停機狀態，當圖靈機一到停機狀態，我們就認為它計算完畢了，因而不用費勁的等上100年。

2、計算的組合

更有意思的是，我們可以把若干個計算系統進行合并構成更大的計算系統。比如還是那個小球吧，如果往地上放了一個蹺蹺板，這樣小球掉到地上會彈起這個蹺蹺板的另一端，而蹺蹺板的另一邊可能還是一個小球，于是這個彈起的小球又會砸向另一個蹺蹺板……。

我們自然可以通過組合若干圖靈機完成更大更多的計算，如果把一個圖靈機對紙帶信息變換的結果又輸入給另一臺圖靈機，然后再輸入給別的圖靈機……，這就是把計算進行了組合！也許你還在為前面說的無限多的內部狀態，無限復雜的程序而苦惱，那么到現在，你不難明白，實際上我們并不需要寫出無限復雜的程序列表，而僅僅將這些圖靈機組合到一起就可以產生復雜的行為了。

有了圖靈機的組合，我們就能夠從最簡單的圖靈機開始構造復雜的圖靈機。那么最簡單的圖靈機是什么呢？我們知道最簡單的信息就是0和1，而最簡單的計算就是對0或1進行布爾運算。而布爾運算本質上其實就三種：與、或、非。從最簡單的邏輯運算操作最簡單的

二進制信息出發我們其實可以構造任意的圖靈機！這點不難理解：任何圖靈機都可以把輸入、輸出信息進行01的編碼，而任何一個變換也可以最終分解為對01編碼的變換，而對01編碼的所有計算都可分解成前面說的三種運算。也許，現在你明白了為什么研究計算機的人都要去研究基本的布爾電路。奧秘就在于，用布爾電路可以組合出任意的圖靈機！

3、征服無限的方法

回憶你小時候是如何學會加法運算的。剛開始的時候，你僅僅會死記硬背。比如你記住了1+1=2，記住了2+4=6，……。然而無論你記住多少固定數字的運算，你都不叫學會了加法。原因很簡單，假如你記住了n 對數的加法，那么我總會拿出第n+1對數是你沒有記住的，因此你還是不會計算。原則上。自然數的個數是無窮的，所以任何兩個數的加法可能結果也是無窮的，而如果采用死記硬背的方法，我們頭腦怎么可能記住無窮數字的計算法則呢？但是隨著年齡的增長，你畢竟還是最終學會了加法運算！說來奇怪，你肯定明白其實加法運算并不需要記住所有數字的運算結果，而僅僅需要記住10以內的任意兩個數的和，并且懂得了進位法則就可以了。

你是怎么做到的呢？假設要計算32+69的加法結果，你會把32寫到一行，把69寫到下一行，然后把他們對齊。于是你開始計算2+9=11，進一位，然后計算3+6=9，再計算9+1=10再進一位，最后，再把計算的這些每一位的結果都拼起來就是最終的答案101。這個簡單例子給我們的啟發就是：作加法的過程就是一個機械的計算過程，這里輸入就是32和69這兩個數字，輸出就是101。而你的程序規則就是具體的把任意兩個10以內的數求和。這樣，根據固定的加法運算程序你可以計算任兩個數的加法了。

不知你發現了沒有，這個計算加法的方法能夠讓你找到運用有限的規則應對無限可能情況的方法！我們剛才說了，實際上自然數是無限的，這樣，所有可能的加法結果也是無限的。然而運用剛才說的運算方法，無論輸入的數字是多少，只要你把要計算的數字寫下來了，就一定能夠計算出最終的結果，而無需死記硬背所有的加法！

因而，可以說計算這個簡單的概念，是一種用有限來應對無限的方法！我們再看一個例子：假如給你一組數對：1，2 3，6 5，10 18，36，就這4對，這時問你102對應的數是多少？很顯然，如果僅僅根據你掌握的已知數對的知識，是不可能知道答案的，因為你的知識庫里面沒有存放著102對應數字的知識。然而，如果你掌握了產生這組數對的程序法則，也就是看到如果第一個數是x ，那么第二個數就是2x 的話，你肯定一下子就算出102對應的是204了。也就是說，你實際上運用2x 這兩個字符就記住了無限的諸如1，2 3，6 102，204所有這樣的數對。

這看起來似乎很奇怪。我怎么可能運用有限的字符來應對無限種可能呢？實際上，當沒有人問你問題的時候，你存儲的2x 什么也沒有，而當我問你102對應的是多少？我就相當于給你輸入了信息：102，而你僅僅是根據這個輸入信息102進行一系列的加工變換得到了輸出信息204。因而輸入信息就好比是原材料，而你的程序規則就是加工的方法，只有在原材料上進行加工，你才能輸出最終產品。

這讓我不禁想起了專家系統方法。其實專家系統就是一個大的規則庫。也就相當于存儲了很多很多的1，2 3，6 5，10這樣特殊的規則對。而無論它存儲的東西再多，總歸會是有限的，你只要找到一個它沒有存儲到的問題，它就無能為力了。因而專家系統就會在你問到102對應是多少的時候失??！如何解決問題？人們想出了很多方法，就比如元規則的方法，其實元規則就相當于剛才所說的計算加法的程序，或者2x 這樣的東西。運用元規則的確可以應對無限種情況了。所以，這就是為什么你問計算機任何兩個數相加是多少，它總能給出你正確的答案的原因，雖然它不必記住所有這些加法對的信息。

然而僅僅是元規則就能解決所有問題么？

假如給你三組數對，排列成一個表：

1，2 3，6 4，8 100，200

3，9 2，6 8，24 100，300

1，4 2，8 3，12 100，400

那么問你在第6行上，3這個數字對應的是多少？我們先要找出第一行的規律是2x 沒有疑問，第二行呢？是3x ，第三行是4x ，那么第6行就應該是7x 了，因而在第6行上3

應該對應的是21了！這里跟前面不太一樣的是，雖然我們得到了每一行的規則比如第一行的2x ，但是隨著行數的增加，這個規則本身也變化了，因而第2行是3x ，第3行是4x 等等，因而我們又得到了一個規則本身的規則，即如果行數是n 的話，那么這一行的規則就是（n+1）x。我們顯然能夠根據輸入的n 和x 計算出數值。把這個道理放到專家系統里面，這種原理就是元規則的規則，元規則的元規則……，應該是無窮的！然而專家系統本身并不會自動的歸納這些規則，人必須事先把這些元規則寫到程序里，這也就是專家系統最大的弊端。而我們人似乎總能在一些個別的事件中歸納出規則。進一步問，機器可以歸納么？這就相當于說：可以為歸納方法編出程序么？這也是一個很有趣的問題，下面將要詳細討論！可以設想，假如我們找到了真正歸納的方法，那么編寫出這樣的程序，它就會一勞永逸的自己進行學習歸納了。我們完全再也不用給他編制程序和規則了。這正是人工智能的終極目標！