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

13

习题1.13

设 $f:\mathbb{N}\rightarrow\mathbb{N}$ 满足 $$ \begin{align} f(0) &= 1, \\ f(1) &= 1, \\ f(x+2) &= f(x)+f(x+1), \end{align} $$ 证明：

(1) $f\in\mathcal{PRF}$;

(2) $f\in\mathcal{EF}$.

证：

（1）

令 $F(n)=\langle f(n),f(n+1) \rangle$，从而 $F(0)=\langle f(0), f(1)\rangle=2\cdot 3=6$。

$$ \begin{align} F(n+1) &= \langle f(n+1), f(n+2) \rangle \\ &= \langle \text{ep}_1(F(n)), \text{ep}_1(F(n))+\text{ep}_0(F(n)) \rangle \\ &= H(F(n)) \end{align} $$ 其中 $H(x)=\langle\text{ep}_1(x),\text{ep}_1(x)+\text{ep}_0(x)\rangle$ 为初等函数。

所以 $F(n)$是原始递归函数，$f(x)=\text{ep}_0(F(x))$为原始递归函数。

（2）

证法一：

提示

参考定理1.31的证明

首先为 $f(n)$找上界。用数学归纳法易证 $f(n)\leq 2^n$. 令 $g(n)=2^n$，易见 $g\in\mathcal{EF}$.

令 $F(n)=\langle f(n),f(n+1) \rangle$，$G(n)=\langle g(n), g(n+1) \rangle$. 显然 $F(n)\leq G(n)$.

令 $H(n)=\langle F(0), F(1),\cdots,F(n)\rangle$, $B(n)=\langle G(0),G(1),\cdots,G(n)\rangle$. 显然 $H(n)\leq B(n)$.

根据 $G\ddot{o}del$ 编码定义有

$$ B(n)=\prod^n_{i=0}[P_i^{G(i)}] $$ 显然 $B(n)\in\mathcal{EF}$.

因为 $\text{ep}_0(H(n))=F(0)$，且 $\forall 0\leq i< y$，有 $$ \begin{align} \text{ep}_{i+1}(H(n))&=F(i+1) \\ &=\langle \text{ep}_1(F(i)), \text{ep}_1(F(i))+\text{ep}_0(F(i)) \rangle\\ &=\langle \text{ep}_1(\text{ep}_i(H(n))), \text{ep}_1(\text{ep}_i(H(n)))+\text{ep}_0(\text{ep}_i(H(n))) \rangle\\ &=A(\text{ep}_i(H(n))) \end{align} $$ 其中 $A(x)=\langle\text{ep}_1(x),\text{ep}_1(x)+\text{ep}_0(x)\rangle$ 为初等函数。

所以

$$H(n)=\mu z\leq B(n).[\text{ep}_0(z)=F(0) \wedge \forall i<n. \text{ep}_{i+1}(z)=A(\text{ep}_i(z))]$$

根据引理1.17-1.19可知，$H(n)\in\mathcal{EF}$.

因为 $f(n)=\text{ep}_0(F(n))=\text{ep}_0(\text{ep}_n(H(n)))$，所以 $f(n)\in\mathcal{EF}$.

证法二：

提示

$\sqrt{x}\not\in\mathcal{EF}$，命题1.24仅证明了 $\lfloor \sqrt[y]{x}\rfloor\in\mathcal{EF}$.

$$\begin{align} f(n) &= \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \\\\ &=\frac{1}{2^{n+1}\sqrt{5}}\left[(1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}\right] \\\\ &=\frac{1}{2^{n+1}\sqrt{5}}\left[\sum_{i=0}^{n+1}C^i_{n+1}(\sqrt{5})^i-\sum_{i=0}^{n+1}C^i_{n+1}(-\sqrt{5})^i\right]\\\\ &=\frac{1}{2^{n+1}\sqrt{5}}\left[\sum_{i=0}^{n+1}C^i_{n+1}2(\sqrt{5})^iN^2(\text{rs}(i,2))\right]\\\\ &=\frac{1}{2^{n}}\left[\sum_{i=0}^{n+1}C^i_{n+1}5^{\lfloor\frac{i-1}{2}\rfloor}N^2(\text{rs}(i,2))\right]\\\\ &=\left\lfloor\frac{\sum_{i=0}^{n+1}C^i_{n+1}5^{\lfloor\frac{i-1}{2}\rfloor}N^2(\text{rs}(i,2))}{2^{n}}\right\rfloor \end{align}$$

其中倒数第二个等号成立是因为求和项不为零时 $i$为奇数，故$\frac{i-1}{2}=\lfloor\frac{i-1}{2}\rfloor$。最后一个等号成立是因为结果一定是整数，故分式可以整除。

14

习题1.14

设数论谓词 $Q(x,y,z,v)$ 定义为 $$ Q(x,y,z,v)\equiv p(\langle x,y,z \rangle) | v, $$ 其中 $p(n)$表示第 $n$ 个素数， $\langle x, y, z \rangle$是 $x,y,z$的 $G\ddot{o}del$编码。证明：$Q(x,y,z,v)$是初等的。

证：

$Q(x,y,z,v)$的特征函数为 $N^2(\text{rs}(v,p(\langle x,y,z \rangle)))$，故是初等的。

15

习题1.15

设 $f:\mathbb{N}\rightarrow\mathbb{N}$ 满足 $$ \begin{align} f(0) &= 1, \\ f(1) &= 4, \\ f(2) &= 6, \\ f(x+3) &= f(x)+(f(x+1))^2+(f(x+2))^3, \end{align} $$ 证明：$f\in\mathcal{PRF}$

证：

令 $F(x)=\langle f(x),f(x+1),f(x+2)\rangle$，故 $f(x)=\text{ep}_0(F(x))$。

$F(0)=\langle 1,4,6\rangle$，且

$$\begin{align} F(x+1) &= \langle f(x+1),f(x+2),f(x+3)\rangle \\\\ &=\langle f(x+1),f(x+2),f(x)+(f(x+1))^2+(f(x+2))^3\rangle \\\\ &=\langle \text{ep}_1(F(x)),\text{ep}_2(F(x)),\text{ep}_0(F(x))+(\text{ep}_1(F(x)))^2+(\text{ep}_2(F(x)))^3\rangle\\\\ &=A(F(x)) \end{align}$$

其中 $A(x)=\langle \text{ep}_1(x),\text{ep}_2(x),\text{ep}_0(x)+(\text{ep}_1(x))^2+(\text{ep}_2(x))^3\rangle\in\mathcal{PRF}$.

故$F(x)\in\mathcal{PRF}$，$f(x)\in\mathcal{PRF}$。

16

习题1.16

设 $f:\mathbb{N}\rightarrow\mathbb{N}$ 满足 $$ \begin{align} f(0) &= 0, \\ f(1) &= 1, \\ f(2) &= 2^2, \\ f(3) &= 3^{3^3}, \\ \cdots & \cdots \\ f(n) &= \underbrace{n^{\cdot^{\cdot^{\cdot^n}}}}_{n个n}, \end{align} $$ 证明：$f\in\mathcal{PRF}-\mathcal{EF}$

证：

首先证明 $f\in\mathcal{PRF}$。

令 $g(m,n)=\underbrace{n^{\cdot^{\cdot^{\cdot^n}}}}_{m个n}$，则

$$\begin{cases} g(0,n)&=N^2n\,,\\\\ g(m+1,n)&=n^{g(m,n)}\,. \end{cases}$$

故 $g(m,n)\in\mathcal{PRF}$，$f(n)=g(n,n)\in\mathcal{PRF}$

下面证明 $f\not\in\mathcal{EF}$.

反设 $f\in\mathcal{EF}$，则存在 $k$，对于任意 $x$，有 $f(x)<\underbrace{2^{2^{\cdot^{\cdot^{\cdot^{2^x}}}}}}_{k个2}$.

令 $x=k+2$，从而 $\underbrace{(k+2)^{\cdot^{\cdot^{\cdot^{(k+2)}}}}}_{k+2个k+2}<\underbrace{2^{2^{\cdot^{\cdot^{\cdot^{2^{k+2}}}}}}}_{k个2}$. 矛盾。

17

习题1.17

设 $g:\mathbb{N}\rightarrow\mathbb{N}\in\mathcal{PRF}$，$f:\mathbb{N}^2\rightarrow\mathbb{N}$， 满足 $$ \begin{align} f(x,0) &= g(x), \\ f(x,y+1) &= f(f(\cdots f(f(x,y),y-1),\cdots ),0), \end{align} $$ 证明：$f\in\mathcal{PRF}$

证：

首先证明 $f(x,y)$ 呈形 $g^{a(y)}(x)$.

当 $y=0$ 时， $f(x,y)=f(x,0)=g(x)$. 即 $a(0)=1$.

假设 $f(x,y)=g^{a(y)}(x)$，

$$\begin{align} f(x,y+1) &= f(f(\cdots f(f(x,y),y-1)\cdots ,1),0)\\\\ &=g^{a(0)}f(\cdots f(f(x,y),y-1)\cdots ,1)\\\\ &=g^{a(0)+a(1)}f(\cdots f(f(x,y),y-1)\cdots ,2)\\\\ &=g^{a(0)+a(1)+\cdots+a(y)}(x) \end{align}$$

故

$$\begin{cases} a(0) &=1\\\\ a(y+1) &=a(0)+\cdots+a(y) \end{cases}$$

易见 $a(y)\in\mathcal{PRF}$, $f(x,y)=g^{a(y)}(x)$.

令 $h(x,y)=g^y(x)$，则 $\begin{cases}h(x,0)&=x\,,\\ h(x,y+1) &=g(h(x,y))\,.\end{cases}$

故 $h\in\mathcal{PRF}$, $f(x,y)=h(x,a(y))\in\mathcal{PRF}$.

18

习题1.18

设 $k\in\mathbb{N}^+$，函数 $f:\mathbb{N}^k\rightarrow\mathbb{N}$ 和 $g:\mathbb{N}^k\rightarrow\mathbb{N}$ 仅在有穷个点取不同值，证明：$f$为递归函数当且仅当 $g$为递归函数。

证：

由 $f,g$ 仅在有穷个点不同，故存在 $k\in\mathbb{N}$，当 $x>k$ 时，$f(x)=g(x)$.

从而 $f(x)=\begin{cases}f(x), &x\leq k\,,\\ g(x), &x>k\,.\end{cases}$

令$f'(x)=\begin{cases}f(x), &x\leq k\,,\\ 0, &x>k\,.\end{cases}$

易见 $f'\in\mathcal{PRF}$. 实际上，$f'(x)=f(0)N(x\ddot-0)+f(1)N(x\ddot-1)+\cdots+f(k)N(x\ddot-k)\in\mathcal{EF}$.

故$f(x)=f'(x)N(x\dot-k)+g(x)N^2(x\dot-k)$.

故$g\in\mathcal{PRF}\Rightarrow f\in\mathcal{PRF}$.

同理$f\in\mathcal{PRF}\Rightarrow g\in\mathcal{PRF}$.

19

习题1.19

证明： $$ f(n)=\left\lfloor \left(\frac{\sqrt{5}+1}{2}\right)n\right\rfloor $$ 为初等函数。

证：

$$\begin{align} f(n) &=\max x\leq 2n. x\leq \left(\frac{\sqrt{5}+1}{2}\right)n\\\\ &=\max x\leq 2n. 2x\ddot-n\leq \sqrt{5}n\\\\ &=\max x\leq 2n. (2x\ddot-n)^2\leq 5n^2\\\\ &=\max x\leq 2n. x^2\dot-(n^2+xn) \end{align}$$

故 $f(n) \in\mathcal{EF}$

习题1.19（修改）

证明： $$ f(n)=\left\lfloor \left(\frac{\sqrt{5}+1}{2}\right)^n\right\rfloor $$ 为初等函数。

证：

使用牛顿二项式展开 $(\sqrt{5}+1)^n$.

$$\begin{align} (\sqrt{5}+1)^n &= \sum_{k=0}^n C_n^k (\sqrt{5})^k \\\\ &= \sum_{k=0}^n C_n^k (\sqrt{5})^k N^2(rs(k, 2)) + \sum_{k=0}^n C_n^k (\sqrt{5})^k N(rs(k, 2)) \\\\ &= \sqrt{5} \sum_{k=0}^n C_n^k 5^{\lfloor \frac{k}{2}\rfloor} N^2(rs(k, 2)) + \sum_{k=0}^n C_n^k 5^{\lfloor \frac{k}{2}\rfloor} N(rs(k, 2)) \\\\ \end{align}$$

令 $g(n) = \sum_{k=0}^n C_n^k 5^{\lfloor \frac{k}{2}\rfloor} N^2(rs(k, 2))$, $h(n) = \sum_{k=0}^n C_n^k 5^{\lfloor \frac{k}{2}\rfloor} N(rs(k, 2))$.

易见 $g(n), h(n) \in\mathcal{EF}$.

故

$$\begin{align} f(n) &= \left\lfloor \frac{\sqrt{5}g(n)+h(n)}{2^n} \right\rfloor \\\\ &=\max x\leq 2^n. x\leq \frac{\sqrt{5}g(n)+h(n)}{2^n} \\\\ &=\max x\leq 2^n. 2^n x \ddot- h(n) \leq \sqrt{5}g(n) \\\\ &=\max x\leq 2^n. (2^n x \ddot- h(n))^2 \dot- 5g^2(n) \end{align}$$

故 $f(n) \in\mathcal{EF}$

20

习题1.20

证明：$\text{Ack}(4,n)=\mathcal{PRF}-\mathcal{EF}$，其中 $\text{Ack}(x,y)$ 是Ackermann函数。

证：

令 $f(n)=\text{Ack}(4,n)$，故

$$f(0)=\text{Ack}(4,0)=\text{Ack}(3,1)=2^{1+3}-3=13$$

$$\begin{align} f(n+1)&=\text{Ack}(4,n+1)\\\\ &=\text{Ack}(3,\text{Ack}(4,n))\\\\ &=\text{Ack}(3,f(n))\\\\ &=2^{f(n)+3}\dot-3 \end{align}$$

令 $g(n)=f(n)+3$，则 $g(0)=16=2^{2^{2}}$，$g(n+1)=2^{g(n)}$，$g(n)=\underbrace{2^{\cdot^{\cdot^{\cdot^2}}}}_{n+3个2}$.

从而 $\text{Ack}(4,n)=\underbrace{2^{\cdot^{\cdot^{\cdot^2}}}}_{n+3个2}\dot-3\in\mathcal{PRF}$.

由于 $\lim_{n\rightarrow \infty}\frac{\underbrace{2^{\cdot^{\cdot^{\cdot^2}}}}_{k个2}}{g(n)}=0$，故$g\not\in\mathcal{EF}$，$f\not\in\mathcal{EF}$.