圖靈機簡介
圖靈機,又稱圖靈計算、圖靈計算機,是由數(shù)學(xué)家阿蘭·麥席森·圖靈(1912~1954)提出的一種抽象計算模型,即將人們使用紙筆進行數(shù)學(xué)運算的過程進行抽象,由一個虛擬的機器替代人們進行數(shù)學(xué)運算。
所謂的圖靈機就是指一個抽象的機器,它有一條無限長的紙帶,紙帶分成了一個一個的小方格,每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內(nèi)部狀態(tài),還有一些固定的程序。在每個時刻,機器頭都要從當(dāng)前紙帶上讀入一個方格信息,然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表,根據(jù)程序輸出信息到紙帶方格上,并轉(zhuǎn)換自己的內(nèi)部狀態(tài),然后進行移動。
圖靈機的主要作用及功能:
作為研究計算的一般性質(zhì)的抽象工具,替代人們進行數(shù)學(xué)運算,并有以下作用:
1、作為語言接受器:被M接受的語育記作L(M),它是Σ中的這樣一些字符串的集合,當(dāng)把這些字符串放在M的帶子上,M處于q0狀態(tài)且M的帶頭處在最左單元時.這些字符串可以使M進入一個終結(jié)狀態(tài)而停機。給定一個識別語言L的圖靈機M,一般假定,當(dāng)輸入被接受時,M為停機,即沒有下一動作。然而對于不被接受的字符串,M可能永不停機.被圖靈機接受的語官稱為遞歸可枚舉語言。遞歸集合是遞歸可枚舉集合的子類,遞歸集合總能被對所有輸入都能停機的圖靈機所接受。
2、作為整數(shù)函數(shù)計算機:被圖靈機計算的函數(shù)稱為部分遞歸函數(shù)。在某種意義上,部分遞歸函數(shù)類似于遞歸可枚舉語言.因為計算它的圖靈機在給定的輸入上可能不停機。完全遞歸函數(shù)對應(yīng)于遞歸語育.因為它能被總能停機的圖靈機計算。
3、作為語言產(chǎn)生器:設(shè)M是一個多帶圖靈機,它用一條帶作為輸出帶,在這條帶上,符號一經(jīng)寫出上就不能再改寫.輸出帶的帶頭也不能左移。假定在輸出帶上,M寫出某個字毋表Σ的一些字符串,并用分隔符分開,則最終打印在輸出帶上的字符串的集合就稱為由M生成的語言,記為G(M),G(M)Σ。如果L是某個圖靈機生成的語言,則L是遞歸可枚舉集合,反之亦然。
圖靈機產(chǎn)生背景
任何科學(xué)思想、科學(xué)概念的誕生都有它的背景,在背景中往往有很多迷人的故事。關(guān)于計算理論可以追溯到1900年,當(dāng)時著名的大數(shù)學(xué)家希爾伯特在世紀之交的數(shù)學(xué)家大會上給國際數(shù)學(xué)界提出了著名的23個數(shù)學(xué)問題。其中第十問題是這樣的:存在不存在一種有限的、機械的步驟能夠判斷“丟番圖方程”是否存在解?這里就提出來了有限的、機械的證明步驟的問題,用今天的話說就是算法。但在當(dāng)時,人們還不知道“算法”是什么。實際上,當(dāng)時數(shù)學(xué)領(lǐng)域中已經(jīng)有很多問題都是跟“算法”密切相關(guān)的,因而,科學(xué)的“算法” 定義呼之欲出。之后到了30年代的時候,終于有兩個人分別提出了精確定義算法的方法,一個人是圖靈,一個人是丘奇。而其中圖靈提出來的圖靈機模型直觀形象,于是很快得到了大家的普遍接受。
不知道你是否聽說過圖靈這個名字。可能有些人知道牛頓,知道愛因斯坦,甚至知道馮諾依曼,但不知道圖靈。然而圖靈的貢獻絕對不亞于這些科學(xué)大師。圖靈最大的貢獻就是把算法這樣一個基本的、深刻的概念用他的圖靈機模型講清楚了。正是因為圖靈奠定的理論基礎(chǔ),人們才有可能發(fā)明20世紀以來甚至是人類有史以來最偉大的發(fā)明:計算機。因此人們稱圖靈為:計算機理論之父。
圖靈生活的年代經(jīng)歷了第二次世界大戰(zhàn)。在二戰(zhàn)期間他曾經(jīng)為英國政府效力成功破譯了德國的密碼,因而為英國做出了突出貢獻。其實也正是因為二戰(zhàn),英國政府才肯掏錢讓圖靈制造最原始的計算機,當(dāng)然這種計算機是專門用來破譯密碼用的,而不是我們現(xiàn)在用的通用計算機。(有一部片子叫《密碼迷情》英文名是《enigma 》就是根據(jù)圖靈當(dāng)時破譯德國密碼的故事改編的,大家有興趣可以去找一找。)
圖靈這個人很古怪,只喜歡自己一個人悶頭研究,不喜歡與別人交流。并且據(jù)說他還是一個同性戀者。要知道在當(dāng)時的英國,同性戀行為可是大逆不道的。最后,在他事業(yè)剛剛達到頂風(fēng)的時候,他自殺了。為了紀念這個偉大的學(xué)者,計算機界設(shè)立了最高榮譽獎:ACM 圖靈獎。
圖靈機的產(chǎn)生一方面奠定了現(xiàn)代數(shù)字計算機的基礎(chǔ)(要知道后來馮諾依曼就是根據(jù)圖靈的設(shè)想才設(shè)計出第一臺計算機的)。另一方面,根據(jù)圖靈機這一基本簡潔的概念,我們還可以看到可計算的極限是什么。也就是說實際上計算機的本領(lǐng)從原則上講是有限制的。請注意,這里說到計算機的極限并不是說它不能吃飯、掃地等硬件方面的極限,而是僅僅就從信息處理這個角度,計算機也仍然存在著極限。這就是圖靈機的停機問題。這個問題在圖靈看來更加重要,在他當(dāng)年的論文中,其實他是為了論證圖靈停機問題才“捎帶手”提出了圖靈機模型的。
圖靈機基本思想
圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學(xué)運算的過程,他把這樣的過程看作下列兩種簡單的動作:
在紙上寫上或擦除某個符號;
把注意力從紙的一個位置移動到另一個位置;
而在每個階段,人要決定下一步的動作,依賴于此人當(dāng)前所關(guān)注的紙上某個位置的符號和此人當(dāng)前思維的狀態(tài)。
為了模擬人的這種運算過程,圖靈構(gòu)造出一臺假想的機器,該機器由以下幾個部分組成:
1.一條無限長的紙帶 TAPE。紙帶被劃分為一個接一個的小格子,每個格子上包含一個來自有限字母表的符號,字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0,1,2,。.. ,紙帶的右端可以無限伸展。
2.一個讀寫頭 HEAD。該讀寫頭可以在紙帶上左右移動,它能讀出當(dāng)前所指的格子上的符號,并能改變當(dāng)前格子上的符號。
3.一套控制規(guī)則 TABLE。它根據(jù)當(dāng)前機器所處的狀態(tài)以及當(dāng)前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作,并改變狀態(tài)寄存器的值,令機器進入一個新的狀態(tài)。
4.一個狀態(tài)寄存器。它用來保存圖靈機當(dāng)前所處的狀態(tài)。圖靈機的所有可能狀態(tài)的數(shù)目是有限的,并且有一個特殊的狀態(tài),稱為停機狀態(tài)。參見停機問題。
注意這個機器的每一部分都是有限的,但它有一個潛在的無限長的紙帶,因此這種機器只是一個理想的設(shè)備。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程。
? ? ?
在某些模型中,讀寫頭沿著固定的紙帶移動。要進行的指令(q1)展示在讀寫頭內(nèi)。在這種模型中“空白”的紙帶是全部為 0 的。有陰影的方格,包括讀寫頭掃描到的空白,標(biāo)記了 1,1,B 的那些方格,和讀寫頭符號,構(gòu)成了系統(tǒng)狀態(tài)。(由 Minsky (1967) p.121 繪制)。
評論
查看更多