4 Turing Machine

4.1 The Definition of Turing Machine

虽然 PDA 比 FA 强大，但它仍然有局限性；而图灵机通过“可读写”的带子克服了这些限制。

定义：一个图灵机是一个五元组 \((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\)

Graph Representation

注意图灵机是确定性的

Definition: A configuration of a TM \(M=(K,Σ,δ,s,H)\) is a member of

\[ K × ▹Σ^∗×(Σ^∗(Σ−\{⊔\})∪{e}) \]

• \(x\)：从左端标记 \(▹\) 到读写头当前位置之间的符号串（含读写头所在位置）
• \(y\)：从读写头右侧第一个非空白符号开始到最右非空白符号之间的内容
• 若右边全为空白，则 \(y=e\)（空串）

A simplified notation of configuration

Example

还是和之前一样用 \(\vdash_M\) 代表一次推导，\(\vdash_M^*\) 和 \(\vdash_M^n\) 的含义也是类似的

---

为之后叙述图灵机简单一些，引入基本图灵机的概念

\[ M_a = ({s, h}, Σ, δ, s, {h}) \]

其中对于任意 \(b\in\Sigma-\{▹\}\)，\(\delta(s,b) = (h,a)\)，同时, \(𝛿(𝑠, ⊳) = (𝑠, →)\)。只要碰到不是 \(▷\) 的符号（比如 \(a\)、\(b\)、空白等），就把那个格子改成 \(a\)，然后停下。

缩写

\(𝑎\) instead of \(𝑀_𝑎\), \(𝐿\) instead of \(𝑀_←\), and \(𝑅\) instead of \(𝑀_→\).

利用基本图灵机组装一个大的图灵机

Example

设 \(M_i = (K_i, \Sigma, \delta_i, s_i, H_i)\)，其中 \(i = 1,2,3\)，均为图灵机（TMs）。组合后的机器为 \(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\)

4.2 Computing with Turing Machine

图灵机通过进入两个特殊的“停机状态”来表示对输入的判断结果——“是”或“否”。

对于一个输入来说，若图灵机进入接受状态则接受输入；若图灵机进入拒绝状态则拒绝输入。

我们称一个图灵机可以决定某个语言，当且仅当对每一个输入 \(w\)，\(M\) 都能在有限步内做出判断：

• 若 \(w∈L\) → 接受
• 若 \(w\notin L\) → 拒绝

如果存在一台图灵机能决定某个语言，则该语言是递归的（即可判定的）。

递归在之前的印象中的含义是一个函数调用自身，那这里为什么称这样的语言是递归的呢？实际上这里递归就是图灵机可停机，只有这样才能调用下去；如果不能停机，也就不能递归调用下去了

Example

对于一个图灵机 \(M = (K,\Sigma,\delta,s,H)\)，然后字母表 \(\Sigma_0 \subseteq \Sigma-\{\sqcup, \triangleright\}\) 然后语言 \(L \subseteq \Sigma_0^*\) 。称 \(M\) 半决定（Semidecides) \(L\) 如果对于任意的 \(w\in \Sigma^*\) 来说，下面的论断是对的

\[ w\in L \Leftrightarrow M 在输入为 w时可以停机 \]

此时也称 \(L\) 是 recursively enumerable 的

为什么称这个为递归可枚举的呢？这里取名为 “可枚举”，我认为的含义是可以枚举出接受的语言。具体可以如下操作

1. 列出所有可能的输入字符串（按长度排序）：ε,a,b,aa,ab,ba,bb,aaa,…（假设字母表有限）
2. 同时模拟 M 在这些字符串上的运行，但不要一个一个等（否则如果第一个不停机，后面永远轮不到）；
3. 而是采用“轮流走一步”的方式： - 第1步：跑 M(ε) 1步 - 第2步：跑 M(ε) 第2步，再跑 M(a) 第1步 - 第3步：跑 M(ε) 第3步，M(a) 第2步，M(b) 第1步
4. 一旦某个模拟停机了，就把对应的输入打印出来！

所有属于 L 的字符串最终都会被打印出来（因为 M 对它们会停机），不属于的永远不会被打印。

If 𝐿 is a recursive language, then it is R.E.

这样就可以让错误的一直不停机

总结一下 Regular Language, CFL， R.E. language 的关系

Recursive Language 的补是 Recursive 的（交换接受和拒绝这两种停机状态即可）并和交也是 Recursive 的

设 \(M=(K,\Sigma,\delta,s,H)\) 是一台图灵机。令 \(\Sigma_0\subseteq\Sigma-\{\triangleright,\sqcup\}\) 为一个字母表，且 \(w\in\Sigma_0^*\)。

• 假设 \(M\) 在输入\(w\)上停机，且 \((s,\triangleright\underline{\sqcup} w)\Rightarrow_M^*(h,\triangleright\underline{\sqcup} y)\) 对某个\(y\in\Sigma_0^*\) 成立。则称 \(y\) 是 \(M\) 在输入\(w\)上的输出，记作 \(M(w)\)。

• 设 \(f\) 是一个函数 \(f:\Sigma_0^*\to\Sigma_0^*\)。若对所有 \(w\in\Sigma_0^*\)，都有 \(M(w)=f(w)\)，则称图灵机 \(M\) 计算函数 \(f\)。

• 若存在一台图灵机 \(M\) 能计算函数 \(f\)，则称函数 \(f\) 是递归的（recursive）。

用人话讲一下就是原先磁带上的是输入，然后经过一番操作之后指针回到原点，然后磁带上的就是输出，这就是一个函数

4.3 Extension of Turing Machine

图灵机可以做一些扩展，但是我们发现这些看似扩展，实则并没有提升图灵机的能力

• 多条磁带
• 双向无限的磁带
• 多个读写头
• 多维磁带
• 不确定性图灵机

这些扩展可以更好地帮我们构建图灵机，下面我们将阐述一下为什么这些扩展并没有提升图灵机的能力

---

下面阐述多条磁带的图灵机

定义：设 \(k \geq 1\) 为一个整数。一个 \(k\) 带图灵机 \((K,\Sigma,\delta,s,H)\)，其中 \(K,\Sigma,s\) 和 \(H\) 与普通图灵机定义中的相同，而 \(\delta\) 是转移函数：

\[ \delta:(K-H)\times\Sigma^k\to K\times(\Sigma\cup\{\leftarrow,\rightarrow\})^k \]

定义：设 \(M=(K,\Sigma,\delta,s,H)\) 是一个 \(k\) 带图灵机。\(M\) 的一个configuration如下：

\[ K\times\left(\triangleright \Sigma^*\times\left(\Sigma^*(\Sigma-\sqcup)\right)\cup\{e\}\right)^k \]

同时我们规定：

• 输入字符串放在第一条带上
• 其他磁带初始为空白，读写头位于最左侧空白格
• 计算结束时，输出在第一条带上，其他磁带忽略

Example

定理：设 \(M=(K,\Sigma,\delta,s,H)\) 是一个 \(k\)-带图灵机（\(k \geq 1\)）。则存在一个标准图灵机 \(M'=(K',\Sigma',\delta',s',H)\)，其中 \(\Sigma \subseteq \Sigma'\)，使得以下结论成立：

• 对任意输入字符串 \(x \in \Sigma^*\)，\(M\) 在输入 \(x\) 上停机，并在第一条带上输出 \(y\)，当且仅当 \(M'\) 在输入 \(x\) 上停机于相同的停机状态，且在其磁带上输出相同的 \(y\)。
• 如果 \(M\) 在输入为 \(x\) 后 \(t\) 步停机了，那么 \(M'\) 会在 \(O(t(|x|+t))\) 步后会停机

证明思路是：构造一个标准图灵机 \(M’\)，模拟 \(k\)-带图灵机 \(M\) 的行为。

Phase 1 将 \(k\) 带图灵机的初始配置编码到单带图灵机的一条磁带上：每个磁带格子存储一个 \(2k\) 元组，前 \(k\) 项表示各带在该位置的符号，后 \(k\) 项用 0/1 标记各读写头是否位于此处。

这里的理解是前 2k 个位置代表原来每条磁带的第一个位置

Phase 2 就是模拟 \(M\) 的计算过程。首先从左到右（或从当前头位置）扫描，收集所有 \(k\) 个虚拟头当前读取的符号，形成 \(k\)-元组；然后根据 \(M\) 的转移函数确定新状态、要写入的符号和各头的移动方向，并更新 \(M’\) 的内部状态；接着再次扫描磁带，将新符号写入对应位置，并通过在头标志位（0/1）上修改来反映各虚拟头的新位置。虽然 \(M'\) 只有一个物理读写头，但通过多次遍历和标记，能准确模拟多个头的“同时”移动与操作。

最后停机的时候

• 解码：将磁带上每个复合元组（如 \((a,⊔,0,0)\)）替换为其第一条带的符号（如 \(a\)），还原输出内容；
• 定位：根据头标志位找到第一个头的位置，将自身读写头移至对应列；
• 同步：进入与 M 相同的接受或拒绝状态，确保行为等价。

对于时间复杂度 \(O(t(|x| + t))\) 来说，由两个阶段决定：

• Phase 1: \(O(|x|)\)
• Phase 2: 对于 M 的每一步，M' 需要 \(O(|x|+2+t)\)

---

对于由两边无限延长的磁带的图灵机来说，很容易将其转换为双磁带的图灵机

对于单磁带多头的图灵机，可以用多带图灵机对其进行模拟，除去原先的单磁带，其他几条磁带用于模拟每个头的状态。

对于多维图灵机也可以用多带图灵机对其模拟，记录坐标即可。

4.4 Nondeterministic Turing Machines

定义：一台非确定型图灵机（NTM）是一个五元组 \(M = (K,\Sigma,\Delta,s,H)\)，其中 \(K\)、\(\Sigma\) 和 \(H\) 与标准图灵机相同，而 \(\Delta\) 是以下集合的一个子集：

\[ ((K - H) \times \Sigma) \times (K \times (\Sigma \cup \{ \leftarrow, \rightarrow \})) \]

与图灵机类似，但 \(\Delta\) 现在是一个关系而非函数。

Configuration以及关系 \(\vdash_M\) 和 \(\vdash_M^*\) 的定义与标准图灵机类似。

• \(\vdash_M\) 不必是单值的：一个 Configuration 在一步中可能产生多个其他格局

半判定：

• 给定 NTM \(M\) 其输入符号集为\(\Sigma_0\)
• \(M\) semidecides \(L\subseteq\Sigma_0^*\) if for any \(w\in\Sigma_0^*\) ,\(w\in L\) iff \((s,\triangleright\sqcup w)\vdash_M^*(h,\cdots)\)for some \(h\in H\)
• 如果 \(w\in L\) 则NTM有分支可以停机，否则没有分支可以停机

判定：令\(M=(K,\Sigma,\Delta,s,\{y,n\})\)，输入符号集 \(\Sigma_0\)，\(M\) decides a language \(L\subseteq\Sigma_0^*\) if

• for any \(w\in\Sigma_0^*\) ,exists an a tural number \(N\),s.t.no configuration \(c\) satisfying \((s,\triangleright\sqcup w)\vdash_M^N c\) 说明在\(N\)步内都可以停机，非确定产生的树高度小于\(N\)
• \(w\in L\) iff \((s,\triangleright\sqcup w)\vdash_M^*(y,\cdots)\) 非确定执行的树上有一条分支可以停机到 \(y\) 状态

半判定就是有一个可停机，判定就是所有可能情况都可停机（注意停机状态只有 Y/N）但是有情况停机状态是 Y

构造 NTM 判定所有合数（非质数）的二进制编码构成的语言

利用NTM可以“猜测”的特性，目标是猜测有没有两个数相乘等于输入。

假设输入字符串为 \(w\)，则先猜测两个数，得到 \(\triangleright\sqcup p\sqcup q\)，然后将\(p\)和\(q\)相乘，如果等于 \(w\) 则停机到 \(y\)，否则停机到 \(n\)，满足第二个条件。

因为 \(p,q\) 都小于 \(w\)，所以猜测是有限的，而且都可以有限步停机，满足第一个条件。

如果一个非确定性图灵机（NTM）\(M\) 能够半判定、判定某种语言或计算某个函数，那么一定存在一个标准的确定性图灵机（Standard TM）\(M’\)，它也能半判定、判定相同的语言或计算相同的函数。这表明非确定性图灵机与标准图灵机在计算能力上是等价的。

若NTM \(M\) 半判定某个语言 \(L\)，则可构造一个标准TM \(M'\)来模拟 \(M\) 的所有可能计算路径，从而系统性地探索 \(M\) 的非确定性分支。\(M’\) 采用三带结构：

• 第一带存储原始输入
• 第二带模拟 \(M\) 的工作带
• 第三带记录指导 \(M’\) 执行特定计算路径的指令序列

在这里 \(C^{1→2}\) 负责将第一带的内容复制到第二带并清空第二带；\(B^3\) 生成第三带上字典序的下一个指令序列；\(M_d^{2,3}\) 是 \(M\) 的确定性版本，在第二和第三带上运行。

可以穷举所有可能性

由于每个状态-符号组合最多有 \(r\) 个转移，\(k\) 步计算可由长度为 \(k\)、每个元素小于 \(r\) 的数字序列唯一确定，因此所有可能的计算路径构成一个有限的配置空间。\(M'\) 通过系统地尝试所有一阶、二阶、三阶……计算路径，确保不会遗漏任何可能导致接受的路径。最终，\(M'\) 要么发现 \(M\) 的某条停机接受路径而停止，要么无限搜索而不停机，其行为与 \(M\) 的半判定能力一致。由于每一步的下一配置数量有限（不超过 \(|K|·(|Σ|+2))\)，对于任意 \(k\)，\(k\) 步计算的数量是有限的，因此 \(M'\) 的构造是可行的，从而完成了从 NTM 到标准 TM 的等价转换。

4.5 Grammars

一个文法 \(G\) 定义为四元组 \(G = (V, Σ, R, S)\)

• \(V\) 是字母表
• \(Σ ⊆ V\) 是终结符集合
• \(V − Σ\) 是非终结符集合
• \(S ∈ V − Σ\) 是起始符号
• \(R\) 是规则集合，即从包含至少一个非终结符的字符串到任意字符串的有限映射。

\(G\) 生成的语言定义为：

\[ L(G)=\{w\in\Sigma^*:S\Rightarrow_G^*w\} \]

从 \(w_0\) 到 \(w_n\) 在 \(G\) 中的一个推导形式为：

\[ w_0\Rightarrow_Gw_1\Rightarrow_G\cdots\Rightarrow_Gw_n \]

• 其中 \(n\) 为推导的长度（即推导步数）。

Example

\(G\) 用于生成语言 \(\{a^n b^n c^n : n \geq 1\}\) ，起始规则 \(S \to ABCS\) 和 \(S \to T_c\) 允许生成任意多个 \(ABC\) 块，即 \(S \Rightarrow (ABC)^n T_c\) （对任意 \(n \geq 0\) ）。通过规则 \(BA \to AB\) 、 \(CA \to AC\) 、 \(CB \to BC\) 可以修复非终结符的顺序，确保 \(A\) 、 \(B\) 、 \(C\) 按照正确顺序排列。接着，规则 \(C T_c \to T_c c\) 和 \(C T_c \to T_b c\) 允许 \(c\)-变换器向左移动并生成 \(c\) ，同时可转化为 \(b\)-变换器。进一步， \(B T_b \to T_b b\) 、 \(B T_b \to T_a b\) 、 \(A T_a \to T_a a\) 和 \(T_a \to \varepsilon\) 实现了从右到左依次生成 \(b\) 和 \(a\) ，最终完成字符串 \(a^n b^n c^n\) 的构造。该过程体现了通过非终结符的移动与转换来实现复杂语言结构生成的思想。

现在我们要说明的是 Grammar 和图灵机的等价性

定理：一个语言能被文法生成，当且仅当它是递归可枚举的。即： \(L\) 是文法生成的语言 \(\iff\) \(L\) 是递归可枚举的。

---

\((\Rightarrow)\) 文法 \(\Rightarrow\) 递归可枚举的证明：

设 \(L=L(G)\)，思路是构造一台非确定性图灵机 \(M\)，使得 \(L(M)=L(G)\)。

\(M\) 有两带：

• 第一带永久保存输入 \(w\)；

• 第二带用于尝试重构从起始符号 \(S\) 到 \(w\) 的推导过程。

\(M\) 非确定性地模拟文法 \(G\) 的推导：

• 从第二带上的 \(S\) 开始，每一步非确定性地选择一条规则进行替换；

• 每次替换后检查当前字符串是否等于 \(w\)；

• 若相等则接受，否则继续尝试；

• 若无法推导出 \(w\)，则可能无限循环。

共有 \(|R|+1\) 种状态选择：

• 前 \(|R|\) 个状态对应应用某条规则；

• 第 \(|R|+1\) 个状态用于比较当前串是否等于 \(w\)，若相等则接受，否则继续。

因此，\(M\) 能半判定 \(L(G)\)，故 \(L\) 是递归可枚举的。

---

\((\Leftarrow)\) 递归可枚举 \(\Rightarrow\) 文法

设 \(M\) 是半判定 \(L\) 的图灵机，构造文法 \(G\) 使得 \(L(G)=L(M)\)。

约定：

• \(M\) 从配置 \((s,\triangleright\underline{w})\) 开始；
• 状态集 \(K\) 与字母表 \(\Sigma\) 不相交，且均不含新边界符 \(\triangleleft\)；
• \(M\) 停机时处于 \((h,\triangleright\underline{})\)。

核心思想：\(G\) 通过逆向模拟 \(M\) 的计算过程来生成语言。

• 中间字符串编码为配置形式：
  • 配置 \((q,\triangleright u\underline{a}w)\) 对应字符串 \(\triangleright uaqw\triangleleft\)
• 构造文法规则，使推导路径对应于 \(M\) 的反向计算步骤。

给定图灵机 \(M\) 要找文法 \(G\) 生成 \(L(M)\)。图灵机半判定的过程中，相应的变化：

\[ \triangleright\sqcup sw\vdash\triangleright\sqcup u_1a_1q_1v_1\vdash\cdots\vdash\triangleright\sqcup h \]

所以我们期望文法 \(G\) 的表现是可以给出如下的替换链：

\[ S\Rightarrow\triangleright\sqcup h\triangleleft\Rightarrow\cdots\Rightarrow\triangleright\sqcup u_1a_1q_1v_1\triangleleft\Rightarrow\triangleright\sqcup sw\triangleleft\Rightarrow w \]

即从停机状态往前推，一直找到初始状态得到字符串 \(w\)，并且在中间给每个状态加上一个三角标记结尾。

文法构造：设 \(G=(V,\Sigma-\{\sqcup,\triangleright\},R,S)\)，其中：

\(V=\Sigma\cup K\cup\{S,\triangleleft\}\)

规则 \(R\) 包含以下类型：

• 若 \((q,a)\to(p,b)\)，则添加规则 \(bp\to aq\)

• 若 \((q,a)\to(p,\rightarrow)\)，则对每个 \(b\in\Sigma\)，添加 \(abp\to aqb\)

• 若 \((q,a)\to(p,\leftarrow)\)，且 \(a\ne\sqcup\)，则添加 \(pab\to aqb\)；若 \(a=\sqcup\)，则添加 \(p\sqcup b\to\sqcup qb\) 和 \(p\triangleleft\leftarrow\sqcup q\triangleleft\)

• 若 \((h,\sqcup)\) 是终止配置，则添加 \(S\to\triangleright\sqcup h\triangleleft\)

• 若 \(s\) 是起始状态，则添加 \(\triangleright\sqcup s\to e\)，\(\triangleleft\to e\)

---

定义：函数 \(f:\Sigma^*\to\Sigma^*\) 是文法可计算的 (grammatically computable)，若存在文法 \(G\) 使得 \(SwS\Rightarrow_G^*v\) 当且仅当 \(v=f(w)\)。

4.6 Numerical Functions

原始递归函数（Primitive Recursive Functions）这是一种从简单函数出发，通过特定操作构建更复杂函数的方法。

所有原始递归函数都从以下三种基本函数开始：

• 零函数（Zero Function）: \(\text{zero}_k(n_1, ..., n_k) = 0\)
• 后继函数（Successor Function）: \(\text{succ}(n) = n + 1\)
• 投影函数（Projection Function）: \(id_{k,j}(n_1, ..., n_k) = n_j\) （返回第 j 个参数）

通过以下两种操作，可以从已有的原始递归函数构造出新的函数：

• 复合（Composition）: 若 \(g\) 是 \(k\) 元函数，\(h_1, ..., h_k\) 是 \(l\) 元函数，则新函数 \(f\) 定义为： \(f(n_1, ..., n_l) = g(h_1(n_1, ..., n_l), ..., h_k(n_1, ..., n_l))\)
• 原始递归（Primitive Recursion）: 给定一个 \(k\) 元函数 \(g\) 和一个 \((k+2)\) 元函数 \(h\)，可以定义一个新的 (\(k+1\)) 元函数 \(f\)：

• \(f(n_1, ..., n_k, 0) = g(n_1, ..., n_k)\)

• \(f(n_1, ..., n_k, m+1) = h(n_1, ..., n_k, m, f(n_1, ..., n_k, m))\)

利用上述规则，可以证明许多常见函数是原始递归的：

• 算术运算: 加法 (plus)、乘法 (mult)、幂 (exp)
• 其他函数: 常数函数、符号函数 (sgn)、截断减法 (m ~ n = max{m-n, 0})
• 谓词（取值 0 或 1 的函数）: 如 iszero(n)（判断是否为零）、greater_than_or_equal(m, n)（判断大小关系）、prime(x)（判断素数）等。
• 有界量词: 如果 p 是原始递归谓词，那么 \(∃t_{≤ m} p(n_1, ..., n_k, t)\) 和 \(∀t_{≤ m} p(n_1, ..., n_k, t)\) 也是原始递归的。

原始递归函数是由局限性的

• 原始递归函数集是可枚举的：因为每个函数都可以用有限的符号串（由基本函数和操作符组成）来表示。
• 存在可计算但非原始递归的函数：通过对角线法可以构造一个函数 \(g(n) = f_n(n) + 1\)（其中 \(f_n\) 是第 n 个原始递归函数），这个 \(g\) 显然是可计算的，但不在原始递归函数列表中。这说明原始递归函数是递归函数的真子集。

---

为了克服原始递归函数的局限性，引入了极小化（Minimalization） 操作。进而引出 \(μ\)-递归函数（\(μ\)-Recursive Functions）

给定一个 (k+1) 元函数 \(g\)，其极小化是一个 k 元函数 \(f\)，定义为：\(f(n_1, ..., n_k)\) = 最小的 m 使得 \(g(n_1, ..., n_k, m) = 1\)（如果存在这样的 \(m\)；否则未定义或设为 0）。

• 符号表示为：\(f = μm [g(n_1, ..., n_k, m) = 1]\)

μ-递归函数是指可以通过基本函数，经由复合、原始递归和（在可极小化函数上的）极小化操作得到的所有函数。

可极小化函数（Minimizable Function）

指对于任意输入 \((n_1, ..., n_k)\)，总存在某个 \(m\) 使得 \(g(n_1, ..., n_k, m) = 1\)。在这种情况下，极小化操作是良定义且总会终止的。

为什么我们要引出 \(\mu\)- 递归函数的概念呢？下面这个定理揭示了其与图灵机的关系

定理：一个函数 \(f: ℕ^k → ℕ\) 是 μ-递归的，当且仅当它是 递归的（recursive），即可以被某台图灵机计算。

(\(⇒\)) \(μ\)-递归 ⇒ 图灵机可计算：因为基本函数（零、后继、投影）很容易用图灵机实现，而复合、原始递归、极小化这三种操作也都可以被图灵机模拟。因此，任何 μ-递归函数都可以被图灵机计算。

(\(⇐\)) 图灵机可计算 ⇒ \(μ\)-递归：

• 首先对状态集 \(K\) 和字母表 \(\Sigma\) 进行编码：设 \(K\cap\Sigma=\emptyset\)，令 \(b=|\Sigma|+|K|\)，并定义一个映射 \(E:\Sigma\cup K\to\{0,1,\ldots,b-1\}\)
• 这样，任意配置\((q,a_1a_2\dots \underline{a_k}\dots a_n)\)可以表示为一个以\(b\)为基数的整数，其形式为\(a_1a_2\dots a_kq\dots a_n\)，对应的数值为

\[ E(a_1)b^n+\cdots+E(a_k)b^{n-k+1}+E(q)b^{n-k}+E(a_{k+1})b^{n-k-1}+\cdots+E(a_n) \]

假设图灵机\(M=(K,\Sigma,\delta,s,\{h\})\)计算函数\(f:\mathbb{N}\to\mathbb{N}\)。我们旨在证明 \(f\) 是 \(μ\)-递归的。为此，我们将\(f(n)\)定义为一个由多个辅助函数组合而成的 \(μ\)-递归函数：

\[ f(n)=\text{num}(\text{output}(\text{last}(\text{comp}(n)))) \]

其中：

• \(\text{comp}(n)\) 表示一个整数，其在 \(b\) 进制下的表示是机器从初始配置 \(\triangleright\sqcup sw\)（\(w\) 为 \(n\) 的二进制编码）开始，经过一系列合法状态转移后，最终停机于\(\triangleright\sqcup hw'\)（\(w'\) 为 \(f(n)\) 的二进制编码）的完整计算历史（即所有中间配置的拼接）；
• \(\text{last}\) 从该整数中提取出最后一个配置；
• \(\text{output}\) 去掉该配置中的前三个符号 \(\triangleright\sqcup h\)，保留其余部分（即输出字符串）；
• \(\text{num}\) 将这个由0和1组成的二进制串转换为对应的自然数。

然后只需要说明上述的函数是 \(\mu\) 递归的即可

Review

1. There exists some Turing machines with one halting state that doesn’t semidecide a language.

Answer

回忆一下半判定的含义。称一台图灵机半判定一个语言，若属于该语言的字符串在这个图灵机上可以停机。那么既然这个图灵机可以停机，那么也就存在相应的语言被其半判定。

Answer

\(L = \{uvcww^R|u,v,w\in\{a,b\}^*,|u| = 2|v|\}\)

如果遇到要写图灵机的转移图的话，遇到 \(ww^R\) 这种可以参考上图右上角的那个部分

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！