英國數學傢A.M.圖靈於1936年提出的一種抽象自動機，用來定義可計算函數類。在數學上遞迴函數和λ可定義函數均等價於圖靈機定義的可計算函數。圖靈機能表示演算法、程式和符號行的變換，因而可作為電子電腦的數學模型，也可用作控制演算法的數學模型，在形式語言理論中還可用來研究短語結構語言（即遞迴可數語言）。40年代以來，許多科學傢根據圖靈的構思提出瞭一系列抽象自動機，來研究神經網路和各種高級控制系統（如自適應、自學習、自組織、自繁殖等系統）。

　　圖靈機的構造　

圖靈機由控制器、存儲帶和讀寫頭組成。①控制器：它是一臺時序機，即有限自動機，具有有限個內在狀態，包括初始狀態和終止狀態。控制器內存有操作程序，即指令序列，用來驅動存儲帶左右移動和控制讀寫頭的操作。②存儲帶：它是一條可向兩端無限延伸的帶子，帶上分成一個個方格，每一方格可以存儲規定字符表中的一個字符，也可保持空白。③讀寫頭：它能與存儲帶進行相對運動，並對存儲帶進行掃描，每次讀出或寫入一個字符。讀寫頭與控制器能進行雙向通信，即接受控制器的指令，並將掃描結果送到控制器。圖中示出圖靈機的構造。

　　圖靈機的功能　圖靈機可用一個三元組(W，p，s)表示，式中W是存儲帶上的符號串；p表示讀寫頭與存儲帶的相對運動；s是圖靈機的內在狀態。因此,圖靈機在某一時刻的形象即格局可描繪成下列形式

這裡C1C2…Cm是存儲帶上的符號串,讀寫頭正掃描Cj,當時圖靈機的內在狀態是Si。圖靈機的計算就是形象變化過程。如果把內在狀態看作符號行的一部分，即把內在狀態嵌入形象符號串中，則圖靈機的計算就是一種符號行的變換。

　　圖靈機的程序可用程序表來說明，此時要區別主動狀態和被動狀態。圖靈機處於主動狀態就繼續執行，處於被動狀態就停機。如果圖靈機有n個內在狀態和由m個符號構成的符號表,則可用n×(m＋1)的表格來表示它的程序。表中每一元素就是一條指令，每條指令有運算指令和轉移指令兩部分，圖靈機的內在狀態起著指令標號的作用。例如,元素Ckpsl表示把讀寫頭掃描的方格改寫成符號Ck，根據p 的取值使存儲帶右移一格，或左移一格,或保持不動,圖靈機轉到內在狀態sl。如果圖靈機當前處於內在狀態si,讀寫頭正在掃描字符Cj,則圖靈機的指令可寫成siCjCkpsl。其中si∈{s1,s2,…,sn},Cj∈{C1,C2,…,Cm},p∈{r，l，h},這裡r表示右移一格，l表示左移一格，h表示不動。

　　圖靈機有兩種基本功能：①作為函數計算機，它能計算一切可計算函數。例如，如果圖靈機的存儲帶上輸入符號串為n的編碼,經過有限步操作後存儲帶上的符號串變為m的編碼，則稱該圖靈機計算瞭函數 f(n)＝m 。②作為語言識別器，它能識別0型語言,即遞歸可枚舉集(見短語結構文法）。

　　通用圖靈機　1936年圖靈提出可構造一種通用圖靈機U來模擬其他圖靈機T的計算。如果 U的存儲帶上存有表征T的形象的符號串，則U將在帶上寫入 T在計算中得到的各種情況。因此讀寫頭掃描U帶上的內容即可獲得T帶上的內容。這就表明可用通用圖靈機來模擬任何其他的圖靈機。1956年C.E.香農證明瞭可構造隻有兩個內在狀態的通用圖靈機。通用圖靈機的概念與通用電子數字計算機的概念等價。通用電子數字計算機是輸入程序和數據,然後按程序進行計算。計算的種類由程序決定,不由計算機決定。通用圖靈機U也是這樣，輸入的是數組(t，x),這裡t是圖靈機T的哥德爾數，即T的程序，x是輸入數據。U對於這個數組的計算與T對x的計算等價,所以隻要對U輸入T的程序,U即可進行T的計算。1945年J.von諾伊曼根據通用圖靈機的概念提出存儲程序式電子數字計算機方案。

　　廣義圖靈機　1960年德國數學傢S.C.克林提出廣義圖靈機，用以定義部分遞歸的有限元泛函。克林提出的廣義圖靈機是一種具有解算裝置的完整的計算過程。解算裝置可看作是圖靈機的一條輔助帶，它的內容可復制到主帶上來，從而擴大圖靈機的計算能力。這種圖靈機定義的可計算函數是相對遞歸函數。

　　圖靈機的改進　任何改進型圖靈機的計算能力均與圖靈機等價，改進的目的是為瞭提高計算效率，尋找新的數學模型，以便於研究各種不同類型的信息處理問題。例如，多帶圖靈機可作為研究計算復雜性理論的數學模型。圖靈機的改進主要有以下兩個方面:①計算方式:圖靈機的計算方式極為原始，為瞭改進這種情況，可增加讀寫頭和存儲帶的數目，甚至把一維帶變成多維帶。這樣做相當於在計算機中增加寄存器和存儲器，增加平行處理功能。②指令形式:可采用沒有內在狀態的機器,使圖靈機的指令形式更接近於現代計算機。1936年英國數學傢E.L.波斯特提出的波斯特機就是這樣的機器，它采用符號集{0,1},比圖靈機更接近現代計算機。1957年美籍數學傢王浩提出的W機，它的構思與波斯特機相同,但程序更為簡潔。改進型圖靈機還有許多型式，各有不同的用處。如半無限帶圖靈機、多頭圖靈機、多帶圖靈機、多維圖靈機、無限多寄存器機器（即URM機）和明斯基機等。

　　圖靈機的停機問題　圖靈機根據程序處理初始格局，有的導致停機,有的導致無限格局序列。人們就提出,是否存在一個算法，能判定任意給定的圖靈機對任意的初始格局是否會導致停機。這就是著名的圖靈機停機問題。已經證明,這樣的算法是不存在的,即停機問題是不可判定的。人們往往把一個問題的判定歸結為停機問題，所以停機問題是研究不可判定問題的基礎。

　　

參考書目

　申南和麥克卡賽編,陳中基編譯：《自動機研究》,科學出版社,北京,1963。(C.E.Shannon and J. McCarthy (eds)，Automata Studies， Princeton University Press, Princeton, N.J.,1956.)