精密機械加工

[拼音]：Tulingji

[英文]：Turing machine

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

圖靈機的構造

圖靈機由控制器、儲存帶和讀寫頭組成。

（1）控制器：它是一臺時序機，即有限自動機，具有有限個內在狀態，包括初始狀態和終止狀態。控制器記憶體有操作程式，即指令序列，用來驅動儲存帶左右移動和控制讀寫頭的操作。

（2）儲存帶：它是一條可向兩端無限延伸的帶子，帶上分成一個個方格，每一方格可以儲存規定字元表中的一個字元，也可保持空白。

（3）讀寫頭：它能與儲存帶進行相對運動，並對儲存帶進行掃描，每次讀出或寫入一個字元。讀寫頭與控制器能進行雙向通訊，即接受控制器的指令，並將掃描結果送到控制器。圖中示出圖靈機的構造。

圖靈機的功能

圖靈機可用一個三元組(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表示不動。

圖靈機有兩種基本功能：

（1）作為函式計算機，它能計算一切可計算函式。例如，如果圖靈機的儲存帶上輸入符號串為n的編碼,經過有限步操作後儲存帶上的符號串變為m的編碼，則稱該圖靈機計算了函式 f(n)＝m 。

（2）作為語言識別器，它能識別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.克林提出廣義圖靈機，用以定義部分遞迴的有限元泛函。克林提出的廣義圖靈機是一種具有解算裝置的完整的計算過程。解算裝置可看作是圖靈機的一條輔助帶，它的內容可複製到主帶上來，從而擴大圖靈機的計算能力。這種圖靈機定義的可計算函式是相對遞迴函式。

圖靈機的改進

任何改進型圖靈機的計算能力均與圖靈機等價，改進的目的是為了提高計算效率，尋找新的數學模型，以便於研究各種不同型別的資訊處理問題。例如，多帶圖靈機可作為研究計算複雜性理論的數學模型。圖靈機的改進主要有以下兩個方面：

（1）計算方式:圖靈機的計算方式極為原始，為了改進這種情況，可增加讀寫頭和儲存帶的數目，甚至把一維帶變成多維帶。這樣做相當於在計算機中增加暫存器和儲存器，增加平行處理功能。

（2）指令形式:可採用沒有內在狀態的機器,使圖靈機的指令形式更接近於現代計算機。1936年英國數學家E.L.波斯特提出的波斯特機就是這樣的機器，它採用符號集{0,1},比圖靈機更接近現代計算機。1957年美籍數學家王浩提出的W機，它的構思與波斯特機相同,但程式更為簡潔。改進型圖靈機還有許多型式，各有不同的用處。如半無限帶圖靈機、多頭圖靈機、多帶圖靈機、多維圖靈機、無限多暫存器機器 （即URM機）和明斯基機等。

圖靈機的停機問題

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

參考書目

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