22.1.1. 通用计算模型¶

在本模块中，我们寻求定义一个尽可能简单的通用计算模型。 原因是我们希望能够理解计算可能性的极限，而这 在一个对"计算机"的复杂定义下相当难做到。 但是，我们也需要确信，无论我们选择哪个模型，它 确实代表了"计算机"的所有基本能力。 特别是，我们希望这个模型能够计算我们的"普通"计算机 所能计算的任何函数。

"状态机"很容易理解。 有若干种不同的状态机，能力各不相同。 我们将讨论其中特别的一种，称为 图灵机。 在讨论"能力"时，关键是 能力，而不是 效率。

任何此类"机器"的必要能力如下：

• 读

• 写

• 计算

图灵机的定义如下。 它有一条被划分为方格的纸带，有一个固定的左端， 并向右无限延伸。 每个方格能存储一个字符。 机器有一个 I/O 头，在任一时刻它"停在" 其中一个方格上。 机器的控制单元由一组抽象 状态 定义。 在任何给定时刻，机器被认为 "处于"某个状态，并且在该状态下有一组可以执行的动作。 从当前状态出发，机器读取 当前方格上的符号，然后可以执行下面之一：

• 改变当前符号。

• 把 I/O 头向左或向右移动一个方格。

按照惯例，如果头移出 纸带的左端，或者控制单元把机器送入一个 特别指定的 停机状态，机器就停止运行。

机器的输入是纸带的初始内容，通过从左到右 列出从最左到最右非空带上的所有方格来描述。 自然，纸带上非空符号的个数必须有限。 机器的 字母表 由一些字母组成， 包括特殊符号 \(\#\)，它表示给定方格上的空 符号。

图灵机形式化地定义为一个四元组 (\(K\), \(\Sigma\), $delta$, $s$)，其中

• \(K\) 是有限状态集（不包括 \(h\)，即 停机状态）。

• \(\Sigma\) 是一个字母表（包含 \(\#\)，不包含 \(L\) 或 \(R\)）。

• \(s \in K\) 是 初始状态。

• \(\delta\) 是从 \(K \times \Sigma\) 到 \((K \cup \{h\}) \times (\Sigma \cup \{L, R\})\) 的函数。

注意，把 \(\#\) 包含进这个语言只是为了 方便。 我们希望在阅读我们规格说明时不会混淆。

如果 \(q \in K\)、\(a \in \Sigma\) 并且 \(\delta(q, a) = (p, b)\)， 那么在状态 \(q\) 下扫描 \(a\) 时， 进入状态 \(p\) 并

1. 如果 \(b \in \Sigma\)，则把 \(a\) 替换为 \(b\)。

2. 否则（\(b\) 是 \(L\) 或 \(R\)）：移动头。

22.1.2. 解释图灵机¶

图灵机的一个 格局 看起来像这样：

当 \(q\) 是 \(h\) （停机状态）时， 就会发生 停机格局。

当 I/O 头从纸上最左边的方格向左 移动时，就会发生 挂起格局。

计算 是某一长度 \(n \geq 0\) 的格局序列。 第一个机器例子从起始格局开始的执行如下所示：

我们说 \(M\) 在输入 :math:`w` 上停机，当且仅当 \((s, \#w\underline{\#})\) 推出某个停机格局。

如果 \((s, \#w\underline{\#})\) 推出某个挂起格局， 则称 \(M\) 在输入 :math:`w` 上挂起。 这意味着 要么 从左端向左移动 要么 进入无限循环。

图灵机计算从字符串到字符串的函数。 形式化地：设 \(f\) 是从 \(\Sigma^*_0\) 到 \(\Sigma^*_1\) 的函数。 当且仅当对任何 \(w \in \Sigma^*_0\)，如果 \(f(w) = u\)， 那么图灵机 \(M\) 计算 \(f\)：

这样的函数 \(f\) 被称为 图灵可计算函数。

下面是我们表达多个参数的方式： 对于 \(f(w_1, ..., w_k) = u\)，

表达自然数上函数的一种方式是用 一元记法 表示一个数。 （记住，我们不关心是否高效，我们关心 是否可能。） 在这种情况下，我们把值 0 表示为空字符串。 我们说如果 \(M\) 计算 \(f': \{I\}^* \rightarrow \{I\}^*\)， 其中对每个 \(n \in \mathbb{N}\) 有 \(f'(I^n) = I^{f(n)}\)，则 \(M\) 计算 \(f: \mathbb{N} \rightarrow \mathbb{N}\)。

22.1.3. 图灵可判定与图灵可接受语言¶

图灵可判定 的语言 \(L \subset \Sigma_0^*\) 当且仅当函数 \(\chi_L: \Sigma^*_0 \rightarrow \{\fbox{Y}, \fbox{N}\}\) 是图灵可计算的，其中对每个 \(w \in \Sigma^*_0\)，

例子：设 \(\Sigma_0 = \{a\}\)，设 \(L = \{w \in \Sigma^*_0: |w|\ \mbox{is even}\}\)。

\(M\) 从右到左擦除标记，当前奇偶性 用状态编码。 一旦到达左侧的空白，就标记 \(\fbox{Y}\) 或 \(\fbox{N}\)，视情况而定。

对计算的看法有很多。 一种是把函数看作输入到输出的映射 （例如 \(N \rightarrow N\)，或 字符串到字符串）。 另一种是判断一个字符串是否属于某种语言。

如果 \(M\) 在输入 \(w\) 上停机，则 \(M\) 接受 字符串 \(w\)。

• \(M\) 接受一个语言当且仅当 :math:M ` 在 :math:` w ` 上停机，当且仅当 :math:` w in L ` 。

• 如果存在某台图灵机接受某个语言，则该语言是 \(Turing-acceptable\) 。

例子：\(\Sigma_0 = \{a, b\}\)， \(L = \{w \in \Sigma^*_0: w\ \mbox{contains at least one}\ a\}\)。

这种语言图灵可判定吗？ 当然。不必只是向左运行，而是调用另一个表示 "见过一个 \(a\)"的状态，如果在该状态下到达 \(\#\) 就打印 \(\fbox{Y}\)，否则打印 \(\fbox{N}\)。

每个图灵可判定的语言都是图灵可接受的， 因为如果机器本可以打印 \(\fbox{Y}\)，那么 这台机器可以改为停机， 或者如果机器本可以打印 \(\fbox{N}\)， 那么它可以向左挂起。

每个图灵可接受的语言都图灵可判定吗？ 这就是停机问题。

当然，如果图灵可接受的语言会停机， 我们就写 \(\fbox{Y}\)。 但如果图灵可接受的语言会挂起， 我们是否 总是 能用改为写 \(\fbox{N}\) 的逻辑 替换它？ 例子：考拉兹函数。

22.1.4. 构造更复杂的机器¶

引理：如果

对某个字符串 \(w\) 成立，并且

那么

洞察：因为 \((q_2, w_2\underline{a_2}u_2) \vdash^*_M (q_3, w_3\underline{a_3}u_3)\)， 这个计算必定在不把磁头移到 \(w_2\) 左方的情况下进行。 机器无法"感知"纸带的左端。 （如果它移到了左边，它就会挂起。） 因此，即使磁头不在纸带的左端，它也不会移到 \(w_2\) 的 左方。

这意味着图灵机的计算可以组合成 更大的机器：

• \(M_2\) 准备字符串作为 \(M_1\) 的输入。

• \(M_2\) 在输入末尾把控制交给 \(M_1\) 的 I/O 头。

• 当 \(M_1\) 完成时，\(M_2\) 收回控制。

下面是一些基本的机器和记法：

• \(|\Sigma|\) 台写符号机（每个符号一台）： 任意给定的字母 \(\sigma\) 都有一台名为 \(\sigma\) 的写符号机。

• 移动磁头的机器，命名为 \(R\) 和 \(L\)，适当地移动 磁头。

• 起始状态用 \(>\) 表示。

• 在（例如）:math:# 之外的东西上的转移被标记 为 \(\overline{\#}\)。

• 机器的多份副本用上标表示：\(R^2\) 指 向右移动两次。

22.1.5. 图灵机的扩展¶

当我们给计算系统添加扩展或新功能时， 有时它们改变了系统能力的一些根本性东西。 例如，当我们向算法添加非确定性时，我们 可能 把底层问题的代价从指数时间变为 多项式时间。 但是，其他改变不会带来根本性的不同。 就图灵机而言，我们关心的是机器能做什么， 而不是做这件事要花多长时间。 非确定性会帮助我们解决停机问题吗？ 不会。 同样，下面的扩展也不会增加图灵机的 能力。

• 提供双向无限纸带

  这不会给图灵机带来新的能力。 为了弄清这一点，我们可以用标准的单向无限纸带 来模拟双向无限纸带的行为。 只需把无限纸带在中间折一下，把纸带的两个方向 都存进单个单元格。 这需要一个大大扩充的字母表，因为我们现在需要能够 表示两个字符的任何组合。 这将需要更多的状态，可能也需要更多的时间。 但在能力方面它不允许任何新的东西。

• 多条纸带（每条都有自己的头）

  同样，我们可以通过把多个符号编码进单个 表格单元格来模拟它。 例如，要模拟两条纸带（每条都有一个头），我们在每个 单元格中编码相应的两个符号，以及两个二进制标记 来指示纸带头当前是否位于两条纸带中对应 的单元格。

• 单条纸带上的多个头

  这比编码多条纸带更容易。 我们只需把磁头编码到纸带上，并模拟它们来回 移动。

• 二维 tape

  我们只需要找到一个从 2D 到 1D 的映射，这 相当容易。 一种方法是以对角线的顺序工作，顺序为 (0, 0)、(0, 1)、 (1, 0)、(0, 2)、(1, 1)、(2, 0)，依此类推。

• 非确定性

  我们可以按顺序模拟非确定性行为，先做所有 长度 1 的计算，然后长度 2 的，依此类推，直到我们 到达其中一个非确定性选择的停机状态。 所以我们看到，虽然非确定性可以节省大量时间，但它 不会改变（最终）能完成什么。