抽象的計算機器：圖靈機

圖靈機（Tur­ing ma­chine）是由圖靈（Alan Tur­ing, 1912–1954）所提出的一種計算模型。圖靈機具有各式不同的種類，包含確定性圖靈機、非確定性圖靈機等；本文簡介確定性圖靈機。

1　圖靈機

1.1　字元集

本文中，我們設 $\Sigma = \{\texttt{0}, \texttt{1}, \texttt{\#}\}$ 與 $\Gamma = \Sigma \cup \{\sqcup\} \period$

我們以 $\Sigma^*$ 代表字元均在 $\Sigma$ 中的有限字串所構成的集合。

設集合 $T$ 包含所有元素均在 $\Gamma$ 中且僅有有限項不為 $\sqcup$ 的無窮序列。

對序列 $t = (t_n)_{n \geq 0} \in T$ 與任意非負整數 $i \comma$我們記 $t(i) = t_i \period$

1.2　圖靈機

設 $k$ 為不小於 2 的整數；設 $Q$ 為一集合，其中 $q_0, q_+, q_- \in Q$ 相異；設 \[\begin{split} \delta \colon (Q \setminus \{q_+, q_-\}) \times \Gamma^k \to Q \times \Gamma^k \times \{-1, 0, 1\}^k \end{split}\] 為一函數，其中對任意 $q \in Q \setminus \{q_+, q_-\} \jcomma (a_i)_{i=0}^{k-1} \in \Gamma^k$ 與 \[\begin{split}(q' \cm (b_i)_{i=0}^{k-1} \cm (h_i)_{i=0}^{k-1}) = \delta(q \cm (a_i)_{i=0}^{k-1})\end{split}\] 均有 $b_0 = a_0$ 與 $h_1 \in \{0, 1\} \period$此時我們稱 \[\begin{split}M = (Q \cm \delta \cm q_0 \cm q_+ \cm q_-)\end{split}\] 為一具有輸入、輸出紙帶與 $k-2$ 條工作紙帶的確定性圖靈機（de­ter­min­is­tic Tur­ing ma­chine）。

• $Q$ 中的元素稱為 $M$ 的狀態（state）：其中 $q_0$ 為初始狀態，$q_+$ 為接受狀態，$q_-$ 為拒絕狀態。
• $\delta$ 則稱為 $M$ 的轉移函數（tran­si­tion func­tion）。

1.3　組態

設 $k$ 為不小於 2 的整數，且 $M = (Q \cm \delta \cm q_0 \cm q_+ \cm q_-)$ 為一具有輸入紙帶、輸出紙帶與 $k-2$ 條工作紙帶的確定性圖靈機。

對任意 $q \in Q \jcomma t_0 \cm t_1 \cm \ldots \cm t_{k-1} \in T$ 與非負整數 $p_0 \cm p_1 \cm \ldots \cm p_{k-1} \comma$我們稱 \[\begin{split}C = (q, t_0, p_0, t_1, p_1, \ldots, t_{k-1}, p_{k-1})\end{split}\] 為確定性圖靈機 $M$ 的一個組態（con­fig­u­ra­tion）。

• $q$ 即為組態 $C$ 對應的狀態。
• 對任意 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\} \comma$$t_i$ 即為組態 $C$ 中索引值為 $i$ 的紙帶上的字元序列。索引值 0、1 的紙帶分別為輸入紙帶與輸出紙帶，而其他的紙帶即為工作紙帶。
• 對任意 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\} \comma$$p_i$ 即為組態 $C$ 中索引值為 $i$ 的紙帶上的讀寫頭的位置。

當圖靈機的輸入為字串 $s = a_0a_1 \cdots a_{n-1} \in \Sigma^*$ 時，此時圖靈機的起始組態（start con­fig­u­ra­tion）為 \[\begin{split}C_0(s) = (q, t_0, p_0, t_1, p_1, \ldots, t_{k-1}, p_{k-1}) \comma\end{split}\]其中

1. $q = q_0 \semicolon$
2. $t_0 = a_0 a_1 \cdots a_{n-1}\,\blank \blank \cdots \semicolon$
3. 對所有 $i \in \{1 \cm 2 \cm \ldots \cm k \varminus 1\}$ 均有 $t_i = \blank \blank \cdots \semicolon$
4. 對所有 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\}$ 均有 $p_i = 0 \period$

對任意組態 \[\begin{split}C = (q, t_0, p_0, t_1, p_1, \ldots, t_{k-1}, p_{k-1}) \comma\end{split}\] 若對每個 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\}$ 設 $a_i = t_i(p_i) \comma$且 \[\begin{split}\delta(q, (a_i)_{i=0}^{k-1}) = (q', (b_i)_{i=0}^{k-1}, (h_i)_{i=0}^{k-1}) \comma\end{split}\] 則我們定義 $C$ 經由 $M$ 的後繼組態為 \[\begin{split}C' = (q', t_0', p_0', t_1', p_1', \ldots, t_{k-1}', p_{k-1}') \comma\end{split}\] 其對所有 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\}$ 滿足 $p_i' = \max\{0, p_i \varplus h_i\}$ 與 \[\begin{split} t_i'(\mkern2muj) = \begin{cases} b_i & \when j = p_i \\ t_i(\mkern2muj) & \when j \neq p_i \end{cases} \comma \end{split}\] 其中 $j$ 為任意非負整數。若 $C'$ 為 $C$ 經由 $M$ 的後繼組態，則我們記 $C \overset{M}\to C' \period$

我們稱滿足 $q \in \{q_+, q_-\}$ 的組態 \[\begin{split}C = (q, t_0, p_0, t_1, p_1, \ldots, t_{k-1}, p_{k-1})\end{split}\] 為一停機組態。此時若 $q = q_+ \comma$則 $C$ 為接受組態；若 $q = q_- \comma$則 $C$ 為拒絕組態。

1.4　接受、拒絕、停機

對於輸入 $s = a_0a_1 \cdots a_{n-1} \comma$設 $C_0 = C_0(s)$ 為對應的起始組態。此時有兩種可能的狀況：

1. 存在一正整數 $T$ 使得 \[\begin{split}C_0 \overset{M}\to C_1 \overset{M}\to \cdots \overset{M}\to C_T \comma\end{split}\] 其中 $C_T$ 為停機組態。此時我們稱 $M$ 對輸入 $s$ 會停機。若 $C_T$ 為接受組態，則我們稱 $M$ 接受 $s \semicolon$否則我們稱 $M$ 拒絕 $s \period$
2. 我們有 \[\begin{split}C_0 \overset{M}\to C_1 \overset{M}\to \cdots \comma\end{split}\] 即 $M$ 對輸入 $s$ 不會停機。

我們稱 $M$ 所接受的字串所構成的集合為 $M$ 所識別（rec­og­nize）的語言；若 $M$ 對任意輸入字串均會停機（即必定接受或拒絕輸入字串），則此時我們稱 $M$ 所接受的字串所構成的集合為 $M$ 所決定（de­cide）的語言。

1.5　遞迴可枚舉語言與遞迴語言

設 $L \subseteq \Sigma^*$ 為一語言。

若存在一確定性圖靈機識別 $L \comma$則我們稱 $L$ 為一遞迴可枚舉（re­cur­sive­ly enu­mer­able）語言。所有遞迴可枚舉語言所構成的集合記作 $\mathbf{RE} \period$

若存在一確定性圖靈機決定 $L \comma$則我們稱 $L$ 為一遞迴（re­cur­sive）語言。所有遞迴語言所構成的集合記作 $\mathbf{R} \period$

2　例子

範例 1　設 $L_\mathrm{EQ} = \{\hash\.s\.\hash\.s\.\hash: s \in \{\zero, \one\}^*\} \period$我們說明 $L_\mathrm{EQ} \in \mathbf{R} \period$

設 $M = (Q, \delta, q_0, q_+, q_-)$ 為一具有輸入、輸出紙帶與 1 條工作紙帶的確定性圖靈機，其中：

• $Q = \{q_0, q_1, q_2, q_3, q_+, q_-\}$ 共包含 6 個狀態。
• $\delta \colon (Q \setminus \{q_+, q_-\}) \times \Gamma^{\.3} \to Q \times \Gamma^{\.3} \times \{-1, 0, 1\}^3$ 定義如下： \[\begin{split} \delta(q, a_0, a_1, a_2) = \begin{cases} (q_-, a_0, \blank, a_2, 0, 0, 0) & \when q = q_0\ \textrm{且}\ a_0 \neq \hash \\ (q_1, a_0, \blank, a_0, 1, 0, 1) & \when q = q_0\ \textrm{且}\ a_0 = \hash \\ (q_-, a_0, \blank, a_2, 0, 0, 0) & \when q = q_1\ \textrm{且}\ a_0 = \blank \\ (q_1, a_0, \blank, a_0, 1, 0, 1) & \when q = q_1\ \textrm{且}\ a_0 \in \{\zero, \one\} \\ (q_2, a_0, \blank, a_0, 0, 0, -1) & \when q = q_1\ \textrm{且}\ a_0 = \hash \\ (q_2, a_0, \blank, a_2, 0, 0, -1) & \when q = q_2\ \textrm{且}\ a_2 \neq \hash \\ (q_3, a_0, \blank, a_2, 1, 0, 1) & \when q = q_2\ \textrm{且}\ a_2 = \hash \\ (q_-, a_0, \blank, a_2, 0, 0, 0) & \when q = q_3\ \textrm{且}\ a_0 \neq a_2 \\ (q_3, a_0, \blank, a_2, 1, 0, 1) & \when q = q_3\ \textrm{且}\ a_0 = a_2 \neq \blank \\ (q_+, a_0, \blank, a_2, 0, 0, 0) & \when q = q_3\ \textrm{且}\ a_0 = a_2 = \blank \\ \end{cases} \end{split}\]

此時圖靈機 $M$ 決定 $L_\textrm{EQ} \period$