圖靈機簡介

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

所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然后結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，并轉換自己的內部狀態，然后進行移動。

圖靈機的主要作用及功能：

作為研究計算的一般性質的抽象工具，替代人們進行數學運算，并有以下作用：

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

2、作為整數函數計算機：被圖靈機計算的函數稱為部分遞歸函數。在某種意義上，部分遞歸函數類似于遞歸可枚舉語言．因為計算它的圖靈機在給定的輸入上可能不停機。完全遞歸函數對應于遞歸語育．因為它能被總能停機的圖靈機計算。

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

圖靈機產生背景

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

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

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

圖靈這個人很古怪，只喜歡自己一個人悶頭研究，不喜歡與別人交流。并且據說他還是一個同性戀者。要知道在當時的英國，同性戀行為可是大逆不道的。最后，在他事業剛剛達到頂風的時候，他自殺了。為了紀念這個偉大的學者，計算機界設立了最高榮譽獎：ACM 圖靈獎。

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

圖靈機基本思想

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

在紙上寫上或擦除某個符號；

把注意力從紙的一個位置移動到另一個位置；

而在每個階段，人要決定下一步的動作，依賴于此人當前所關注的紙上某個位置的符號和此人當前思維的狀態。

為了模擬人的這種運算過程，圖靈構造出一臺假想的機器，該機器由以下幾個部分組成：

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

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

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

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

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設備。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程。

? ? ?

在某些模型中，讀寫頭沿著固定的紙帶移動。要進行的指令（q1）展示在讀寫頭內。在這種模型中“空白”的紙帶是全部為 0 的。有陰影的方格，包括讀寫頭掃描到的空白，標記了 1，1，B 的那些方格，和讀寫頭符號，構成了系統狀態。（由 Minsky （1967） p.121 繪制）。