这是我们（32 舍 388）参考老师的课堂内容整理的 11 年的答案，附带解析。由于时间仓促，错误必定不少，请各位见谅并吐槽指正。G 版(a) F 不一定。因为假设 A 是{Σ*}，B 是{M 在“M”上不停机}，符合题目要求，B 不是可判定的。(b) T 假如 A 可以归约到 B，根据归约的定义，x∈A 的时候 t(x)∈B，反之，x∉A，即 x∈A的补的时候 t(x)∉B，即 t(x)∈B 的补。(c) F 因为 DFA 总有停机的时候，对于一个 DFA 输入“M”，这个 DFA 总会读完所有的字符然后给出 yes 或者 no，因此这个语言是递归的。老师课堂上说 DDFA是非正则的，这是可以用对角化定理证明 DDFA和每个正则语言都不一样，证明和课本 165 页中间的相似。(d) T 这个非递归可枚举的语言就是课本 164 下面那个 H1 的补，{M 在“M”上不停机}(e) T He 可以用通用图灵机半判定，但是无法判定。停机问题，即图灵机 M 在某个输入 w上是否停机，无法判定，这里让 w=e 即可。(f) F 根据定理 5.4.1，因为 H 不是递归的，所以 L 也不递归了。因为 H≤L 补，所以 H 补≤L。假如 L 是递归可枚举的，那么 H 补也是递归可枚举，那么 H 就不是递归可枚举的了，这和 H 本身是递归可枚举的事实是相悖的，因此 L 不是递归可枚举的。(g) T 假设 M1 半判定 A，M2 半判定 B，M3 半判定 A∪B 的补。对于输入 w，交给M1、M2 和 M3 一起做。假如 M1 接受，那么 w∈A，M2 接受，那么 w∈B，假如 M3 接受，那么 w∉(A∪B)，即不是 A 也不是 B。因为 A 和 B 是不相交的，因此 M1、M2 和 M3 的合体可以判定 A 或者 B，因此 A 和 B 都是可判定的，递归的。(h) T 后面的是 NTIME，应该是不确定性计算的所需时间。所以，我们把 nk看作一体的，称为 a，那么确定计算时间是指数 ca，非确定计算只要 a，也就是 nk了。(i) T B 是 P，A 可以多项式时间归约到 B，所以 A 也是 P，P 对补封闭，所以命题正确。(j) F 假设 A 是这样一个问题，给定一个整数集合和整数 k，求是否存在 k 个元素和大于C。直观看我们可以用随机抽取 k 个元素然后算和然后假如其中一次大于 C 就接受。但是我们也可以通过，例如多项式时间的冒泡排序，把集合的整数降序排序，归约到问题 B，前 k 个元素的和是否大于 C，显然 B 是 P 的。所以，只能说假如 B 是 NP 的，A 可以归约到B，那么 ...
