Exercise 1
证明：
已知一个集合是 R-decidable 的，当且仅当它和它的补集都是 R-enumerable 的。
令永真式集合为 $Val = \{\varphi \in L_0^{S_\infty} \mid \models \varphi\}$。根据引理，我们知道 $Val$ 是R-enumerable的；而根据定理 1.9，$Val$ 不是R-decidable的）。
假设可满足的公式集合 $Sat = \{\varphi \in L_0^{S_\infty} \mid \text{satisfiable}\}$ 是 R-enumerable 的。
我们知道，一个公式 $\varphi$ 不可满足，等价于它的否定 $\neg\varphi$ 是一个永真式（即 $\neg\varphi \in Val$）。如果 $Sat$ 是可枚举的，那我们完全可以写一个程序：把 $Sat$ 里的公式全枚举出来，然后对它们挨个取否定。这个过程恰好就能枚举出所有“不可满足的公式”，也就是 $Val$ 的补集 $\{\varphi \mid \not\models \varphi\}$。
这说明 $Val$ 的补集也是 R-enumerable 的。既然 $Val$ 和它的补集都是可枚举的，那么 $Val$ 必定是 R-decidable 的。但这与定理 1.9 直接矛盾。
所以假设不成立，原集合不是 R-enumerable 的。
Exercise 2
证明：
已知 $W_A \le_m W_B$，说明存在一个可计算的归约函数 $f$，使得对于任意 $x$，都有 $x \in W_A \iff f(x) \in W_B$。
(i) 反证法。假设 $W_B$ 是 R-decidable 的，即存在一个判定程序 $\mathbb{P}_B$。
对于任意输入 $x$，我们构造一个新程序：先计算出 $f(x)$，然后把 $f(x)$ 喂给 $\mathbb{P}_B$。因为 $x \in W_A \iff f(x) \in W_B$，所以 $\mathbb{P}_B$ 的输出结果就能直接用来判定 $x$ 是否属于 $W_A$。这就意味着 $W_A$ 也是 R-decidable 的，与已知条件矛盾。故 $W_B$ 不是 R-decidable 的。
(ii) 反证法。假设 $W_B$ 是 R-enumerable 的，即存在一个枚举程序 $\mathbb{P}_B$ 会不断输出 $W_B$ 中的元素。
我们构造一个针对 $W_A$ 的枚举程序：按字典序生成所有的字符串 $x$，计算它们的 $f(x)$，然后把这些 $f(x)$ 放到 $\mathbb{P}_B$ 里去跑。一旦 $\mathbb{P}_B$ 输出了某个 $f(x)$，我们的程序就把对应的 $x$ 打印出来。这样就能把 $W_A$ 里的元素全枚举出来，说明 $W_A$ 是 R-enumerable 的，与已知条件矛盾。故 $W_B$ 不是 R-enumerable 的。
Exercise 3
先证 $\Pi_{halt} \le_m TOTAL$
给定任意程序 $\mathbb{P}$，我们构造一个新程序 $\mathbb{P}'$。$\mathbb{P}'$ 的逻辑很简单：对任何输入 $x$，它都直接忽略 $x$，然后内部模拟运行“$\mathbb{P}$ 在空串 $\Box$ 上的表现”。
- 如果 $\mathbb{P}$ 在 $\Box$ 上停机（即 $\mathbb{P} \in \Pi_{halt}$），那么 $\mathbb{P}'$ 无论收到什么输入都会停机，即 $\mathbb{P}' \in TOTAL$。
- 如果 $\mathbb{P}$ 在 $\Box$ 上不停机（即 $\mathbb{P} \notin \Pi_{halt}$），那么 $\mathbb{P}'$ 对任何输入都会陷入死循环，即 $\mathbb{P}' \notin TOTAL$。
由此可得 $\Pi_{halt} \le_m TOTAL$。
我们来证 $\overline{\Pi_{halt}} \le_m TOTAL$。
给定程序 $\mathbb{P}$，构造新程序 $\mathbb{P}''$。对于输入 $x$，$\mathbb{P}''$ 模拟 $\mathbb{P}$ 在 $\Box$ 上运行 $|x|$（即字符串长度）步。如果 $\mathbb{P}$ 在这 $|x|$ 步内停机了，$\mathbb{P}''$ 就主动进入死循环；如果没停机，$\mathbb{P}''$ 就正常停机。
- 若 $\mathbb{P} \in \overline{\Pi_{halt}}$（在 $\Box$ 上永远不停机），那对于任何输入 $x$，$\mathbb{P}''$ 模拟时都等不到它停机，所以 $\mathbb{P}''$ 会正常停机。此时 $\mathbb{P}'' \in TOTAL$。
- 若 $\mathbb{P} \notin \overline{\Pi_{halt}}$（在 $\Box$ 上某 $k$ 步时停机了），那么对于所有长度 $|x| \ge k$ 的输入，$\mathbb{P}''$ 都会发现它停机了并主动陷入死循环。此时 $\mathbb{P}'' \notin TOTAL$。
既然非 R-enumerable 的集合 $\overline{\Pi_{halt}}$ 可以多对一归约到 TOTAL，根据本题 Exercise 2(ii) 的结论，TOTAL 必然不是 R-enumerable 的。
Exercise 4
证明：
(P1) 证明 $\mathfrak{A}_\mathbb{P} \models \psi_\mathbb{P}$：
$\psi_\mathbb{P}$ 的结构为 $\psi_0 \wedge R\bar{0}\dots\bar{0} \wedge \psi_{\alpha_0} \wedge \dots \wedge \psi_{\alpha_{k-1}}$。我们需要证明在结构 $\mathfrak{A}_\mathbb{P}$ 中这些合取项都成立。
- 对于 $\psi_0$：$\mathfrak{A}_\mathbb{P}$ 的论域设定为 $\mathbb{N}$，< 是标准的自然数大小关系，$f$ 定义为加1后继操作，$c=0$。这完美满足了 $\psi_0$ 中关于序、最小元和后继的公理。
- 对于 $R\bar{0}\dots\bar{0}$：关系 $R^{\mathfrak{A}_\mathbb{P}}$ 的定义是“所有可达配置的集合”。因为初始配置 $(0,0,\dots,0)$ 显然是不走任何步数就能到达的，所以它在这个集合里，该项成立。
- 对于 $\psi_{\alpha_i}$：这些公式描述了指令执行前后的配置转移（如果前一个配置在 $R$ 里，执行指令后的配置也得在 $R$ 里）。因为 $R^{\mathfrak{A}_\mathbb{P}}$ 已经包含了所有可达的配置，这种状态转移的闭包性质自然是满足的。
综上所述，所有合取项均为真，故 $\mathfrak{A}_\mathbb{P} \models \psi_\mathbb{P}$。
(P2) 若 $\mathfrak{A} \models \psi_\mathbb{P}$ 且 $(L, m_0, \dots, m_n)$ 是一组可达格局，证明 $\mathfrak{A} \models R\bar{L}\bar{m}_0\dots\bar{m}_n$：
对到达该格局所需要的步数 $s$ 进行数学归纳法。
- Base Case ($s=0$)： 走 0 步可达的只有初始格局 $(0,0,\dots,0)$。因为 $\mathfrak{A} \models \psi_\mathbb{P}$，它自然满足里面的合取项 $\mathfrak{A} \models R\bar{0}\bar{0}\dots\bar{0}$，结论成立。
- Inductive Step： 假设对于走了 $s$ 步达到的格局 $(L, m_0, \dots, m_n)$，有 $\mathfrak{A} \models R\bar{L}\bar{m}_0\dots\bar{m}_n$ 成立。
现考虑第 $s+1$ 步，它是通过执行指令 $\alpha_L$ 得到的。因为 $\mathfrak{A} \models \psi_\mathbb{P}$，所以 $\mathfrak{A} \models \psi_{\alpha_L}$。
不妨以加法指令 LET R_i = R_i + | 为例，$\psi_{\alpha_L}$ 规定了 $R\bar{L}y_0\dots y_n \to R\overline{L+1}y_0\dots fy_i \dots$。将当前的变量值 $y_j = \bar{m}_j$ 代入，由归纳假设可知蕴含式的前件为真。再结合 $f(\bar{m}_i) = \overline{m_i+1}$，通过肯定前件，我们必然能得出后件 $\mathfrak{A} \models R\overline{L+1}\bar{m}_0\dots\overline{m_i+1}\dots$ 为真。
对于减法或分支指令，推理过程完全同理。由数学归纳法可知，定理得证。