圖靈機的組成：

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

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

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

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

關(guān)于圖靈機的模型介紹

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

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

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

當前內(nèi)部狀態(tài)s 輸入數(shù)值i 輸出動作o 下一時刻的內(nèi)部狀態(tài)s‘

B 1 前移C

A 0 往紙帶上寫1 B

C 0 后移A

… … … …

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

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

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