圖靈機(jī)的組成部分_圖靈機(jī)的模型介紹

1.一條無(wú)限長(zhǎng)的紙帶 TAPE。紙帶被劃分為一個(gè)接一個(gè)的小格子，每個(gè)格子上包含一個(gè)來(lái)自有限字母表的符號(hào)，字母表中有一個(gè)特殊的符號(hào) 表示空白。紙帶上的格子從左到右依此被編號(hào)為 0，1，2，。.. ，紙帶的右端可以無(wú)限伸展。

2.一個(gè)讀寫頭 HEAD。該讀寫頭可以在紙帶上左右移動(dòng)，它能讀出當(dāng)前所指的格子上的符號(hào)，并能改變當(dāng)前格子上的符號(hào)。

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

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

圖靈機(jī)的模型介紹雖然有些無(wú)趣，不過(guò)請(qǐng)堅(jiān)持看下去，我會(huì)在下面運(yùn)用大家比較好理解的形式重新解釋的。在這里你僅僅需要認(rèn)識(shí)它的輪廓。一個(gè)圖靈機(jī)是形如下面的一個(gè)裝置：

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

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

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

B 1 前移C

A 0 往紙帶上寫1 B

C 0 后移A

… … … …

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

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

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