图灵机¶

约 1801 个字 9 张图片预计阅读时间 9 分钟

FA只能读取纸带上的内容并转移状态,PDA可以读取纸带上的内容并操作栈顶,而图灵机则可以读取纸带上的内容并对纸带进行读写操作.这意味着图灵机是最强大的自动机,任何可以被计算的问题都可以被图灵机解决.

图灵机

图灵机是一个五元组\(M=(K,\Sigma,\delta,s,H)\),其中:

\(K\) 是一个有限的状态集。
\(\Sigma\) 是一个字母表，其中：
- 包含 \(\sqcup\) (空白符号) 和 \(\triangleright\) (左端符号)。
- 不包含符号 \(\rightarrow\) 和 \(\leftarrow\)。
\(s \in K\) 是初始状态。
\(H \subseteq K\) 是停机状态集。
\(\delta: (K - H) \times \Sigma \to K \times (\Sigma \cup \{\leftarrow, \rightarrow\})\) 是转移函数，满足：
- 对于任意 \(q \in K - H\)，如果 \(\delta(q, \triangleright) = (p, b)\)，那么 \(b = \rightarrow\)。
- 对于任意 \(q \in K - H\) 和 \(a \in \Sigma\)，如果 \(\delta(q, a) = (p, b)\)，那么 \(b \neq \triangleright\)。

用图来表示图灵机就是:

图灵机示意图

也就是在状态\(q\)下读取纸带上的符号\(a\),然后根据转移函数\(\delta\)转移到状态\(p\),并且对纸带进行操作,要么写入一个符号,要么向左移动,要么向右移动.

一个图灵机识别语言的例子就是

图灵机识别语言示意图

在识别语言\(L=\{a^nb^n|n\geq1\}\)时,图灵机会先扫描纸带上的\(a\),将其替换为\(x\),然后继续向右扫描,直到遇到第一个\(b\),将其替换为\(y\),然后返回纸带的开头,继续扫描下一个\(a\),重复这个过程,直到所有的\(a\)都被替换为\(x\),然后继续扫描纸带,没有可识别的\(a\)了,在识别到\(y\)时就会进入下一个状态,这个状态仅识别\(y\),也就是说此时如果还有多余的\(b\)的话,图灵机就会拒绝输入.

Turing Machine Configuration¶

图灵机的配置如下图所示,由其当前的状态与两部分纸带内容组成:

图灵机配置示意图

写作配置\((q,\triangleright x,y)\),其中\(q\)是当前状态,\(x\)是纸带上读头左侧的内容,\(y\)是纸带上读头右侧的内容,一直到最后一个非空白符号为止.

当然,这个配置也可以写成二元组的形式\((q,\triangleright\ \underline{x}y)\),其中\(x\)和\(y\)的定义与上面相同.

更多的例子:

图灵机配置示意图

Computation

设 \(M = (K, \Sigma, \delta, s, H)\) 是一个图灵机，并考虑 \(M\) 的两个配置：\((q_1, w_1\underline{a_1}u_1)\) 和 \((q_2, w_2\underline{a_2}u_2)\)，其中 \(a_1, a_2 \in \Sigma\)。

我们说 \((q_1, w_1\underline{a_1}u_1)\) 在一步之内产生 \((q_2, w_2\underline{a_2}u_2)\)，记作 \((q_1, w_1\underline{a_1}u_1) \vdash_M (q_2, w_2\underline{a_2}u_2)\)，当且仅当，对于某个 \(b \in \Sigma \cup \{\rightarrow, \leftarrow\}\)，有 \(\delta(q_1, a_1) = (q_2, b)\)，并且满足以下三种情况之一：

写入 (Write): \(b \in \Sigma\)
- \(w_1 = w_2\)
- \(u_1 = u2\)
- \(a_2 = b\)
左移 (Move Left): \(b = \leftarrow\)
- \(w_1 = w_2a_2\)
- 并且满足以下任一条件：
  - 如果 \(a_1 \neq \sqcup\) 或 \(u_1 \neq \epsilon\)，则 \(u_2 = a_1u_1\)。例如,\((q_1,xy\underline{a_1}z) \vdash_M (q_2,x\underline{y}a_1z)\)。
  - 如果 \(a_1 = \sqcup\) 且 \(u_1 = \epsilon\)，则 \(u_2 = \epsilon\)。例:如,\((q_1,xa_1\underline{\sqcup}) \vdash_M (q_2,\underline{x})\)。
右移 (Move Right): \(b = \rightarrow\)
- \(w_2 = w_1a_1\)
- 并且满足以下任一条件：
  - 如果 \(a_2 \neq \sqcup\) 或 \(u_2 \neq \epsilon\)，则 \(u_1 = a_2u_2\)。例:\((q_1,xy\underline{a_1}z) \vdash_M (q_2, xya_1\underline{z})\)。
  - 如果 \(a_2 = \sqcup\) 且 \(u_2 = \epsilon\)，则 \(u_1 = \epsilon\)。例:\((q_1,x\underline{a_1}) \vdash_M (q_2,xa_1\underline{\sqcup})\)。

同样,这个推导也有传递和自反闭包.和之前定义的一样,令\(\vdash_M^*\)表示推导的自反传递闭包,\(\vdash_M^n\)表示经过n步推导.

Basic Machine¶

我们将图灵机归结为最简单的两种:Symbol Writing Machine和Hand Moving Machine.

它们的共同特点就是,只做一种操作,要么只写符号,要么只移动读头.只有两种状态.

对于一个固定的字母表 \(\Sigma\) 和一个符号 \(a \in \Sigma \cup \{\leftarrow, \rightarrow\} - \{\triangleright\}\)，我们可以定义一个图灵机 \(M_a = (\{s, h\}, \Sigma, \delta, s, \{h\})\)，其中：

对于每个 \(b \in \Sigma - \{\triangleright\}\)，转移函数为 \(\delta(s, b) = (h, a)\)。
自然地，\(\delta(s, \triangleright) = (s, \rightarrow)\)。

这个图灵机 \(M_a\) 的作用是在读到任何非左端符号后，执行动作 a（写入符号 a、左移或右移），然后立即停机。

\(R_{\sqcup}\): 找到当前磁带头右侧的第一个空白符号并停机。实现机制是如果读到非空白符号就右移,读到空白符号就停机.

\(R_{\sqcup}\)示意图
\(R_{\bar{\sqcup}}\): 找到当前磁带头右侧的第一个非空白符号并停机。实现机制是如果读到空白符号就右移,读到非空白符号就停机.

\(R_{\bar{\sqcup}}\)示意图
\(L_{\sqcup}\): 找到当前磁带头左侧的第一个空白符号并停机。

\(L_{\sqcup}\)示意图
\(L_{\bar{\sqcup}}\): 找到当前磁带头左侧的第一个非空白符号并停机。

\(L_{\bar{\sqcup}}\)示意图

组合图灵机¶

我们可以将多个图灵机组合成一个更复杂的图灵机，以实现更复杂的功能。例如，我们可以根据纸带上的符号来决定下一个要执行的图灵机。

形式化定义

正式地，令 \(M_i = (K_i, \Sigma, \delta_i, s_i, H_i)\) 为图灵机（其中 \(i = 1, 2, 3\)）。组合后的图灵机为 \(M = (K, \Sigma, \delta, s, H)\)，其中：

\(K = K_1 \cup K_2 \cup K_3\)
\(s = s_1\)
\(H = H_2 \cup H_3\)

对于每个 \(\sigma \in \Sigma\) 和 \(q \in K - H\)，转移函数 \(\delta(q, \sigma)\) 定义如下：

如果 \(q \in K_1 - H_1\)，那么 \(\delta(q, \sigma) = \delta_1(q, \sigma)\)。
如果 \(q \in K_2 - H_2\)，那么 \(\delta(q, \sigma) = \delta_2(q, \sigma)\)。
如果 \(q \in K_3 - H_3\)，那么 \(\delta(q, \sigma) = \delta_3(q, \sigma)\)。
如果 \(q \in H_1\)，那么：
- 若 \(\sigma = a\)，则 \(\delta(q, \sigma) = s_2\)
- 若 \(\sigma = b\)，则 \(\delta(q, \sigma) = s_3\)
- 否则，\(\delta(q, \sigma) \in H\)

形成了如下的结构：

        +-------------------+
        |        M1         |
        |   +-----------+   |
        |   |           |   |
    --> | s1|           |h1 |---+
        |   |           |   |   |
        |   +-----------+   |   |
        +-------------------+   |
              |                 |
           a  |                 | b
              v                 v
        +-------------------+   +-------------------+
        |        M2         |   |        M3         |
        |   +-----------+   |   |   +-----------+   |
        |   |           |   |   |   |           |   |
        | s2|           |h2 |   | s3|           |h3 |
        |   |           |   |   |   |           |   |
        |   +-----------+   |   |   +-----------+   |
        +-------------------+   +-------------------+

箭头表示状态转移的方向。
当 \(M_1\) 运行到 \(h_1\)，根据当前读到的符号（\(a\) 或 \(b\)），分别跳转到 \(M_2\) 或 \(M_3\) 的起始状态继续运行。

使用图灵机¶

图灵机 M 接受输入字符串 \(w \in (\Sigma - \{\sqcup, \triangleleft\})^*\)，如果从初始配置 \((s, \triangleleft\ \underline{\sqcup}w)\) 出发，经过若干步推导后，能够到达一个接受配置（
令 \(\Sigma_0 \subseteq \Sigma - \{\sqcup, \triangleleft\}\) 为一个字母表 —— 即 M 的输入字母表。
M 决定 \(L \subseteq \Sigma^*\) 当且仅当对所有 \(w \in \Sigma^*\)，有：
- \(w \in L\) 当且仅当 M 接受 \(w\)；
- \(w \notin L\) 当且仅当 M 拒绝 \(w\)。
如果存在一个图灵机能够判定 \(L\)，则称语言 \(L\) 是递归的（recursive）。

一个例子如下: