《计算模型导引》第五章习题

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 公式知

$$e=\frac{1}{0!}+\frac{1}{1!}+\cdots + \frac{1}{n!} + \frac{e^\theta}{(n+1)!}$$

其中 $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$，

$$M|\overline{(n_1,\cdots,n_k)} \twoheadrightarrow \overline{y} \Leftrightarrow U|\overline{(\sharp M, n_1,\cdots,n_k)} \twoheadrightarrow \overline{y}$$

（2）

通用Turing机能模拟任何其他Turing机。通用Turing机在早期程序存储式计算机的研制中起到了重要的促进作用。