Turing Machine⚓︎

定义

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

• \(K\)：状态的有限集合
• \(\Sigma\)：字母表，包含空符号 \(\sqcup\) 和左端符号 \(\triangleright\)，但不包含符号 \(\leftarrow, \rightarrow\)
• \(s \in K\)：初始状态
• \(H \subseteq K\)：停机状态(halting states) 的集合
• \(\delta\)：转移函数，一个从 \((K - H) \times \Sigma\) 到 \(K \times (\Sigma \cup \{\leftarrow, \rightarrow\})\) 的函数，满足：
  • \(\forall\ q \in K - H\)，若 \(\delta(q, \triangleright) = (p, b)\)，那么 \(b = \rightarrow\)
  • \(\forall\ q \in K - H, a \in \Sigma\)，若 \(\delta(q, a) = (p, b)\)，那么 \(b \ne \triangleright\)

定义

图灵机 \(M = (K, \Sigma, \delta, s, H)\) 的配置(configuration) 是 \(K \times \triangleright \Sigma^* \times (\Sigma^* (\Sigma - \{\sqcup\}) \cup \{e\})\) 的一个成员。

定义

令 \(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) \vdash_M (q_2, w_2\underline{a_2}u_2) $$

当且仅当在对于某些 \(b \in \Sigma \cup \{\leftarrow, \rightarrow\}, \delta(q_1, a_1) = \delta(q_2, b)\)，以及以下三种情况之一满足时：

1. \(b \in \Sigma, w_1 = w_2, u_1 = u_2, a_2 = b\)
2. \(b = \leftarrow, w_1 = w_2 a_2\)，且满足以下两种情况之一：
   • 当 \(a_1 \ne \sqcup\) 或 \(u_1 \ne e\) 时，\(u_2 = a_1 u_1\)
   • 当 \(a_1 = \sqcup\) 且 \(u_1 = e\) 时，\(u_2 = e\)
3. \(b = \rightarrow, w_2 = w_1 a_1\)，且满足以下两种情况之一：
   • \(u_1 = a_2 u_2\)
   • \(u_1 = u_2 = e\) 且 \(a_2 = \sqcup\)

成立。

定义

对任意图灵机 \(M\)，令 \(\vdash_M^*\) 为 \(\vdash_M\) 的自反传递闭包。若 \(C_1 \vdash_M^* C_2\)，称配置 \(C_1\) 产生了配置 \(C_2\)。\(M\) 的计算(computation) 是一个配置序列 \(C_0, C_1, \dots, C_n\ (n \ge 0)\)，满足： $$ C_0 \vdash_M C_1 \vdash_M C_2 \vdash_M \dots \vdash_M C_n $$

称上述计算长度为 \(n\) 或需要 \(n\) 步完成，并且可将其简写为 \(C_0 \vdash_M^n C_n\)。

定义

令 \(M = (K, \Sigma, \delta, s, H)\) 为一台图灵机，且 \(H = \{y, n\}\) 包含两个不同的停机状态（分别表示「是」和「否」）。任何包含状态 \(y\) 的停机配置被称为接受配置(accpeting configuration)，而任何包含状态 \(n\) 的停机配置被称为拒绝配置(rejecting configuration)。

对于输入 \(w \in (\Sigma - \{\sqcup, \triangleright\})^*\)，若 \((s, \triangleright \underline{\sqcup} w)\) 产生了接受配置，那么称 \(M\) 接受(accepts) 了 \(w\)；若 \((s, \triangleright \underline{\sqcup} w)\) 产生了拒绝配置，那么称 \(M\) 拒绝(rejects) 了 \(w\)。

令 \(\Sigma_0 = \Sigma - \{\sqcup, \triangleright\}\) 为 \(M\) 的输入字母表(input alphabet)。对于语言 \(L \subseteq \Sigma_0^*\)，若任意字符串 \(w \in \Sigma_0^*\)，以下条件为真：\(w \in L\) 时 \(M\) 接受了 \(w\)，且 \(w \notin L\) 时 \(M\) 拒绝了 \(w\)，那么称 \(M\) 判定(decides) 了 \(L\)。而被图灵机判定的语言被认为是递归的(recursive)。

定义

令 \(M = (K, \Sigma, \delta, s, H)\) 为图灵机，\(\Sigma_0 = \Sigma - \{\sqcup, \triangleright\}\) 为字母表，\(w \in \Sigma_0^*\)。假设 \(M\) 在输入 \(w\) 上停机，且 \((s, \triangleright \underline{\sqcup} w) \vdash_M^* (h, \triangleright \underline{\sqcup} y)\)（\(y \in \Sigma_0^*\)），那么称 \(y\) 为 \(M\) 在输入 \(w\) 上的输出，记作 \(M(w)\)。

令 \(f\) 为从 \(\Sigma_0^*\) 到 \(\Sigma_0^*\) 的函数。当且仅当 \(\forall\ w \in \Sigma_0^*\)，\(M(w) = f(w)\)，称 \(M\) 计算(computes) 了函数 \(f\)。像这种能被图灵机计算出来的函数被认为是递归的(recursive)。

定义

令 \(M = (K, \Sigma, \delta, s, H)\) 为图灵机，满足 \(0, 1, ; \in \Sigma\)，并令 \(f\) 为任意从 \(\mathbb{N}^k\) 到 \(\mathbb{N}\) 的函数（\(k \ge 1\)）。若 \(\forall\ w_1, \dots, w_k \in 0 \cup 1 \cup (0 \cup 1)^*\)（即任意 \(k\) 个表示整数二进制编码的字符串），\(\text{num}(M(w_1; \dots ; w_k)) = f(\text{num}(w_1), \dots, \text{num}(w_k))\)，称 \(M\) 计算了 \(f\)。也就是说，若 \(M\) 起始于整数 \(n_1, \dots, n_k\) 的二进制表示，那么它最终停机时，纸带上包含了一个表示数字 \(f(n_1, \dots, n_k)\)（函数值）的字符串。这样被图灵机计算出来的函数被认为是递归的。

定义

令 \(M = (K, \Sigma, \delta, s, H)\) 为图灵机，\(\Sigma_0 = \Sigma - \{\sqcup, \triangleright\}\) 为字母表，\(L \subseteq \Sigma_0^*\) 为语言。若对于任意字符串 \(w \in \Sigma_0^*\)，以下条件为真：当且仅当 \(M\) 在输入 \(w\) 上停机时，\(w \in L\)，那么称 \(M\) 半判定(semidecides) 了 \(L\)。这种被图灵机半定的语言被认为是递归可枚举的(recursively enumerable)。

定义

令整数 \(k \ge 1\)。\(k\)- 纸带图灵机是一个五元组 \((K, \Sigma, \delta, s, H)\)，其中 \(K, \Sigma, s, H\) 的定义和标准图灵机相同，而转移函数 \(\delta\) 是一个从 \((K - H) \times \Sigma^k\) 到 \(K \times (\Sigma \cup \{\leftarrow, \rightarrow\})^k\) 的函数。也就是说，对于每个状态 \(q\)，每个纸带符号的 \(k\) 元组 \((a_1, \dots, a_k)\)，\(\delta(q, (a_1, \dots, a_k)) = (p, (b_1, \dots, b_k))\)，其中 \(p\) 是新状态，\(b_j\) 是 \(M\) 在纸带 \(j\) 上采取的行动。

自然地，我们再次断言：若 \(a_j = \triangleright\ (j \le k)\)，那么 \(b_j = \rightarrow\)。

定义

令 \(M = (K, \Sigma, \delta, s, H)\) 是 \(k\)- 纸带图灵机。\(M\) 的配置是以下关系的一个成员： $$ K \times (\triangleright \Sigma^* \times (\Sigma^* (\Sigma - {\sqcup}) \cup {e}))^k $$

也就是说，配置能够标识出状态、纸带内容，以及 \(k\) 个纸带上各个头的位置。

定义

随机访问图灵机(random access Turing machine) 是一个二元对 \(M = (k, \Pi)\)，其中 \(k > 0\) 表示寄存器数量，程序 \(\Pi = (\pi_1, \pi_2, \dots, \pi_p)\) 是一个有限的指令序列，其中每条指令 \(\pi_i\) 是来自上面表格中的其中一个类型。假设最后一条指令 \(\pi_p\) 始终是一个 halt 指令（程序的也可以包含其他 halt 指令）。

随机访问图灵机 \((k, \Pi)\) 的一个配置是一个 \(k+2\) 元组 \((\kappa, R_0, R_1, \dots, R_{k-1}, T)\)，其中：

• \(\kappa \in \mathbb{N}\) 是程序计数器，一个介于 \(0\) 到 \(p\) 的整数
• 若 \(\kappa = 0\)，那么该配置是一个停机配置
• \(\forall\ 0 \le j < k\)，\(R_j \in \mathbb{N}\) 是寄存器 \(j\) 的当前值
• 纸带内容 \(T\) 是一个关于正整数对的有限集合，具体来说是 \((\mathbb{N} - \{0\}) \times (\mathbb{N} - \{0\})\) 的一个子集，满足 \(\forall\ i > 1\)，至多存在一个形如 \((i, m) \in T\) 的对
  • \((i, m) \in T\) 表示第 \(i\) 个纸带格子的当前值为整数 \(m > 0\)

令配置 \(C = (\kappa, R_0, R_1, \dots, R_{k-1}, T), C' = (\kappa', R_0', R_1', \dots, R_{k-1}', T')\)，当 \(\kappa', R_j', T'\) 的值能够反映当前指令 \(\pi_k\) 的“语义”在 \(\kappa, R_j, T\) 上的应用时，称 \(C\) 在一步内产生了 \(C'\)，记作 \(C \vdash_M C'\)。\(\vdash_M\) 的自反传递闭包 \(\vdash_M^*\) 是名为「产生(yield)」的关系。

定义

固定字母表 \(\Sigma\)，随机访问图灵机从中获取输入，其中 \(\sqcup \in \Sigma\)，而 \(\triangleright \notin \Sigma\)（因为随机访问图灵机没有离开纸带最左端的问题）。令 \(\mathbf{E}\) 为 \(\Sigma\) 和 \(\{0, 1, \dots, |\Sigma| - 1\}\) 的一个固定双射，它对输入和输出进行了编码；并假设 \(\mathbf{E}(\sqcup) = 0\)。

输入为 \(w = a_1 a_2 \dots a_n \in (\Sigma - \{\sqcup\})^*\) 的随机访问图灵机 \(M = (k, \Pi)\) 为 \((\kappa, R_0, \dots, R_{k-1}, T)\)，其中 \(\kappa = 1, R_j = 0\ (\forall\ j), T = \{(1, \mathbf{E}(a_1)), (2, \mathbf{E}(a_2)), \dots, (n, \mathbf{E}(a_n))\}\)。

当若输入为 \(x \in \Sigma^*\) 的初始配置产生停机配置时，若 \(R_0 = 1\)，称 \(M\) 接受了字符串 \(x\)；若 \(R_0 = 0\)，则称 \(M\) 拒绝了字符串 \(x\)。

令字母表 \(\Sigma_0 \subseteq \Sigma - \{\sqcup\}\)，令语言 \(L \subseteq \Sigma_0^*\)。当 \(x \in L\) 时 \(M\) 接受了 \(x\)，当 \(x \notin L\) 时 \(M\) 拒绝了 \(x\)，称 \(M\) 判定了 \(L\)。

当以下条件为真：当前仅当对于输入 \(x\)，\(M\) 能够产生某些停机状态时，\(x \in L\)，称 \(M\) 半判定了 \(L\)。

令函数 \(f: \Sigma_0^* \mapsto \Sigma_0^*\)。\(\forall\ x \in \Sigma_0^*\)，\(M\) 的起始配置最终在产生停机配置时得到纸带内容 \(\{(1, \mathbf{E}(a_1)), (2, \mathbf{E}(a_2)), \dots, (n, \mathbf{E}(a_n))\}\)，其中 \(f(w) = a_1 \dots a_n\)，称 \(M\) 计算了 \(f\)。

定义

令 \(M = (K, \Sigma, \Delta, s, H)\) 为非确定性图灵机。对于输入 \(w \in (\Sigma - \{\triangleright, \sqcup\})^*\)，若 \((s, \triangleright \underline{\sqcup}w) \vdash_M^* (h, u\underline{a}v)\)，其中 \(h \in H, a \in \Sigma, u, v \in \Sigma^*\)，称 \(M\) 接受了 \(w\)。注意：对于该输入，即便 NTM 可能有多种非停机计算的可能，只要存在一个能停机的计算，就认为 NTM 接受了该输入。

若对于所有输入 \(w \in (\Sigma - \{\triangleright, \sqcup\})^*\)，满足当且仅当 \(M\) 接受 \(w\) 时 \(w \in L\)，称 \(M\) 半判定了语言 \(L \subseteq (\Sigma - \{\triangleright, \sqcup\})^*\)。

定义

令 \(M = (K, \Sigma, \Delta, s, \{y, n\})\) 为 NTM。对于所有输入 \(w \in (\Sigma - \{\triangleright, \sqcup\})^*\)，若满足以下两个条件，称 \(M\) 判定了语言 \(L \subseteq (\Sigma - \{\triangleright, \sqcup\})^*\)：

• 存在一个自然数 \(N\)，依赖于 \(M, w\)，使得不存在满足 \((s, \triangleright \underline{\sqcup}w) \vdash_M^N C\) 的配置 \(C\)
• 当且仅当 \((s, \triangleright \underline{\sqcup}w) \vdash_M^* (h, u\underline{a}v)\)（其中 \(u, v \in \Sigma^*, a \in \Sigma\)）时 \(w \in L\)

最后，对于所有输入 \(w \in (\Sigma - \{\triangleright, \sqcup\})^*\)，若满足以下两个条件，称 \(M\) 计算了函数 \(f: (\Sigma - \{\triangleright, \sqcup\})^* \mapsto (\Sigma - \{\triangleright, \sqcup\})^*\)：

• 存在一个自然数 \(N\)，依赖于 \(M, w\)，使得不存在满足 \((s, \triangleright \underline{\sqcup}w) \vdash_M^N C\) 的配置 \(C\)
• 当且仅当 \(ua = \triangleright \sqcup\) 且 \(v = f(w)\) 时 \((s, \triangleright \underline{\sqcup}w) \vdash_M^* (h, u\underline{a}v)\)

定义

文法（无限制文法 / 重写系统 (rewriting system) 是一个四元组 \(G = (V, \Sigma, R, S)\)，其中：

• \(V\)：字母表
• \(\Sigma \subseteq V\)：终结符(terminal symbols) 集合；\(V - \Sigma\) 就是非终结符(nonterminal symbols) 集合
• \(S \in V - \Sigma\)：起始符号 (start symbol)
• \(R\)：规则集合，是 \((V^*(V - \Sigma)V^*) \times V^*\) 的有限子集

• 若 \((u, v) \in R\)，记作 \(u \rightarrow v\)
• 当且仅当对于 \(w_1, w_2 \in V^*\)，\(u' \rightarrow v' \in R\)，\(u = w_1 u' w_2, v = w_1 v' w_2\) 时，记作 \(u \Rightarrow_G v\)
• \(\Rightarrow_G^*\) 为 \(\Rightarrow_G\) 的自反传递闭包
• 当且仅当 \(S \Rightarrow_G^* w\) 时，称 \(G\) 生成了字符串 \(w \in \Sigma^*\)
• 由 \(G\) 生成的语言 \(L(G)\) 是 \(\Sigma^*\) 中由 \(G\) 生成的所有字符串的集合
• 推导(derivation) 是形如 \(w_0 \Rightarrow_G w_1 \Rightarrow_G \dots \Rightarrow_G w_n\) 的一个序列

定义

令 \(G = (V, \Sigma, R, S)\) 为文法，\(f: \Sigma^* \mapsto \Sigma^*\) 为函数。\(\forall\ w, v \in \Sigma^*\)，以下条件为真时，称 \(G\) 计算了 \(f\)：

也就是说，由输入 \(w\) 组成的字符串，两侧带有 \(G\) 的起始符号，恰好产生一个在 \(\Sigma^*\) 的字符串，其值为 \(f(w)\)。

当且仅当存在一个能计算函数 \(f: \Sigma^* \mapsto \Sigma^*\) 的文法时，称该函数为文法可计算的(grammartically computable)。

定义

先定义一种极其简单的，从 \(\mathbb{N}^k\) 到 \(\mathbb{N}\) 的函数（\(k \ge 0\)）基本函数为：

• \(\forall\ k \ge 0\)，\(k\) 元零函数(\(k\)-ary zero function) 被定义为：\(\text{zero}_k (n_1, \dots, n_k) = 0\)（\(\forall\ n_1, \dots, n_k \in \mathbb{N}\)）
• \(\forall\ k \ge j > 0\)，第 \(j\) 个 \(k\) 元恒等函数(\(j\)th \(k\)-ary identity function) 被定义为：\(\text{id}_{k, j} (n_1, \dots, n_k) = n_j\)（\(\forall\ n_1, \dots, n_k \in \mathbb{N}\)）
• 后继函数(successor function) 被定义为 \(\text{succ}(n) = n + 1\)（\(\forall\ n \in \mathbb{N}\)）

更复杂的函数：

• 令 \(k, l \ge 0, g: \mathbb{N}^k \mapsto \mathbb{N}\) 为 \(k\) 元函数，令 \(h_1, \dots, h_k\) 为 \(l\) 元函数，那么带有 \(h_1, \dots, h_k\) 的组合(composition) 函数 \(g\) 是 \(l\) 元函数，其定义如下：

  \[ f(n_1, \dots, n_{\ell}) = g(h_1(n_1, \dots, n_{\ell}), \dots, h_k(n_1, \dots, n_{\ell})) \]

• 令 \(k \ge 0\)，\(g\) 为 \(k\) 元函数，令 \(h\) 为 \((k + 2)\) 元函数，那么由 \(g, h\) 递归定义的函数 \(f\) 是 \(k + 1\) 元函数，其定义如下（\(\forall\ n_1, \dots, n_k, m \in \mathbb{N}\)）：

  \[ \begin{aligned} f(n_1, \dots, n_k, 0) &= g(n_1, \dots, n_k), \\ f(n_1, \dots, n_k, m + 1) &= h(n_1, \dots, n_k, m, f(n_1, \dots, n_k, m)) \end{aligned} \]

原始递归函数(primitive recursive functions) 就是上面全部的基本函数，以及通过任意次数的组合和递归定义从基本函数获得的所有函数。

定义

令 \(g\) 为 \(k+1\) 元函数（\(k \ge 0\)）。\(g\) 的最小化(minimalization) 是一个 \(k\) 元函数 \(f\)，其定义如下：

将 \(g\) 的最小化记作 \(\mu m[g(n_1, \dots, n_k, m) = 1]\)。

若运行以下方法后总是能终止，那么称函数 \(g\) 是可最小化的(minimalizable)。

m := 0;
while g(n_1, ..., n_k, m) != 1 do m := m + 1;
output m

也就是说，当且仅当 \(\exists\ m \in \mathbb{N}\)，满足 \(g(n_1, \dots, n_k, m) = 1\) 时，\(g\) 是可最小化的。

若一个函数可以通过基本函数的组合、递归定义和可最小化函数的最小化操作获得，则称该函数为 \(\mu\)- 递归的。