圖靈機:基本思想,形式化,停機問題,通用機型,變體,等價機器,

圖靈機 (Turing machine, TM) 是由圖靈在1936年提出的，它是一種精確的通用計算機模型，能模擬實際計算機的所有計算行為。

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

基本介紹

中文名：圖靈機
外文名：Turing Machine
提出時間：1936年
別稱：圖靈計算

基本思想,形式化,停機問題,通用機型,變體,等價機器,

基本思想

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

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

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

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

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

1.一條無限長的紙帶 TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號表示空白。紙帶上的格子從左到右依此被編號為 0,1,2,... ，紙帶的右端可以無限伸展。2.一個讀寫頭 HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

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

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

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

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

形式化

一台圖靈機是一個七元組，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中 Q，Σ，Γ 都是有限集合，且滿足

1.Q 是狀態集合；

2.Σ 是輸入字母表，其中不包含特殊的空白符；

3.Γ 是帶字母表，其中 □∈Γ且Σ∈Γ ；4. δ：Q×「→Q×Γ×{L,R}是轉移函式，其中L,R 表示讀寫頭是向左移還是向右移；

5.q0∈Q是起始狀態；

6. qaccept是接受狀態。

7.qreject是拒絕狀態，且qreject≠qaccept。

圖靈機 M = (Q，Σ，Γ，δ，q0,qaccept,qreject) 將以如下方式運作：

開始的時候將輸入符號串從左到右依此填在紙帶的第號格子上，其他格子保持空白（即填以空白符）。M 的讀寫頭指向第 0 號格子， M 處於狀態 q0。機器開始運行後，按照轉移函式 δ 所描述的規則進行計算。例如，若當前機器的狀態為 q，讀寫頭所指的格子中的符號為 x，設 δ（q,x) = (q',x',L），則機器進入新狀態 q'，將讀寫頭所指的格子中的符號改為 x'，然後將讀寫頭向左移動一個格子。若在某一時刻，讀寫頭所指的是第 0 號格子，但根據轉移函式它下一步將繼續向左移，這時它停在原地不動。換句話說，讀寫頭始終不移出紙帶的左邊界。若在某個時刻 M 根據轉移函式進入了狀態 qaccept，則它立刻停機並接受輸入的字元串；若在某個時刻 M 根據轉移函式進入了狀態 qreject，則它立刻停機並拒絕輸入的字元串。

注意，轉移函式 δ 是一個部分函式，換句話說對於某些 q,x， δ（q,x) 可能沒有定義，如果在運行中遇到下一個操作沒有定義的情況，機器將立刻停機。

停機問題

停機問題（halting problem）是目前邏輯數學的焦點，和第三次數學危機的解決方案。其本質問題是：給定一個圖靈機 T，和一個任意語言集合 S，是否 T 會最終停機於每一個。其意義相同於可確定語言。顯然任意有限 S 是可判定性的，可數的（countable) S 也是可停機的，在使用 oracle 輸入的幫助下。

通俗的說，停機問題就是判斷任意一個程式是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，可以有一個程式判斷其本身是否會停機並做出相反的行為。這時候顯然不管停機問題的結果是什麼都不會符合要求。所以這是一個不可解的問題。

停機問題本質是一階邏輯的不自恰性和不完備性。類似的命題有理髮師悖論、全能悖論等。

證明：

設停機問題有解，即：存在過程H(P,I）可以給出程式P在輸入I的情況下是否可停機。假設若P在輸入I時可停機，H輸出“停機”，反之輸出“死循環”，即可導出矛盾：

顯然，程式本身可以被視作數據，因此它可以被作為輸入，故H應該可以判定當將P作為P的輸入時，P是否會停機。所以我們設過程K(P）的流程如下：首先，它調用H(P,P），如果H(P,P）輸出“死循環”，則K(P）停機，反之K(P）死循環。即K(P）做與H(P,P）的輸出相反的動作。

現在假設求K(K），則若H(K,K）輸出停機，K(K）死循環，但由定義知二者矛盾。反之，H(K,K）輸出死循環，則K(K）停機，兩者一樣矛盾。

因此，H不是總能給出正確答案，故而不存在解決停機問題的方法。

通用機型

對於任意一個圖靈機，因為它的描述是有限的，因此我們總可以用某種方式將其編碼為字元串。我們用 <M> 表示圖靈機 M 的編碼。

我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機 M 的編碼<M> ，然後模擬 M 的運作，這樣的圖靈機稱為通用圖靈機(Universal Turing Machine）。現代電子計算機其實就是這樣一種通用圖靈機的模擬，它能接受一段描述其他圖靈機的程式，並運行程式實現該程式所描述的算法。但要注意，它只是模擬，因為現實中的計算機的存儲都是有限的，所以無法跨越有限狀態機的界限。經典圖靈機及其許多變形識別語言的能力都是相同的，正因為如此，圖靈機可以作為計算的一般模型。另外，通用圖靈機 (可程式圖靈機) 是存在的，通用圖靈機可以模擬任意一個圖靈機，這也是將圖靈機作為現代計算機的形式模型的根本原因。