圖靈機

圖靈機的藝術表示

圖靈機（英語：Turing machine），又稱確定型圖靈機，是英國數學家亞倫·圖靈於1936年提出的一種將人的計算行為抽象化的數理邏輯機，其更抽象的意義為一種計算模型，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。

圖靈的基本思想

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

• 在紙上寫上或擦除某個符號；
• 把注意力從紙的一處移動到另一處；

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

在某些模型中，紙帶移動，而未用到的紙帶真正是「空白」的。要進行的指令（q4）展示在掃描到方格之上（由Kleene（1952）p.375繪製）。

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

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

1. 一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號$\square$表示空白。紙帶上的格子從左到右依次被編號為0, 1, 2, ...，紙帶的右端可以無限伸展。
2. 一個讀寫頭HEAD。它可以在紙帶上左右移動，能讀出當前所指的格子上的符號，並能改變它。
3. 一套控制規則數量有限的TABLE（A finite table of instructions）。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態暫存器的值，令機器進入一個新的狀態。
   按照以下順序告知圖靈機命令：
   • 1. 寫入（替換）或擦除當前符號；
   • 2. 移動 HEAD， 'L'向左， 'R'向右或者'N'不移動；
   • 3. 保持當前狀態或者轉到另一狀態。
4. 一個狀態暫存器。它用來儲存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。參見停機問題。

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

圖靈機的正式定義

一台圖靈機是一個七元有序組$(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})$，其中$Q,\Sigma ,\Gamma$都是有限集合，且滿足：

1. $Q$是非空有窮狀態集合；
2. $\Sigma$是非空有窮輸入字母表，其中不包含特殊的空白符$\square$；
3. $\Gamma$是非空有窮帶字母表且$\Sigma \subset \Gamma$；$\square \in \Gamma -\Sigma$為空白符，也是唯一允許出現無限次的字元；
4. $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R,-\}$是轉移函數，其中$L,R$表示讀寫頭是向左移還是向右移, - 表示不移動；
5. $q_{0}\in Q$是起始狀態；
6. $q_{accept}\in Q$是接受狀態。
7. $q_{reject}\in Q$是拒絕狀態，且$q_{reject}\neq q_{accept}$。

圖靈機$M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})$將以如下方式運作：

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

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

圖靈機的基本術語

設$M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})$是一台圖靈機，

1. $M$的帶描述（tape description）是一個函數$F:\mathbb {N} \to \Gamma$，其中$F(i)$表示$M$的帶上第$i$個格子中的符號；
2. $M$的格局（configuration）是一個三元組$(F,q,e)$，其中$F:\mathbb {N} \to \Gamma$是當前的帶描述，$q\in Q$是當前的狀態，$e\in \mathbb {N}$是當前讀寫頭所處的位置；
3. 設$C_{1}=(F_{1},q_{1},e_{1})$, $C_{2}=(F_{2},q_{2},e_{2})$是$M$的格局，設$\delta (q_{1},F_{1}(e_{1}))=(q,x,d)$，若滿足$q_{2}=q$，

   $e_{2}={\begin{cases}e_{1}-1&d=L\\e_{1}+1&d=R\end{cases}}$

   以及

   $F_{2}(i)={\begin{cases}F_{1}(i)&i\neq e_{1}\\x&i=e_{1}\end{cases}}$

   則稱$M$從格局$C_{1}$ 產生格局$C_{2}$，記作$C_{1}\to _{M}C_{2}$。
4. 設$C=(F,q,e)$為$M$的格局，若$q=q_{accept}$則稱$C$為接受格局；若$q=q_{reject}$則稱$C$為拒絕格局；接受格局和拒絕格局統稱為停機格局。

設$M$是一台圖靈機，將字串 $\omega =\omega _{0}\omega _{1}\ldots \omega _{n-1}$ 作為其輸入，若存在格局序列$C_{1},C_{2},\ldots ,C_{k}$，使得

1. $C_{1}$是$M$在輸入$\omega$上的起始格局，即$C_{1}=(F,q_{0},0)$，其中

   $F_{1}(i)={\begin{cases}\omega _{i}&0\leq i\leq n-1\\\square &{\mbox{otherwise}}\end{cases}}$

2. $C_{i}\to _{M}C_{i+1}$，其中$i=1,2,\ldots ,k-1$；
3. $C_{k}$是接受格局。

則稱$M$ 接受字串$\omega$，且$C_{1},C_{2},\ldots ,C_{k}$稱為圖靈機$M$在輸入$\omega$上的接受計算歷史。同理，若$C_{k}$是拒絕格局，則稱$M$ 拒絕$\omega$，且$C_{1},C_{2},\ldots ,C_{k}$稱為圖靈機$M$在輸入$\omega$上的拒絕計算歷史。$M$所接受的所有字串的集合稱為$M$的語言，記作$L(M)$。

圖靈機的例子

設$M=(\{0,1,10,11\},\{0,1\},\{0,1,\square \},\delta ,0,,)$和$\delta :\{0,1,10,11\}\times \{0,1\}\to \{0,1,10,11\}\times \{0,1\}\times \{R,L,E,S\}$. 比如做一個以1的個數表示數值的加法運算，在磁帶上的數據是0000001110110000，就是3+2的意思。程式$\delta$如下：

0,0 -> 0,0R

0,1 -> 1,1R

1,0 -> 10,1R

1,1 -> 1,1R

10,0 -> 11,0L

10,1 -> 10,1R

11,0 -> E

11,1 -> 0,0S

第一行程式0,0->0,0R意思就是如果機器讀到0，就將其變成0，狀態變為0，讀寫頭向右移動一格. R就是向右移動一格，L就是向左移一格，E是錯誤，S是停機. xx,y -> aa,b中xx是當前狀態, y是當前格子的值, aa是程式下一步的狀態, b是當前格的修改值。

雖然這裏給出與上面不同形式的定義，但兩者是等價的，這裏的定義能完成的工作並不比上面的定義多。

步數	狀態（執行前）	狀態（執行後）	磁帶（執行前）	磁帶（執行後）
1	0	0	0000001110110000	0000001110110000
2	0	0	0000001110110000	0000001110110000
3	0	0	0000001110110000	0000001110110000
4	0	0	0000001110110000	0000001110110000
5	0	0	0000001110110000	0000001110110000
6	0	0	0000001110110000	0000001110110000
7	0	1	0000001110110000	0000001110110000
8	1	1	0000001110110000	0000001110110000
9	1	1	0000001110110000	0000001110110000
10	1	10	0000001110110000	0000001111110000
11	10	10	0000001111110000	0000001111110000
12	10	10	0000001111110000	0000001111110000
13	10	11	0000001111110000	0000001111110000
14	11	0	0000001111110000	0000001111100000

通用圖靈機

主條目：通用圖靈機

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

我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機$M$的編碼$\langle M\rangle$，然後模擬圖靈機$M$的運作，這樣的圖靈機稱為通用圖靈機（Universal Turing Machine）。現代電腦的計算模型其實就是這樣一種通用圖靈機，它先接受一段描述另一圖靈機，例如圖靈機$X$的action table的字串，然後執行寫給圖靈機$X$的程式$Y$，這樣通用圖靈機執行程式$Y$就像圖靈機$X$一樣，能正確執行並實現程式$Y$所描述的演算法。

圖靈機的其他版本

圖靈機有很多衍伸，但可以證明這些衍伸的計算能力都是等價的，即它們辨識同樣的語言類。證明兩個計算模型$A$和$B$的計算能力等價的基本思想是：用$A$和$B$相互模擬，若$A$可模擬$B$且$B$可模擬$A$，顯然他們的計算能力等價。注意這裏我們暫時不考慮計算的效率，只考慮計算的理論上「可行性」。

首先我們可以發現，改變圖靈機的帶字母表並不會改變其計算能力。例如我們可以限制圖靈機的帶字母表為$\{0,1\}$，這並不會改變圖靈機的計算能力，因為我們顯然可以用帶字母表為$\{0,1\}$的圖靈機模擬帶字母表為任意有限集合$\Gamma$的圖靈機。

另一個要注意的是，如果我們允許圖靈機的紙帶兩端都可以無限伸展，這並不能增加圖靈機的計算能力，因為我們顯然可以用只有紙帶一端能無限伸展的圖靈機來模擬這種紙帶兩端都可以無限伸展的圖靈機。

如果我們允許圖靈機的讀寫頭在某一步保持原地不動，那也不會增加其計算能力，因為我們可以用向左移動一次再向右移動一次來代替在原地不動。

其它的常見圖靈機衍伸包括：

• 多帶圖靈機
• 非確定型圖靈機
• 交替式圖靈機
• 列舉元

圖靈可計算性

• 圖靈可辨識語言
• 圖靈可判定語言
• 遞歸可列舉語言
• 可計算函數
• 遞歸函數
• 停機問題
• 可判定性
• 不可判定性
• 不可解度

其它等價的計算模型

除了圖靈機以外，人們還發明了很多其它的計算模型。包括：

• 暫存器機
• 遞歸函數
• λ演算
• 生命遊戲
• 馬可夫演算法

然而這些模型無一例外地都和圖靈機的計算能力等價，因此邱奇，圖靈和哥德爾 提出了著名的邱奇-圖靈論題：一切直覺上能計算的函數都可用圖靈機計算，反之亦然。

定理

• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理

參考文獻

• Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem（頁面存檔備份，存於互聯網檔案館）, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David（ed.）, The Undecidable, Hewlett, NY: Raven Press, 1965;
• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997. ISBN 0-534-94728-X

外部連結

• Visual Turing, a Turing machine interactive simulator/IDE（頁面存檔備份，存於互聯網檔案館）（free software for Windows）。
• Suzanne Brittons Turing Machine Simulator（java applet）。
• C++ Simulator of a Nondeterministic and Deterministic Turing Machine（頁面存檔備份，存於互聯網檔案館）（free software）。
• Citations from CiteSeer（頁面存檔備份，存於互聯網檔案館）