圖靈機(jī)簡(jiǎn)介

圖靈機(jī)，又稱圖靈計(jì)算、圖靈計(jì)算機(jī)，是由數(shù)學(xué)家阿蘭·麥席森·圖靈（1912～1954）提出的一種抽象計(jì)算模型，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程進(jìn)行抽象，由一個(gè)虛擬的機(jī)器替代人們進(jìn)行數(shù)學(xué)運(yùn)算。

所謂的圖靈機(jī)就是指一個(gè)抽象的機(jī)器，它有一條無限長(zhǎng)的紙帶，紙帶分成了一個(gè)一個(gè)的小方格，每個(gè)方格有不同的顏色。有一個(gè)機(jī)器頭在紙帶上移來移去。機(jī)器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每個(gè)時(shí)刻，機(jī)器頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動(dòng)。

圖靈機(jī)的主要作用及功能：

作為研究計(jì)算的一般性質(zhì)的抽象工具，替代人們進(jìn)行數(shù)學(xué)運(yùn)算，并有以下作用：

1、作為語言接受器：被M接受的語育記作L（M），它是Σ中的這樣一些字符串的集合，當(dāng)把這些字符串放在M的帶子上，M處于q0狀態(tài)且M的帶頭處在最左單元時(shí)．這些字符串可以使M進(jìn)入一個(gè)終結(jié)狀態(tài)而停機(jī)。給定一個(gè)識(shí)別語言L的圖靈機(jī)M，一般假定，當(dāng)輸入被接受時(shí)，M為停機(jī)，即沒有下一動(dòng)作。然而對(duì)于不被接受的字符串，M可能永不停機(jī)．被圖靈機(jī)接受的語官稱為遞歸可枚舉語言。遞歸集合是遞歸可枚舉集合的子類，遞歸集合總能被對(duì)所有輸入都能停機(jī)的圖靈機(jī)所接受。

2、作為整數(shù)函數(shù)計(jì)算機(jī)：被圖靈機(jī)計(jì)算的函數(shù)稱為部分遞歸函數(shù)。在某種意義上，部分遞歸函數(shù)類似于遞歸可枚舉語言．因?yàn)橛?jì)算它的圖靈機(jī)在給定的輸入上可能不停機(jī)。完全遞歸函數(shù)對(duì)應(yīng)于遞歸語育．因?yàn)樗鼙豢偰芡C(jī)的圖靈機(jī)計(jì)算。

3、作為語言產(chǎn)生器：設(shè)M是一個(gè)多帶圖靈機(jī)，它用一條帶作為輸出帶，在這條帶上，符號(hào)一經(jīng)寫出上就不能再改寫．輸出帶的帶頭也不能左移。假定在輸出帶上，M寫出某個(gè)字毋表Σ的一些字符串，并用分隔符分開，則最終打印在輸出帶上的字符串的集合就稱為由M生成的語言，記為G（M），G（M）Σ。如果L是某個(gè)圖靈機(jī)生成的語言，則L是遞歸可枚舉集合，反之亦然。

圖靈機(jī)產(chǎn)生背景

任何科學(xué)思想、科學(xué)概念的誕生都有它的背景，在背景中往往有很多迷人的故事。關(guān)于計(jì)算理論可以追溯到1900年，當(dāng)時(shí)著名的大數(shù)學(xué)家希爾伯特在世紀(jì)之交的數(shù)學(xué)家大會(huì)上給國際數(shù)學(xué)界提出了著名的23個(gè)數(shù)學(xué)問題。其中第十問題是這樣的：存在不存在一種有限的、機(jī)械的步驟能夠判斷“丟番圖方程”是否存在解？這里就提出來了有限的、機(jī)械的證明步驟的問題，用今天的話說就是算法。但在當(dāng)時(shí)，人們還不知道“算法”是什么。實(shí)際上，當(dāng)時(shí)數(shù)學(xué)領(lǐng)域中已經(jīng)有很多問題都是跟“算法”密切相關(guān)的，因而，科學(xué)的“算法” 定義呼之欲出。之后到了30年代的時(shí)候，終于有兩個(gè)人分別提出了精確定義算法的方法，一個(gè)人是圖靈，一個(gè)人是丘奇。而其中圖靈提出來的圖靈機(jī)模型直觀形象，于是很快得到了大家的普遍接受。

不知道你是否聽說過圖靈這個(gè)名字?？赡苡行┤酥琅ｎD，知道愛因斯坦，甚至知道馮諾依曼，但不知道圖靈。然而圖靈的貢獻(xiàn)絕對(duì)不亞于這些科學(xué)大師。圖靈最大的貢獻(xiàn)就是把算法這樣一個(gè)基本的、深刻的概念用他的圖靈機(jī)模型講清楚了。正是因?yàn)閳D靈奠定的理論基礎(chǔ)，人們才有可能發(fā)明20世紀(jì)以來甚至是人類有史以來最偉大的發(fā)明：計(jì)算機(jī)。因此人們稱圖靈為：計(jì)算機(jī)理論之父。

圖靈生活的年代經(jīng)歷了第二次世界大戰(zhàn)。在二戰(zhàn)期間他曾經(jīng)為英國政府效力成功破譯了德國的密碼，因而為英國做出了突出貢獻(xiàn)。其實(shí)也正是因?yàn)槎?zhàn)，英國政府才肯掏錢讓圖靈制造最原始的計(jì)算機(jī)，當(dāng)然這種計(jì)算機(jī)是專門用來破譯密碼用的，而不是我們現(xiàn)在用的通用計(jì)算機(jī)。（有一部片子叫《密碼迷情》英文名是《enigma 》就是根據(jù)圖靈當(dāng)時(shí)破譯德國密碼的故事改編的，大家有興趣可以去找一找。）

圖靈這個(gè)人很古怪，只喜歡自己一個(gè)人悶頭研究，不喜歡與別人交流。并且據(jù)說他還是一個(gè)同性戀者。要知道在當(dāng)時(shí)的英國，同性戀行為可是大逆不道的。最后，在他事業(yè)剛剛達(dá)到頂風(fēng)的時(shí)候，他自殺了。為了紀(jì)念這個(gè)偉大的學(xué)者，計(jì)算機(jī)界設(shè)立了最高榮譽(yù)獎(jiǎng)：ACM 圖靈獎(jiǎng)。

圖靈機(jī)的產(chǎn)生一方面奠定了現(xiàn)代數(shù)字計(jì)算機(jī)的基礎(chǔ)（要知道后來馮諾依曼就是根據(jù)圖靈的設(shè)想才設(shè)計(jì)出第一臺(tái)計(jì)算機(jī)的）。另一方面，根據(jù)圖靈機(jī)這一基本簡(jiǎn)潔的概念，我們還可以看到可計(jì)算的極限是什么。也就是說實(shí)際上計(jì)算機(jī)的本領(lǐng)從原則上講是有限制的。請(qǐng)注意，這里說到計(jì)算機(jī)的極限并不是說它不能吃飯、掃地等硬件方面的極限，而是僅僅就從信息處理這個(gè)角度，計(jì)算機(jī)也仍然存在著極限。這就是圖靈機(jī)的停機(jī)問題。這個(gè)問題在圖靈看來更加重要，在他當(dāng)年的論文中，其實(shí)他是為了論證圖靈停機(jī)問題才“捎帶手”提出了圖靈機(jī)模型的。

圖靈機(jī)基本思想

圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，他把這樣的過程看作下列兩種簡(jiǎn)單的動(dòng)作：

在紙上寫上或擦除某個(gè)符號(hào)；

把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置；

而在每個(gè)階段，人要決定下一步的動(dòng)作，依賴于此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號(hào)和此人當(dāng)前思維的狀態(tài)。

為了模擬人的這種運(yùn)算過程，圖靈構(gòu)造出一臺(tái)假想的機(jī)器，該機(jī)器由以下幾個(gè)部分組成：

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

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)來確定讀寫頭下一步的動(dòng)作，并改變狀態(tài)寄存器的值，令機(jī)器進(jìn)入一個(gè)新的狀態(tài)。

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

注意這個(gè)機(jī)器的每一部分都是有限的，但它有一個(gè)潛在的無限長(zhǎng)的紙帶，因此這種機(jī)器只是一個(gè)理想的設(shè)備。圖靈認(rèn)為這樣的一臺(tái)機(jī)器就能模擬人類所能進(jìn)行的任何計(jì)算過程。

? ? ?

在某些模型中，讀寫頭沿著固定的紙帶移動(dòng)。要進(jìn)行的指令（q1）展示在讀寫頭內(nèi)。在這種模型中“空白”的紙帶是全部為 0 的。有陰影的方格，包括讀寫頭掃描到的空白，標(biāo)記了 1，1，B 的那些方格，和讀寫頭符號(hào)，構(gòu)成了系統(tǒng)狀態(tài)。（由 Minsky （1967） p.121 繪制）。