《计算模型导引》（2019）课后习题答案（一）：递归函数

个人答案，仅供参考。

查看全部

页面含有超多数学公式，打开后需要等待很长时间才能彻底完成渲染和排版，尤其是移动设备。

$$\def \IF {\mathcal{IF}} \def \BF {\mathcal{BF}} \def \EF {\mathcal{EF}} \def \PRF {\mathcal{PRF}} \def \GRF {\mathcal{GRF}} \def \RF {\mathcal{RF}} \def \inBF {\in\BF} \def \notBF {\notin\BF} \def \inEF {\in\EF} \def \notEF {\notin\EF} \def \inPRF {\in\PRF} \def \notPRF {\notin\PRF} \def \inGRF {\in\GRF} \def \notGRF {\notin\GRF} \def \inRF {\in\RF} \def \notRF {\notin\RF} \def \B {\mathbb{B}} \def \N {\mathbb{N}} \def \vx {\vec x} \def \vy {\vec y} \def \nx {\|\vx\|} \def \vb {\vec b} \def \dotminus {∸} \def \ddotminus {\ddot{-}} \newcommand \bmin [3] [x] {\min #1 \le #2 . #3} \newcommand \bmax [3] [x] {\max #1 \le #2 . #3} \newcommand \bminnfy [1] {\bmin n {f(#1, \vy)}} \newcommand \bmaxnfy [1] {\bmax n {f(#1, \vy)}} \newcommand \angles [1] {\langle #1 \rangle}$$

1.1 证明：对于固定的$k$，一元数论函数$x+k\inBF$

证明：简记$f_k=x+k$，以下采用数学归纳法进行证明

• 当$k=0$时，$f_0=x+0=x=P_1^1\inBF$

• 若已知$f_k=x+k\inBF$，可得

  $$f_{k+1}=x+(k+1)=(x+k)+1=S(x+k)=Comp_1^1[S,f_k]\inBF$$

因此，$\forall k \in \mathbb{N}, f_k=x+k\inBF$，证毕。

引理1 （供习题1.2, 1.3, 1.4使用）

若$f(\vx) \inBF$，考虑$f$为$m\in\N^+$元函数，即$f:\N^m\to\N$，

对任意给定的$\vb = (b_1,b_2,\cdots,b_m) \in\B^m$，其中$\B$表示数集$\{0,1\}$，

$\exists c\in\B$，使得$\forall \vx \in \N^m$下式成立：

$$f(\vx + \vb) - f(\vx) = f(x_1+b_1,x_2+b_2,\cdots,x_m+b_m)-f(x_1,x_2,\cdots,x_m)=c$$

证明：$f\inBF$，因此对其构造长度$l$采用数学归纳法证明上述结论

• $l=0 \Rightarrow f\in\IF = \{Z,S,P_i^n\}$，显然

  • $f=Z$时，$c=0$
  • $f=S$时，$c=b_1$（一元函数，$\vb=(b_1)$）
  • $f=P_i^n$时，$c=b_i$

• 假设$l\le n$时已知$f$使得上述结论成立，那么对于构造长度$l=n+1$的构造过程$f_0,f_1,\cdots,f_{n+1}$

  • $f_{n+1} \in \IF$，已证明结论成立。

  • $f_{n+1} = Comp_k^m[f_{l_0}, f_{l_1}, \cdots, f_{l_k}] = f_{l_0}(f_{l_1}(\vx), f_{l_2}(\vx), \cdots, f_{l_k}(\vx))$

    其中$f_{l_i}$的构造长度均不超过$n$，因此

    $$\begin{split} f_{n+1}(\vx+\vb) &= f_{l_0}(f_{l_1}(\vx+\vb) , f_{l_2}(\vx+\vb) , \cdots, f_{l_k}(\vx+\vb)) \\ &= f_{l_0}(f_{l_1}(\vx) + c_1 , f_{l_2}(\vx) + c_2, \cdots, f_{l_k}(\vx) + c_k) \\ &= f_{l_0}(f_{l_1}(\vx), f_{l_2}(\vx), \cdots, f_{l_k}(\vx)) + c \\ &= f_{n+1}(\vx) + c \end{split}$$

    上式中，$c_i\in\B$由$f_{l_i}$与$\vb$决定，与$\vx$无关；$c\in\B$由$f_{l_0}$与$(c_1,c_2,\cdots,c_k)$决定，与$\vx$无关。因此，$f=f_{n+1}$在构造长度为$n+1$时依然使结论成立。

综上所述，引理1成立。

1.2 证明：对任意$k\in\N^+$，$f:\N^k\to\N$，若$f\inBF$，则存在$h$，使得

$$f(\vx)<\nx+h$$

其中$\nx\equiv\max\{x_i:1\le i\le k\}$

证明：简记$\B=\{0,1\}, \vec 0 = (0,0,\cdots ,0)$

由于$\nx$是$\vx$中最大的元素值，显然，$\vx$存在以下拆解形式（不一定唯一）：

$$\vx=\vb_1+\vb_2+\cdots+\vb_{\nx} \quad (\vb_i\in\B^k,1\le i \le \nx)$$

将之带入$f(\vx)$中并利用引理1，

$$\begin{split} f(\vx) &= f(\vb_1+\vb_2+\cdots+\vb_{\nx}) \\ &= f(\vb_1+(\vb_2+\cdots+\vb_{\nx})) \\ &= c_1 + f(\vb_2+\cdots+\vb_{\nx}) \\ &= c_1 + c_2 + f(\vb_3+\cdots+\vb_{\nx}) \\ &= \cdots \\ &= c_1 + c_2 + \cdots + c_{\nx} + f(\vec 0) \\ &= \sum_{i=1}^{\nx}{c_i} + f(\vec 0) \end{split}$$

注意到，虽然这里$b_i$与$\vx$有关导致$c_i$间接地与$\vx$有关，但是在引理1中$\vb$的取值是任意的，所以这并不妨碍我们使用引理1，依然有$c_i\in\B$

$$c_i\in\B \Rightarrow \sum_{i=1}^{\nx}{c_i}\le \nx \\ \therefore f(\vx) \le \nx + f(\vec 0) \lt \nx + (f(\vec 0) + 1)$$

因此，只需要取$h=f(\vec 0)+1$即有$f(\vx)<\nx+h$，证毕

1.3 证明：二元数论函数$x+y\notBF$

证明： 简记$\B=\{0,1\}, \vx=(x,y),f(\vx)=x+y$

反证法，假设$f(\vx)\inBF$

取$\vb=(1,1)$，

$$c=f(\vx+\vb)-f(\vx)=(x+y+1+1)-(x+y)=2\notin\B$$

与引理1矛盾，所以$x+y\notBF$

1.4 证明：二元数论函数$x \dotminus y\notBF$

证明： 简记$\B=\{0,1\}, \vx=(x,y),f(\vx)=x-y$

反证法，假设$f(\vx)\inBF$

取$\vb=(0,1),\vx=(2,0)$，

$$c=f(\vx+\vb)-f(\vx)=(2\dotminus 1)-(2\dotminus 0)=1-2\notin\B$$

与引理1矛盾，所以$x \dotminus y\notBF$

1.5 设$pg(x,y)=2^x(2y+1)\dotminus 1$，证明：存在初等函数$K(x)$和$L(x)$使得

$$K(pg(x,y))=x,\\ L(pg(x,y))=y,\\ pg(K(z),L(z))=z.$$

证明： $\forall x,y \in\N, 2^x(2y+1)\ge 1$，因此$2^x(2y+1)=pg(x,y)+1$

又因为$2y+1$为奇数，所以取$K(z)=ep(0,z+1) \inEF$即可有$K(pg(x,y))=ep(0,2^x(2y+1))=x$

进一步地，取 $L(z)= \Big\lfloor (\lfloor \frac {z+1} {exp(2, ep(0,z+1)))}\rfloor \dotminus 1)/ 2 \Big\rfloor \inEF$，可得$L(pg(x,y))=y$

又由于$z+1$总能整除$2^{ep(0,z+1)}$，且所得的商一定是奇数，因此，

$L(z)$中的取整符号可以去掉，$\dotminus$也可以改写为$-$号，写作$L(z)= (\frac {z+1} {exp(2, ep(0,z+1))}- 1)/ 2$

$\therefore pg(K(z),L(z))=2^{ep(0,z+1)}(2((\frac {z+1} {exp(2, ep(0,z+1))} - 1)/ 2)+1)\dotminus 1=z+1\dotminus 1=z$，证毕。

1.6 设$f:\N\to\N$，证明$f$可以作为配对函数的左函数当且仅当对任何$i\in\N$,

$$|\{x\in\N:f(x)=i\}|=\aleph_0$$

证明：（习惯起见，用$z$做左函数自变量）

$\{z\in\N:f(z)=i\}\subseteq\N\Longrightarrow|\{z\in\N:f(z)=i\}|\le\aleph_0$，因此只需证明其中只能取等号，不能取小于号。

反证法，假设$\exists i\in\N,|\{z\in\N:f(z)=i\}|\lt\aleph_0$，并记$\mathcal Z = \{z\in\N:f(z)=i\}$。

考虑与之对应的任意配对函数$pg:\N^2\to\N$，以及右函数$g:\N\to\N$，并记$\mathcal Y=\{g(z)\mid z\in\mathcal Z\}$

由于$\mid\mathcal Z\mid \lt \aleph_0$，即其中元素的数量是有限的，故$\mathcal Y$中的元素也是有限的，因此集合$\N - \mathcal Y$非空，

任取$j\in\N-\mathcal Y$，

• 如果$pg(i,j)\in\mathcal Z$，则有$j=g(pg(i,j))\in\mathcal Y$，与$j\in\N-\mathcal Y$矛盾
• 如果$pg(i,j)\not\in\mathcal Z$，则有$f(pg(i,j))\neq i$，与配对函数的定义矛盾

两种情况都有矛盾，因此，假设中的命题为假，进而原命题得证

1.7 证明：从本原函数出发，经复合和算子$\prod\limits_{i=n}^m[\cdot]$可以生成所有的初等函数，这里

$$\prod_{i=n}^m[f(i)]=\begin{cases}f(n)\cdot f(n+1) \cdot\,\cdots\,\cdot f(m),&\text{若}m\ge n,\\ 1,&\text{若}m\lt n. \end{cases}$$

证明：记由上述方式得出的函数集合为$\mathcal F$，显然只需证明$\mathcal F$对绝对值减法$\ddotminus$，有界迭加算子$\sum[\cdot]$和有界迭乘算子$\prod[\cdot]$封闭。

1. 显然有界迭乘算子$\prod[\cdot]$是算子$\prod\limits_{i=n}^m[\cdot]$当$n=0$的特殊情况，不需多言

2. • 指数函数$pow(x,y)=\begin{cases}x^y,&y\neq 0\\1,&y=0\end{cases}=\prod\limits_{i=1}^y x$，所以$pow \in \mathcal F$

   • 取反函数$N(x)=\begin{cases}0,&x\neq 0\\1,&x=0\end{cases}=\prod\limits_{i=1}^x {Z}$，所以$N\in\mathcal F$

   • 相等比较$eq(x,y)=\begin{cases}0,&x=y\\1,&x\neq y\end{cases}={(\prod\limits_{i=x}^y {Z})}^{N(\prod\limits_{i=y}^x {Z})}$，所以$eq\in\mathcal F$，

   • 定义对数函数$log(x,y)=\begin{cases}i,&i\in N,x^i=y\\1,&\forall i\in\N,x^i\neq y\end{cases}$其中$x\ge2$，

     由于$x\ge 2$，$x^i=y$最多只可能有一个自然数解，上述定义是良好的。

     $log(x,y)=\prod\limits_{i=0}^y{i^{N(eq(y,pow(x,i)))}}\in\mathcal F$

   • 定义算子$\sum\limits_{i=n}^m[f(i)]=\begin{cases}f(n)+ f(n+1) +\,\cdots\,+ f(m),&\text{若}m\ge n,\\0,&\text{若}m\lt n.\end{cases}$

     利用指数、对数函数，且不妨取底数为2，$\sum\limits_{i=n}^m{[f(i)]}=log(2,\prod\limits_{i=n}^m{pow(2,f(i))})$

     故，$\mathcal F$对于$\sum\limits_{i=n}^m[\cdot]$算子封闭

   • 有界迭加算子$\sum[\cdot]$是$\sum\limits_{i=n}^m[\cdot]$的特例，显然$\mathcal F$对其封闭

3. • $\mathcal F$对乘法封闭，因为$x\times y=\prod\limits_{i=1}^x y$
   • $\mathcal F$对加法封闭，因为$x+y=log(2,pow(2,x)\times pow(2,y))$
   • $x\ddotminus y=(\sum\limits_{i=x+1}^y 1)+(\sum\limits_{i=y+1}^x 1)$，$\mathcal F$对绝对值减法封闭

原命题得证。

1.8 设

$$M(x) = \begin{cases} M(M(x+11)), &\text{若}x\le100,\\ x-10, &\text{若}x>100. \end{cases}$$

证明

$$M(x) = \begin{cases} 91, &\text{若}x\le100,\\ x-10, &\text{否则}. \end{cases}$$

证明：

$$\forall x \in [90, 100], M(x)=M(M(x+11))=M(x+11-10)=M(x+1)\\ \Rightarrow \forall x \in [90, 100], M(x)=M(101)=91$$

进一步地，

$$\forall x \in [79, 89], x+11 \in [90,100], M(x)=M(M(x+11))=M(91)=91 \\ \forall x \in [68, 78], x+11 \in [79,89], M(x)=M(M(x+11))=M(91)=91 \\ \cdots$$

$\therefore \forall x \in [0, 100], M(x) = 91$

1.9 证明：

$$\bminnfy x = n \dotminus \bmaxnfy {n\dotminus x} \\ \bmaxnfy x = n \dotminus \bminnfy {n\dotminus x}$$

证明：

• 首先考虑$f(x ,\vy)$于$[0, n]$上无零点的情况，根据定义显然上式皆成立

• 若有零点，令$r = \bminnfy x, R=\bmaxnfy x$

  即$\forall x \in [0, r) \cup (R, n], f(x,\vy) \neq 0$

  $$\therefore \forall x \in [0, n\dotminus R) \cup (n\dotminus r, n], f(n \dotminus x, \vy) \neq 0$$

  另外又有$f(r,\vy)=0, f(R, \vy) = 0$

  $$\therefore f(n\dotminus (n\dotminus r), \vy) = 0, f(n\dotminus (n\dotminus R), \vy) = 0$$

  故而可知

  $$\bmaxnfy {n\dotminus x} = n\dotminus r \quad\Longrightarrow \bminnfy x = n \dotminus \bmaxnfy {n\dotminus x} \\ \bminnfy {n\dotminus x} = n\dotminus R \quad\Longrightarrow \bmaxnfy x = n \dotminus \bminnfy {n\dotminus x}$$

1.10 证明：$\EF$对有界max-算子封闭。

证明：考虑任意的$f(x,\vy)\inEF,y\in\N^k, k\in \N$

• 先考虑有零点情况

  $$\sum_{i=0}^n {N(f(i, \vy))} = f(x,\vy)\text{在}[0,n]\text{上对}x\text{的零点数} \\ N^2[\sum_{i=0}^n {N(f(i, \vy))} \dotminus \sum_{i=0}^m {N(f(i, \vy))}] = \begin{cases} 1, &[0，m]\text{上的零点少于在}[0,n]\text{上的零点}, \\ 0, &[0,n]\text{上最大零点也位于}[0,m]\text{中}. \end{cases}\\ \therefore \bmaxnfy x = \sum_{m=0}^n{[N^2[\sum_{i=0}^n {N(f(i, \vy))} \dotminus \sum_{i=0}^m {N(f(i, \vy))}]]}$$

• 再考虑无零点情况

  $\bmaxnfy x = 0$恰好也满足有零点情况下的表达

总之，$\bmaxnfy x = \sum_{m=0}^n{[N^2[\sum_{i=0}^n {N(f(i, \vy))} \dotminus \sum_{i=0}^m {N(f(i, \vy))}]]} \inEF$

1.11 Euler函数$\varphi: \N\to\N$定义为

$$\varphi(n)=|\{x:0\lt x\le n \quad\wedge\quad \gcd(x,n)=1\}|$$

即$\varphi(n)$表示小于等于$n$且与$n$互素 等正整数个数。例如$\varphi(1)=1$，因为1与其本身互素；$\varphi(9)=6$，因为9与1,2,4,5,7,8互素。证明：$\varphi\inEF$。

证明：显然，$rs(x,y)=x-y\times\lfloor \frac x y\rfloor \inEF$

$$\text{当}0 \lt i \le x \le n,N(rs(x,i))\times N(rs(n,i)) = \begin{cases} 1, &i\text{是}x\text{和}n\text{的公因数}, \\ 0, &\text{否则}. \end{cases}\\ \Rightarrow \text{当}0\le x \le n, N[\sum_{i=0}^{x}{[N(rs(x,i))\times N(rs(n,i))]} \dotminus 2] = \begin{cases} 1, &\gcd(x.n)=1\vee x=0,\\ 0, &\text{否则}. \end{cases}\\ \Rightarrow \varphi(n)=\sum_{x=0}^n{[N[\sum_{i=0}^{x}{[N(rs(x,i))\times N(rs(n,i))]} \dotminus 2]]} \dotminus 1$$

1.12 设$h(x)$为$x$的最大素因子的下标，约定$h(0)=0, h(1)=1$。例如$h(88)=4$，因为$88=2^3\times 11$的最大素因子11是第4个素数$p_4$，其下标为4。证明：$h\inEF$。

证明：已知$ep(n,x)\inEF$

令$H(n,x)=\bmax [i] n N(ep(n,x))$，即为$x$不大于$P(n)$的最大素因子的下标，有$H\inEF$

显然$h(x)=H(h(x),x)$

$h(x)\le x \quad\Longrightarrow\quad h(x)=H(x,x)\inEF$

1.13 设$f:\N\to\N$满足

$$f(0)=1\\ f(1)=1\\ f(x+2)=f(x)+f(x+1)$$

证明：

(1) $f\inPRF$

(2) $f\inEF$

证明：

(1) 首先任取$\{pg,K,L\}$为$\EF$中（当然也是$\PRF$中）的一配对函数组，

定义$F(x)=pg(f(x),f(x+1))$，可得，

$$F(0)=pg(f(0),f(1))=pg(1,1)\in\N \\ \begin{split} F(x+1)&=pg(f(x+1),f(x+2))\\ &=pg(f(x+1),f(x)+f(x+1))\\ &=pg(L(F(x)), K(F(x)) + L(F(x))) \end{split}\\ \text{记}h(x)=pg(L(x), K(x) + L(x)) \inEF,\\ \text{则}F(x+1)=P_2^2[x, h(F(x))]\\ \therefore F(x) \inPRF \quad\Longrightarrow\quad f(x)=K(F(x))\inPRF$$

(2) 继续(1)中的证明

先证明$f(x)\le2^x$，利用数学归纳法即可，

$$f(0)=1\le2^0\\ f(1)=1\le2^1\\ f(x+2)=f(x)+f(x+1)\le2^x+2^{x+1}\lt 2^{x+1}+2^{x+1}=2^{x+2}\\ \therefore f(x)\le2^x$$

然后由于(1)中的配对函数组是任意的，不妨取一具体的配对函数组$\{\angles {x,y},ep_0, ep_1\}$

$$F(x)=\angles {f(x),f(x+1)}=2^{f(x)}+3^{f(x+1)}=2^{2^x}+3^{4^x} \le2\times81^x$$

易证$2\times81^x\inEF$，即原始递归函数$F(x)$被初等函数$32^x$控制，由定理 1.31，$F(x)\inEF$

因此$f(x)=ep_0(F(x))\inEF$得证

1.14 设数论谓词$Q(x,y,z,v)$定义为

$$Q(x,y,z,v)\equiv p(\angles{x,y,z}) \mid v,$$

其中$p(n)$表示第$n$个素数，$\angles {x,y,z}$是$x,y,z$的Gödel编码，证明：$Q(x,y,z,v)$是初等的。

证明： $p,<\cdot,\cdot,\cdot>,rs,N^2$都是初等的

$Q(x,y,z,v)=N^2(rs(\angles{x,y,z},v))$，故而$Q\inEF$

1.15 设$f:\N\to\N$满足

$$\begin{split} f(0)&=1,\\ f(1)&=4,\\ f(2)&=6,\\ f(x+3)&=f(x) + (f(x+1))^2 + (f(x+2))^3, \end{split}$$

证明：$f\inPRF$

证明：$\PRF$中存在三元配对函数组$\{[\cdot,\cdot,\cdot],(\cdot)_0,(\cdot)_1,(\cdot)_2\}$

因此，构造函数$F(x)=[f(x),f(x+1),f(x+2)]$，可得

$$\begin{split} F(0)&=[f(0),f(1),f(2)] \\ F(x+1)&=[f(x+1),f(x+2),f(x+3)] \\ &=[f(x+1),f(x+2),f(x) + (f(x+1))^2 + (f(x+2))^3] \\ &=[(F(x))_1,(F(x))_2,(F(x))_0 + ((F(x))_1)^2 + ((F(x))_2)^3] \end{split}$$

记

$$\begin{split} a&=[f(0),f(1),f(2)] \\ G(x,y)&=[(y)_1,(y)_2,(y)_0 + ((y)_1)^2 + ((y)_2)^3] \end{split}$$

显然有，$a\in\N$为常数且$G\inPRF$，故而$F(x)=Prim^0[a,G]\inPRF$

最终可得$f(x)=(F(x))_0\inPRF$

1.16 设$f:\N\to\N$满足

$$\begin{split} f(0)&=0,\\ f(1)&=1,\\ f(2)&=2^2,\\ f(3)&={3^3}^3,\\ &\cdots\\ f(n)&=\underbrace {n^{⋰^n}}_{n\text{个}n}, \end{split}$$

证明：$f\in{\PRF-\EF}$

证明：原命题可以等价地分为两个子命题，$f\inPRF$且$f\notEF$

• 构造函数$h(x,y)$使得

  $$h(x,0)=x \\ h(x,y+1)=x^{h(x,y)}$$

  显然，$h(x,y)=Prim^1[P_1^1,Comp[exp,P_1^3,P_3^3]]\inPRF$

• 要证明$f\notEF$，可以采用反证法，假设$f\inEF$

  那么对于$\EF$的控制函数$G(k,x)=\underbrace {2^{2^{⋰^{2^x}}}}_{k\text{个}2}$，必然存在常数$k\in\N$使得

  $$\forall x\in\N, f(x)\lt G(k,x)$$

  然而，只需取$x=k+2\ge 2$

  $$f(x)=\underbrace {x^{⋰^x}}_{k+2\text{个}x} \ge \underbrace {2^{2^{⋰^{2^x}}}}_{k+1\text{个}2} \ge \underbrace {2^{2^{⋰^{2^x}}}}_{k\text{个}2} = G(k,x)$$

  矛盾，故$f\notEF$

1.17 设$g:\N\to\N\in\PRF,f:\N^2\to\N$，满足

$$f(x,0)=g(x),\\ f(x,y+1)=f(f(\cdots f(f(x,y),y-1),\cdots),0).$$

证明：$f\inPRF$

证明： 先证明$f(x,y)=\begin{cases}g(x),&y=0,\\g^{2^{(y-1)}}(x),&y\neq 0.\end{cases}$

数学归纳法，若已知对$\forall y\le n$上述结论成立，

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

因此上述$f(x)$的表达式得证。

构造函数$Y(y)=\begin{cases}1,&y=0,\\2^{(y-1)},&y\neq 0.\end{cases}$，再证明$Y\inPRF$，

又因为$Y(y)=\lfloor \frac{2^yN^2(y)+2N(y)}2 \rfloor$（利用$N,N^2$函数实现条件判断，先乘2再除2规避$2^{-1}$无定义问题）

所以，$Y\inPRF$。

而函数$G(x,n)=g^n(x)\in\mathcal {ITF}=\PRF$。

$f(x,y)=G(x,Y(y))\inPRF$得证。

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

(题目里说的是递归函数，不清楚是指代$\GRF$还是$\RF$，以下证明中为$\GRF$，但换成$\RF$也是一样可以。)

证明：这个问题具有对称性，只需证明$f\inGRF\Longrightarrow g\inGRF$，自然有$g\inGRF\Longrightarrow g\inGRF$，继而$f\inGRF \iff g\inGRF$。

构造集合$\mathcal D\subset N^k$，使得$\forall \vx \in\mathcal D,f(\vx)\neq g(\vx)$且$\forall \vx \in\mathcal \N^k - D,f(\vx)=g(\vx)$。

由已知条件，集合$\mathcal D$只有有限个元素，并记常数$N=|\mathcal D|$，可以将之一一枚举出来$\mathcal D=\{\vx_1,\vx_2,\cdots,\vx_{N}\}$。

与之对应地，此时$g(x)$的函数值意义枚举为$\{y_1,y_2,\cdots,y_{N}\}$。

$g(x)=f(x)(\prod\limits_{i=1}^N{eq(\vx,\vx_i)})+\sum\limits_{i=1}^N{(N(eq(\vx,\vx_i))y_i)}$

（这里的迭加与迭乘范围为有限常数项，仅仅是书写上的简洁表示，并非是作为算子的迭加迭乘）

因此$g\inGRF$，进而原命题得证。

1.19 证明：

$$f(n)=\lfloor (\frac{\sqrt 5 + 1}2) n \rfloor$$

为初等函数。

证明：$\frac{\sqrt 5 + 1}2 \le 2\Longrightarrow f(n)\le2n \Longrightarrow f(n)=\bmax {2n} {x\le (\frac{\sqrt 5 + 1}2) n}$

$$\begin{split} & x \le (\frac{\sqrt 5 + 1}2) n \\ &\iff 2x \le (\sqrt 5 + 1)n \\ &\iff 2x-n \le \sqrt 5 n \\ &\iff 4x^2-4xn+n^2\le 5n^2 \\ &\iff x^2-xn-n^2\le 0 \\ &\iff x^2\dotminus xn\dotminus n^2 = 0 \end{split}$$

$\therefore f(n)=\bmax {2n} {N^2(x^2\dotminus xn\dotminus n^2)}\inEF$

1.20 证明：$Ack(4,n)\in\PRF-\EF$，其中$Ack(x,y)$是Ackermann函数。

证明： 记$f(n)=Ack(4,n)+3=\underbrace {2^{2^{⋰^2}}}_{n+3\text{个}2}$

$$Ack(4,n)\in\PRF-\EF \iff \begin{cases}Ack(4,n)\inPRF\\Ack(4,n)\notEF\end{cases} \iff \begin{cases}f(n)\inPRF\\f(n)\notEF\end{cases}$$

• 构造常数$a=2^{2^2}\in\N$，函数$g(x,y)=2^y\inPRF$，有

  $$f(0)=a \\ f(n+1)=g(n,f(n))$$

  显然，$f(n)=Prim^0[a,g]\inPRF \iff Ack(4,n)\inPRF$

• 要证明$f\notEF$，可以采用反证法，假设$f\inEF$

  那么对于$\EF$的控制函数$G(k,n)=\underbrace {2^{2^{⋰^{2^n}}}}_{k\text{个}2}$，必然存在常数$k\in\N$使得

  $$\forall n\in\N, f(n)\lt G(k,n)$$

  然而，只需取$n=2k$

  $$f(n)=f(2k)=\underbrace {2^{⋰^2}}_{2k+3\text{个}2} = G(k,{\underbrace {2^{⋰^2}}_{k+3\text{个}2}}) \ge G(k,2(k+3)) \gt G(k,2k) = G(k,n)$$

  矛盾，故$f\notEF\iff Ack(4,n)\notEF$

1.21 设$f:\N\to\N$，$f$为单射(1-1)且满射(onto)，证明：$f\inGRF\iff f^{-1}\inGRF$。

证明：

• $f^{-1}(y)$可以定义为如下形式，

  $$f^{-1}(y)=\mu x. {[f(x)\dotminus y]}$$

  又因为对任意$y\in\N$，存在且只存在为一的$x\in\N$使得$f(x)=y$，即$[f(x)-y]$是正则的。

  $\GRF$对正则$\mu$算子封闭，$f\inGRF \Longrightarrow f^{-1}\inGRF$

• 因为$f$是单射且满射的，所以$f^{-1}$也是单射且满射的，

  $$f^{-1}\inGRF\Longrightarrow {(f^{-1})}^{-1} = f\inGRF$$

1.22 设$p(x)$为整系数多项式，令$f:\N\to\N$定义为$f(a)=p(x)-a\text{对于}x\text{的非负整数根}$，证明$f\inRF$。

证明：记$p(x)=\sum_{i=0}^n{k_ix^i}$且$P=\{i | k_i\gt0\},N=\{i|k_i\lt0\}$，即$p(x)=\sum_{i\in P}{|k_i|x^i}-\sum_{i\in N}{|k_i|x^i}$。

同时构造$F(x,a)=\Big|\sum_{i\in P}{|a_i|x^i}-\sum_{i\in N}{|a_i|x^i} - a\Big|$，其中$x\in\N,a\in\N$。

• 先证$F\inRF$

  显然幂函数与带绝对值的减法都属于$\RF$，所以$F\inRF$

• 再证$f=\mu a.{[F(x,a)]}$

  已知$\sum_{i\in P}{|a_i|x^i} \ge 0, \sum_{i\in N}{|a_i|x^i} \ge 0, a \ge 0$，可得，

  $F(x,a)=0 \iff \sum_{i\in P}{|a_i|x^i} - \sum_{i\in N}{|a_i|x^i} - a = 0 \iff p(x)-a=0$

  即$p(x)-a$的零点与$F(x,a)$的零点等价，$\therefore f=\mu a.{[F(x,a)]}$。

综上，$f \inRF$。

1.23 设

$$f(x)=\begin{cases} x/y, &\text{若}y\neq 0\text{且}y\mid x, \\ \uparrow, &\text{否则}. \end{cases}$$

证明$f\inRF$。

证明：$f(x)=\mu k. {[x\dotminus ky+N(y)]}$

• 当$y=0$，$f(x)=\mu k.[x+1]\Longrightarrow\forall x,f(x)=\uparrow$
• 当$y\neq0$且$y \nmid x$，$f(x)=\mu k.[x\dotminus ky]\Longrightarrow\forall x,f(x)=\uparrow$
• 当$y\neq0$且$y \mid x$，$f(x)=\mu k.[x\dotminus ky]\Longrightarrow f(x)=x/y$

该$f(x)$表达形式与原定义等价。

$[x\dotminus ky+N(y)]\inRF\Longrightarrow f\inRF$

1.24 设$g:\N\to\N$满足

$$g(0)=0,\\ g(1)=1,\\ g(n+2)=rs((2002g(n+1)+2003g(n)),2005).$$

(1)试求$g(2006)$，

(2)证明$g\inEF$。

解：先在实数范围类讨论数列$a_1=0,a_2=1,a_{n+2}=2002a_{n+1}+2003a_n$的通项公式

其特征方程$z^2=2002z+2003$存在两个实数解-1和2003，进一步地得出其通项公式，

$$a_n=\frac{(-1)^n+{2003}^{n-1}}{2004}$$

因为$g(n)\equiv a_{n+1} \,mod\, 2005$，所以$g(n)=rs(a_{n+1},2005)=rs(\frac{(-1)^{n+1}+2003^n}{2004},2005)$，

显然，$g\inEF$，（2）得证

再求$g(2006)=rs(\frac{2003^{2006}-1}{2004},2005)=1942$，（1）得解

1.25 设$f:\N\to\N$定义为

$$f(n)=\pi\text{的十进制展开式中第}\text{n位数字}$$

例如$f(0)=3,f(1)=1,f(2)=4$，证明：$f\inGRF$

证明：在$m\times m$分辨率下拟合一个四分之一圆，即取集合$\mathcal S=\{(x,y)\mid x,y\in\N,x^2+y^2\le m^2\}$，

记其拟合面积$S(m)=|\mathcal S|=\sum\limits_{i=0}^m{\sum\limits_{j=0}^m{N(i^2+j^2\dotminus m^2)}}$，显然$S\inGRF$。

考虑真实的四分之一圆面积$S'=\frac \pi 4 m^2$，这种拟合方法总是会高估圆面积，即$S>S'$，

但二者的误差不超过接触边界的像素数量，而接触边界的像素数量不超过$2m$，所以有

$$0\lt S-S'=S - \frac \pi 4 m^2\le2m$$

取$m=10^k,k\in\N$并另记$P(k)=\frac{4S(10^k)}{10^{2k}}=\frac{4S(m)}{m^2} \inGRF$

$$0\lt P(n)-\pi=\frac{4S(m)}{m^2} - \pi \le\frac8m \lt \frac{10}m = \frac{10}{10^k}=10^{1-k}$$

也就是说，用$P(k)$近似$\pi$的正误差不超过$10^{1-k}$。

因此需要寻找合适的分辨率指数$k=K(n)$，使得$P(k)$的结果对取$\pi$的第$n$位足够精确，

$\pi=3.14\dots$，如果要从$P(k)$中精确获得$\pi$的第$n$位，那么可以通过如下两条保证获得：

1. $P(k)$的误差不超过$10^{-1-n}$（比如，要取第0位，即个位，误差小于0.1）
2. $P(k)$的第$n+1$位不应该是0，防止正误差导致的进位变化（3.00与2.99误差小于0.1，但由于进位导致个位不一致）

表示为：

$$\therefore K(n)=min\{x:10^{1-x}\le10^{-1-n} \wedge rs(\lfloor 10^{n+1}P(x) \rfloor,10)\neq 0\} \inGRF$$

通过以上保证，取$P(K(n))$的第$n$位就是$\pi$的第$n$位。

综上所述：

$$S(m)=\sum\limits_{i=0}^m{\sum\limits_{j=0}^m{N(i^2+j^2\dotminus m^2)}}\inGRF\\ P(k)=\frac{4S(10^k)}{10^{2k}}\\ K(n)=min\{x:x\gt n \wedge rs(\lfloor 10^{n+1}P(x) \rfloor,10)\neq 0\}\inGRF\\ f(n)=rs(\lfloor 10^n P(K(n)) \rfloor,10)\inGRF$$

原命题得证。