**Exercise 1**

• $(\Rightarrow)$ 假设 $W$ 是可判定的。 这意味着存在一个算法，对于任意输入的字符串 $w$，都能在有限步内确切输出 $w \in W$ 还是 $w \notin W$。由于字符集 $A$ 是有限的，我们可以写一个程序，严格按照题目给定的字典序（先按长度，长度相同则按字母序）从小到大生成 $A^*$ 中的所有字符串：$s_1, s_2, s_3, \dots$。

对于每一个生成的 $s_i$，我们将其输入给 $W$ 的判定算法。如果算法返回“是”（即 $s_i \in W$），我们就将 $s_i$ 输出。因为我们是严格按字典序测试的，输出的序列必然也是严格按字典序排列的。这就构成了一个按字典序枚举 $W$ 的过程。

• $(\Leftarrow)$ 假设 $W$ 可以按字典序枚举。

如果 $W$ 是有限集，任何有限集都是可判定的。如果 $W$ 是无限集，意味着存在一个枚举程序，能输出一个严格按字典序递增的序列 $w_1 <_\alpha w_2 <_\alpha w_3 <_\alpha \dots$。

给定任意一个待判定的字符串 $x \in A^*$，我们启动这个枚举程序。由于序列的长度或字母序在不断严格增加，必然在有限的某一步，程序会枚举到一个字符串 $w_k$，满足 $w_k = x$ 或者 $w_k >_\alpha x$。

1. 如果 $w_k = x$，则说明 $x \in W$，判定程序输出“接受”并停机。

2. 如果 $w_k >_\alpha x$，因为后续枚举的所有字符串在字典序上都会比 $w_k$ 更大，因此 $x$ 永远不可能再出现。判定程序输出“拒绝”并停机。

无论哪种情况都在有限步内给出了确切结果，因此 $W$ 是可判定的。

**Exercise 2**

• $(\Rightarrow)$ (i) 推出 (ii)：

假设 $W$ 是 R-可枚举的。如果 $W = \emptyset$，构造一个对任何输入都进入死循环的程序即可。如果 $W \neq \emptyset$，根据定义，存在一个可计算函数能列出 $W$ 中的所有元素 $s_1, s_2, s_3, \dots$。

我们构造程序 $\mathbb{P}$：给定输入 $w$，$\mathbb{P}$ 开始逐个生成 $W$ 的枚举序列 $s_1, s_2, \dots$。每生成一个 $s_i$，$\mathbb{P}$ 就检查是否 $s_i = w$。如果相等，$\mathbb{P}$ 立刻跳出循环，输出 $\Box$ 并停机。如果不等，则继续枚举下一个。

如果 $w \in W$，$w$ 必然在枚举序列的第 $k$ 项出现，$\mathbb{P}$ 会在第 $k$ 步停机输出 $\Box$。如果 $w \notin W$，$w$ 永远不会出现，$\mathbb{P}$ 会无限循环 ($\infty$)。

• $(\Leftarrow)$ (ii) 推出 (i)：

假设存在满足题目条件的程序 $\mathbb{P}$。

我们将 $A^*$ 中的所有字符串按某种顺序排列：$x_1, x_2, x_3, \dots$。

枚举器的逻辑如下，分为若干个阶段（第 1 阶段，第 2 阶段，...）：

在第 $k$ 阶段，枚举器同时（或分时交替）对前 $k$ 个字符串 $x_1, x_2, \dots, x_k$ 运行程序 $\mathbb{P}$，每个字符串只运行 $k$ 步。

如果在第 $k$ 阶段的这 $k$ 步中，发现某个 $x_i$ 的运行刚好停机并输出了 $\Box$，并且 $x_i$ 之前没有被输出过，我们就将 $x_i$ 输出。

因为对于任何 $w \in W$，$\mathbb{P}(w)$ 都会在有限的步数 $N$ 内停机。那么在阶段 $\max(N, \text{index}(w))$ 时，这个 $w$ 一定会被我们的枚举器找到并输出。因此，该过程成功枚举了 $W$ 中的所有元素，(i) 成立。

**Exercise 3**

使用反证法。假设 $TOTAL$ 是 R-可判定的。这意味着存在一个能判定其他程序的程序 $H$：当输入程序 $P$ 属于 $TOTAL$ 时，$H(P) = 1$（接受）；当 $P \notin TOTAL$ 时，$H(P) = 0$（拒绝）。且 $H$ 对任意输入都在有限步内停机。

由于 $A=\{|\}$，程序的代码和输入可以编码为由 $|$ 组成的一元字符串。我们可以将所有合法的程序按长度编号为 $P_0, P_1, P_2, \dots$。

现在，我们利用 $H$ 构造一个新的程序 $D$，其工作逻辑如下（输入为 $x \in A^*$）：

1. 令 $n = |x|$（输入的长度）。

2. 调用假设存在的 $H$ 来测试第 $n$ 个程序 $P_n$。

3. 如果 $H(P_n) = 1$（即 $P_n \in TOTAL$），程序 $D$ 计算 $P_n(x)$ 的结果，然后输出 $P_n(x) + |$ （在原结果后多加一个字符）并停机。

4. 如果 $H(P_n) = 0$（即 $P_n \notin TOTAL$），程序 $D$ 直接输出 $\Box$ 并停机。

分析 $D$ 的性质：由于 $H$ 总是能给出确切的 $1$ 或 $0$ 且总是停机，而当 $H$ 返回 $1$ 时 $P_n$ 又是必定停机的全函数，因此 $D$ 对于任何输入 $x$ 都会在有限步内停机。这说明 $D$ 属于 $TOTAL$。

既然 $D$ 是一个合法的程序，它必定在我们之前的程序列表中拥有一个编号，假设为 $k$。即 $D = P_k$。

现在我们将长度为 $k$ 的字符串 $w_k = |^k$ 输入给 $D$。

因为 $D \in TOTAL$，由 $H$ 的定义，$H(P_k)$ 必然等于 $1$。

根据 $D$ 的内部逻辑规则（第3步），既然 $H(P_k) = 1$，那么 $D(w_k)$ 的执行结果必须是 $P_k(w_k) + |$。

但因为 $D$ 本身就是 $P_k$，这就导出了悖论：

产生这个悖论的唯一原因是我们假设了“$TOTAL$ 是可判定的（即存在这样的判定器 $H$）”。因此，假设不成立，$TOTAL$ 不是 R-可判定的。

**Exercise 4**

• $(\Rightarrow)$ 假设 $W$ 是 T-可判定的。

这意味着存在一台图灵机 $M=(Q,\Gamma,\delta,q_0,q_{accept},q_{reject})$ 可以判定 $W$。我们可以使用 R-程序（例如由寄存器和 while 循环组成的程序）来模拟图灵机 $M$：

1. 纸带模拟： 图灵机有向两端无限延伸的纸带。我们可以在 R-程序中使用两个整数变量 $L$ 和 $R$ 来分别表示读写头左侧和右侧的纸带内容。通过将 $\Gamma=\{0,1,\Box\}$ 编码为三进制数，$L$ 和 $R$ 的数值可以完全还原纸带状态。

2. 状态与控制流： 使用一个整型变量 $S$ 保存当前状态 $q \in Q$。模拟的主体是一个大的 while (S != q_{accept} && S != q_{reject}) 循环。在循环内部，使用一系列条件分支（模拟转移函数 $\delta$）。根据 $S$ 和纸带当前格（从变量 $R$ 中取余获得）的值，更新 $S$、写入新字符（通过数学乘加运算修改 $R$ 的末位），以及移动读写头（通过 $L$ 和 $R$ 之间的整数乘除以 $3$ 实现值的转移，模拟左移 $L$ 或右移 $R$）。

3. 由于 $M$ 是一个能在有限步内停机的判定机，该 while 循环必然会结束。结束时，如果 $S == q_{accept}$，R-程序返回接受（1）；如果 $S == q_{reject}$，R-程序返回拒绝（0）。因此，$W$ 是 R-可判定的。

• $(\Leftarrow)$ 假设 $W$ 是 R-可判定的。

这意味着存在一个基于寄存器的通用程序 $\mathbb{P}$ 可以判定 $W$。我们可以构造一台多带图灵机 $M$（多带图灵机与标准单带图灵机是计算等价的）来模拟 $\mathbb{P}$：

1. 数据存储： 程序的每一个变量（寄存器）可以在图灵机的纸带上分配一个连续的区域，区域之间用特殊符号（如 #）隔开。寄存器内的数值使用二进制存储在对应区域。

2. 指令模拟： R-程序的基本操作包括加一、减一和零检测分支。这些都可以通过图灵机的有限状态控制来实现：

- 加法/减法指令可以通过将读写头移动到对应寄存器区域，执行二进制加/减法的状态机转换，并根据进位/借位移动后续区域的内容来实现。

- 控制转移（If/While）可以通过扫描寄存器区域是否全为 0 来决定图灵机下一步的状态跳转。

3. 因为 $\mathbb{P}$ 是一个判定程序，对所有输入都能停机。我们的模拟图灵机 $M$ 也必定会在有限步后完成模拟。当 $\mathbb{P}$ 停机并输出接受时，$M$ 进入 $q_{accept}$；输出拒绝时，$M$ 进入 $q_{reject}$。因此，$W$ 是 T-可判定的。