《计算模型导引》第五章习题¶
15¶
习题5.15
证明定理 5.21 中函数 \(g\) 为一般递归函数。
解：
这里空白的地方太小，写不下。请听习题课讲解。
16¶
习题5.16
证明引理 5.25 中函数 \(e(m,l)\) 为一般递归函数。
解：
这里空白的地方太小，写不下。请听习题课讲解。
17¶
习题5.17
令 \(S=\{\sharp M: M \text{为Turing机}\}\) ，证明 \(S\) 是Turing-可计算的。
解：
这里空白的地方太小，写不下。请听习题课讲解。
18¶
习题5.18
由 CT 证明函数 \(g(n)\) 可计算，这里 $$ g(n)=\text{在自然对数之底e的十进制展开式中第n个数字}. $$
解：
只需证 \(g(n)\) 为直觉可计算。
由 Taylor 公式知
其中 \(0<\theta<1\)
由此可见 \(g(n)\) 直觉可计算。由 CT，\(g(n)\) 可计算。
19¶
习题5.19
（1）什么是停机问题？
（2）什么是可判定问题（decision problem）？
（3）停机问题可判定吗？
解：
（1）
是否存在能行过程来判定机器对所有输入皆停机？
（2）
设 \(A\) 为 \(\mathcal{N}\) 的子集，\(A\) 是可判定的指 \(A\) 的特征函数 \(\chi_A\) 是 Turing-可计算的，即有机器 \(M_A\)，其对于输入 \(\overline{x}\)，若 \(x\in A\)，则输出 \(\overline{0}\)；否则，输出 \(\overline{1}\)。
（3）
停机问题不可判定。
20¶
习题5.20
（1）什么是通用Turing机（universal Turing machine）？
（2）通用Turing机起什么作用？
解：
（1）
通用Turing机 \(U\) 使对任何机器 \(M\) 和任何 \((n_1,\cdots,n_k)\in\mathcal{N}^k\)，
（2）
通用Turing机能模拟任何其他Turing机。通用Turing机在早期程序存储式计算机的研制中起到了重要的促进作用。