圖靈機

1936年，阿蘭·圖靈提出了一種抽象的計算模型 ── 圖靈機 (Turing Machine)。圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

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

而在每個階段，人要決定下一步的動作，依賴於 (a) 此人當前所關注的紙上某個位置的符號和(b) 此人當前思維的狀態。為了模擬人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 $\square$ 表示空白。紙帶上的格子從左到右依此被編號為 0, 1, 2, ... ，紙帶的右端可以無限伸展。
一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。
一個狀態寄存器。它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。
一套控制規則。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態寄存器的值，令機器進入一個新的狀態。

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

圖靈機的形式化定義

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

$Q$ 是狀態集合；
$\Sigma$ 是輸入字母表，其中不包含特殊的空白符 $\square$ ；
$\Gamma$ 是帶字母表，其中 $\square \in \Gamma$ 且 $\Sigma \subset \Gamma$ ；
$\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ 是轉移函數，其中 $L,R$ 表示讀寫頭是向左移還是向右移；
$q_{0}\in Q$ 是起始狀態；
$q_{accept}\in Q$ 是接受狀態。
$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})$ 是一台圖靈機，

$M$ 的帶描述(tape description)是一個函數 $F:\mathbb {N} \to \Gamma$ ，其中 $F(i)$ 表示 $M$ 的帶上第 $i$ 個格子中的符號；
$M$ 的格局(configuration)是一個三元組 $(F,q,e)$ ，其中 $F:\mathbb {N} \to \Gamma$ 是當前的帶描述， $q\in Q$ 是當前的狀態， $e\in \mathbb {N}$ 是當前讀寫頭所處的位置；
設 $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}$ 。
設 $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}$ ，使得

$C_{1}$ 是 $M$ 在輸入 $\omega$ 上的起始格局，即 $C_{1}=(F,q,e)$ ，其中 $F_{1}(i)={\begin{cases}\omega _{i}&0\leq i\leq n-1\\\square &{\mbox{otherwise}}\end{cases}}$
$C_{i}\to _{M}C_{i+1}$ ，其中 $i=1,2,\ldots ,k-1$ ；
$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)$ 。

圖靈機的例子

[TODO: 這裡需要補充幾個例子]

通用圖靈機

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

我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機 $M$ 的編碼 $\langle M\rangle$ ，然後模擬 $M$ 的運作，這樣的圖靈機稱為通用圖靈機(Universal Turing Machine)。現代電子計算機其實就是這樣一種通用圖靈機，它能接受一段描述其他圖靈機的程序，並運行程序實現該程序所描述的算法。

圖靈機的變種

圖靈機有很多變種，但可以證明這些變種的計算能力都是等價的，即它們識別同樣的語言類。證明兩個計算模型 $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 053494728X

外部鏈結

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