NKU 第七次作业

注意

尚不完善，请有选择地参考.

Exercise 4.2.48

对于任意给定的实数 $\pi$，令
$$ F(m) = \begin{cases}0, & 如果\pi 的十进制展开中至少有 m 个 7, \\ 1, & 其他 \end{cases} $$
证明 $F$ 是原始递归函数.

由于 $[0,1]$ 和 $\mathbb{R}$ 之间存在双射，因此不妨仅考虑 $\pi\in [0,1]$ 的情形，首先证明如下的函数是原始递归函数：

\[ \begin{aligned} f(n) & := \pi 的十进制展开中的第 n 位 \\ & = [10^n \cdot \pi] \dot{-} [10^{n-1}\cdot \pi] \end{aligned} \]

由于 $\pi$ 已经给定，且 $m^n$ 和 $\dot{-}$ 均为原始递归的，因此 $f(n)$ 也是原始递归函数.

利用函数 $f(n)$ 分情形定义

\[ \mathrm{K}_f(n) = \begin{cases} 1, & f(n) = 7, \\ 0, & f(n)\neq 7. \end{cases} \]

不难验证 $\mathrm{K}_f(n)$ 也是原始递归的，故利用如下的递归方程可证明 $F(m)$ 是原始递归函数：

\[ \begin{aligned} F(0) & = 0 \\ F(m+1) & = [1\dot{-}F(m)] \times \mathrm{K}_f(n) \end{aligned} \]

$\square$

Exercise 4.2.54

令 $G^{(p)}$ 指代函数 $G\circ G \circ\cdots \circ G$ （共 $p$ 次复合），且
$$ F(m) = G^{(H(m))}(m). $$
说明：如果 $G$ 和 $H$ 都是（原始）递归函数，则 $F$ 也是.

由于原始递归函数类 $\mathrm{Prim}$ 和递归函数类 $\mathrm{Rec}$ 对函数复合封闭，因此 $G^{(p)}(m)$ 是（原始）递归函数.

先对原始递归的情形作证明，对于

\[ F(0) = G^{(H(0))} (0) \]

由于 $H(0)$ 是常数，$G^{(p)}(0)$ 也是常数，故 $F(0)$ 也是常数，即为零元函数.

由于 $G^{(p)}(m)$ 和 $H(m)$ 都是原始递归函数，不妨设为

\[ G^{(p)}(m+1) = P[m,G^{(p)}(m)] \]

以及

\[ H(m+1) = Q(m,H(m)) \]

其中 $P(x,y)$ 和 $Q(x,y)$ 均为原始递归函数，从而

\[ \begin{aligned} F(m+1) & = G^{(H(m+1))}(m+1) \\ & = G^{(Q(m,H(m)))}(m+1) \\ & = P[m,G^{(Q(m,H(m)))}(m)] \\ \end{aligned} \]

因此 $F$ 是原始递归函数. 对于递归函数，由于 $\mathrm{Rec}$ 对复合运算封闭，上述的证明依旧成立. $\square$

评论