2.2. 图灵机¶
2.2.1. 图灵机¶
2.2.1.1. 通用计算模型¶
我们希望定义一个尽可能简单的通用计算模型。原因是我们想要理解计算的可能性边界，但如果"计算机"的定义很复杂，这就很难做到。但我们需要确信，无论我们选择什么模型，它都能真正代表"计算机"的所有基本能力。
"状态机"很容易理解。有许多不同的状态机，具有不同的能力。我们将讨论一个特定的状态机，称为 图灵机。当我们定义"能力"时，关键是 能力，而不是 效率。
任何此类"机器"的必要能力如下：
读取
写入
计算
图灵机定义如下。它有一条一维的带子，分成若干方格。这条带子向左和向右无限延伸。每个方格可以存储一个字符。机器有一个 I/O 头，在任何时刻都"在"一个方格上。机器的控制单元由一组抽象的 状态 定义。在任何给定时刻，机器被认为"处于"其中一个状态，并且在该状态下可以执行一组动作。从当前状态，机器读取当前方格上的符号，然后根据它看到的符号值执行以下操作：
用新符号覆盖该符号，
将带头向左（\(L\)）、向右（\(R\)）或停留（\(S\)）移动
带子上可以出现的字母是给定图灵机定义的重要组成部分。机器的 字母表 就是这些可以出现在输入中的字母。除了可以定义输入字符串的字母表字母外，还有空白字符。当谈论字符串时，由于空白难以看到，我们将使用 \(\#\) 字符来表示空白字符。注意，将 \(\#\) 包含在字母表中只是为了方便。我们希望能够阅读我们的规范而不被混淆。
机器的输入是带子的初始内容，通过列出从最左边的非空白带单元到最右边的非空白带单元的所有带方格来描述。当然，带子上必须有有限数量的非空白符号。输入字符串可能在定义输入的非空白方格之间有一些空白方格。
现在，我们知道在任何时刻机器都处于某个状态，并且输入头在带子上的某个方格下。机器读取符号，并通过进入某个状态（可能是当前状态，也可能是另一个状态）、在方格上写入某个字母（可能是与当前方格中相同的字母，也可能是另一个），然后将头向左移动一个方格、向右移动一个方格或将头留在当前方格来响应。这就是机器所能做的一切。
图灵机形式化定义为 ( \(Q\) , \(\Sigma\) , \(\Gamma\) , $s$, \(F\) , \(\delta\) )，其中
\(Q\) 是有限状态集。
\(\Sigma\) 是字母表。用于定义输入。
\(\Gamma\) 是另一个字母表，至少包含 \(\Sigma\) 和 \(\#\)。它可能包含其他符号，是计算过程中使用的字母表。
\(s \in Q\) 是 初始状态。
\(F \subset Q\) 是 最终状态 集。
\(\delta\) 是从 \(Q \times \Gamma\) 到 \(Q \times \Gamma \times \{L, R, S\})\) 的偏函数。
机器操作如下：对于 \(q \in Q\)，\(a \in \Sigma\) 和 \(\delta(q, a) = (p, b, m)\)，当处于状态 \(q\) 并扫描 \(a\) 时，进入状态 \(p\)，用 \(b\) 替换 \(a\)，并移动头（\(m\) 是 \(L\)、\(R\) 或 \(S\)）。
要进行计算，我们必须有一些关于开始和结束过程的约定。如果（1）机器进入任何 最终状态，或（2）它处于某个状态并扫描一个没有转换的字符，则机器立即停止。（注意，定义图灵机有很多方法，有些定义需要一个显式的拒绝状态。我们没有。）
我们也可以将图灵机描述为一个图，其节点是 \(Q\) 中的状态，边对应于 \(\delta\) 中的转换。此外，我们可以将机器的处理可视化为头在带子上的移动。在可视化中，当前带方格（头当前所在的位置）被高亮显示。
2.2.1.2. 解释图灵机¶
图灵机的一个 格局 如下所示：
这意味着图灵机处于状态 \(q\)，带子包含 \(\underline{a}aba\)，读/写头位置在下划线的'a'上。回想一下，我们假设在任何图灵机开始处理输入时，读/写头位置在最左边的非空白字符上。
不要忘记带子在两个方向上都是无限的。因此，在这个格局中，最左边的'a'的左边有无限多个空白方格，最右边的'a'的右边也有无限多个空白方格。
当机器从当前状态使用当前带字母（当前格局）找不到移动时，就会发生 停止格局。换句话说，如果没有定义 \(\delta\)，图灵机就会停止。注意，我们从未定义任何从任何最终状态出来的转换。所以之前我们说机器在任何最终状态或没有当前转换时停止有些冗余。但有两个这样的停止定义使得定义接受和拒绝字符串之间的差异变得容易。
计算 是一系列长度为 \(n \geq 0\) 的格局。
符号：给定字符串 \(w\)，格局的符号 \(\underline{w}\) 表示读/写头正在扫描 \(w\) 中最左边的字符。
\(M\) 在输入 \(w\) 上 停止 当且仅当 \((s, \underline{w})\) 产生某个停止格局。
\(M\) 在输入 \(w\) 上 挂起 如果 \((s, \underline{w})\) 产生某个挂起格局。
等等，什么？什么是"挂起"格局？当机器进入无限循环时就会挂起。任何时候你提供仅在条件满足时结束的循环机制，你也创造了可能允许无限循环发生的条件。考虑以下在 a 和 b 字符串上向右扫描直到看到'b'的机器。如果它从未看到'b'，那么它永远不会停止。这意味着任何时候输入字符串不包含'b'，它就会进入无限循环（或挂起）。
2.2.1.3. 图灵接受器和图灵转换器¶
图灵机计算从字符串到字符串的函数。形式化：设 \(f\) 是从 \(\Sigma^*_0\) 到 \(\Sigma^*_1\) 的函数。图灵机 \(M\) 计算 \(f\) 当，对于任何字符串 \(w \in \Sigma^*_0\)，如果 \(f(w) = u\) 则
对于某个状态 \(h \in F\) （即，\(M\) 的最终状态）。
这样的函数 \(f\) 称为 图灵可计算函数。
这是我们表达多个参数的方式：对于 \(f(w_1, ..., w_k) = u\)，
表达自然数函数的一种方法是使用 一元记号 表示数字。（记住，我们不关心什么是高效的，我们关心什么是可能的。）在这种情况下，我们将值 0 表示为空字符串。我们说 \(f: \mathbb{N} \rightarrow \mathbb{N}\) 由 \(M\) 计算，如果 \(M\) 计算 \(f': \{I\}^* \rightarrow \{I\}^*\)，其中 \(f'(I^n) = I^{f(n)}\) 对于每个 \(n \in \mathbb{N}\)。
2.2.1.4. 图灵可判定语言与图灵可接受语言¶
回想一下，我们定义了一个关于接受/拒绝输入字符串是否在指定语言中的约定：如果机器在最终状态停止，则字符串被接受为属于该语言；如果机器通过跟随未定义的转换停止，则字符串被拒绝。这里的关键是机器停止（有单独的接受或拒绝机制）。如果每个字符串都产生这两种结果之一，我们定义语言为 图灵可判定的。
不幸的是，还有第三种可能的结果：机器可能进入无限循环。
我们可以定义另一个概念： \(Turing-acceptable\) 。我们说机器 \(M\) 接受 字符串 \(w\) ，如果 \(M\) 在输入 \(w\) 上停机。那么，
\(M\) 接受一个语言当且仅当 \(M\) 在 \(w\) 上停机当且仅当 \(w \in L\) 。
如果存在某台图灵机接受某个语言，则该语言是 \(Turing-acceptable\) 。
因此，如果语言在每种输入上都停止，有两种不同的方式，我们可以判断字符串是否在语言中，则该语言是图灵可判定的。单独来说，如果语言在语言中的字符串上停止，在不在语言中的字符串上不停止，则该语言是图灵可接受的。
将任何图灵可判定机器转换为图灵可接受机器很容易。如果机器将拒绝字符串，那么只需通过向右移动进入无限循环，而不管看到的符号值如何。但是，每个图灵可接受机器都能转换为图灵可判定机器吗？
考虑这个例子：示例： \(\Sigma_0 = \{a, b\}\) , \(L = \{w \in \Sigma^*_0: w\ \mbox{contains at least one}\ a\}\) 。
这台机器是图灵可接受的。如果它看到'a'就停止，如果没有'a'就挂起。
这个语言是图灵可判定的吗？当然是。机器在看到#时不必向右运行，而是可以停止。这是修改后的机器：
我们所做的只是删除了看到空白符号时要执行的操作的转换。因此，机器停止而不是向右移动（从而开始无限循环）。
（你可能会问：但如果#右边有'a'怎么办？回想一下，我们只关心机器在合法开始格局中开始时的行为。）
但是，我们可以再次问：每个图灵可接受语言都是图灵可判定的吗？换句话说，每当图灵可接受机器将挂起时，我们能否 总是 用逻辑替换它以触发不存在的转换？这被称为 停机问题。
事实证明，我们可以 证明 总是存在无法从图灵可接受转换为图灵可判定的语言。换句话说，我们可以 证明 停机问题是不可解的。
2.2.1.5. 制造更复杂的机器¶
显然，图灵机可以接受输入并修改它。我们将看到这如何导致强大的计算能力的示例，即使它看起来还不那么强大。为了快速了解它们的能力，考虑以下相对简单的机器来接受 \(L(a^nb^nc^n)\)。这很重要，因为这个语言实际上不是上下文无关的！这意味着这个简单的图灵机正在做一些任何 DFA、NFA 或 PDA 都无法做到的事情！
但是，虽然图灵机可能能够做强大的事情，但在单个状态级别操作时，编程它们可能变得相当困难和繁琐。事实上，在某些方面，它可能感觉像编写机器码或汇编语言。现代软件开发成功的秘诀是建立更强大的工具，特别是通过将行为打包在一起并操作这些包。我们可以希望用图灵机建立类似的能力。
引理：如果
\[(q_1, w_1\underline{a_1}u_1) \vdash_M^* (q_2, ww_2\underline{a_2}u_2)\]对于字符串 \(w\)，并且
\[(q_2, w_2\underline{a_2}u_2) \vdash^*_M (q_3, w_3\underline{a_3}u_3),\]那么
\[(q_1, w_1\underline{a_1}u_1) \vdash^*_M (q_3, ww_3\underline{a_3}u_3).\]洞察：因为 \((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_2\) 在 \(M_1\) 完成时检索控制权。
以下是一些基本机器和符号
\(|\Sigma|\) 符号写入机器（每个符号一个）： 任何给定字母 \(\sigma\) 有一个名为 \(\sigma\) 的符号写入机器。
头移动机器，名为 \(R\) 和 \(L\)，相应地移动头。
开始状态用 \(>\) 表示。
除了（例如） \(\#\) 之外的任何内容的转换都标记为 \(\overline{\#}\)
机器的多个副本获得上标：\(R^2\) 表示 向右移动两次。
复制机器：将 \(\#w\underline{\#}\) 转换为 \(\#w\#w\underline{\#}\)。注意开始状态中的 \(L_{\#}\) （意味着向左移动直到看到第一个空白）和底部的 \(L\#\) （意味着向左移动然后写入一个空格）之间的差异。
2.2.1.6. 图灵机扩展¶
当我们给计算系统扩展或新功能时，有时它们会改变系统能力的一些基本内容。例如，当我们向算法添加非确定性时，我们 可能 将底层问题的成本从指数时间改为多项式时间。但是，其他改变没有什么根本性的。就图灵机而言，我们关心的是机器能做什么，而不是做它需要多长时间。非确定性是否帮助我们解决停机问题？不。同样，以下扩展不会增加图灵机的能力。
限制带子只在一个方向无限
我们的第一个示例实际上表明一些限制没有区别。许多形式语言教科书将基本图灵机呈现为只在一个方向无限延伸的带子。下图显示我们可以轻松地用单向无限带模拟双向无限带。
想法是将双向无限带在中间弯曲，并将两个方向存储在单个单元中。这需要大大扩展字母表，因为我们现在需要能够表示两个字符的任何组合。这将需要更多状态，可能需要更多时间。但在能力方面没有任何新内容。
多个带子（每个都有自己的头）
同样，我们可以通过将多个符号编码到单个表单元中来模拟这个。例如，要模拟两个带子（每个都有一个头），我们在每个单元中编码相应的两个符号，以及两个二进制标记来指示带子头当前是否在两个带子的相应单元中。
一个带子上的多个头
这比编码多个带子更容易。我们只需将头编码到带子上，并模拟移动它们。
二维"带子"
我们需要做的就是找到从 2D 到 1D 的映射，这相当容易。一种方法是按对角线工作，顺序为 (0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0)，依此类推。
非确定性
我们可以依次模拟非确定性行为，执行所有长度 1 的计算，然后长度 2，依此类推，直到我们达到非确定性选择之一的停止状态。所以我们看到，虽然非确定性可以节省大量时间，但它不会改变（最终）可以做什么。
