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

1

习题1.1

证明：对于固定的$k$，一元数论函数$x+k\in \mathcal{BF}$

证：

用$k$个后继函数复合即可，$S\circ S\circ \cdots \circ S$。

2

习题1.2

证明：对任意$k\in \mathbb{N}^+$，$f:\mathbb{N}^k\rightarrow \mathbb{N}$，若$f\in \mathcal{BF}$，则存在$h$，使得 $$ f(\overrightarrow{x})<\lVert\overrightarrow{x}\rVert+h. $$ 其中$\lVert\overrightarrow{x}\rVert\equiv\max\{x_i:1\leq i\leq k\}$

证：

由于$f\in\mathcal{BF}$，故存在构造序列$f_0,f_1,\dots,f_n$使得$f=f_n$.

下面对$n$做数学归纳。

当$n=0$时，由$f_0\in\mathcal{IF}$。若$f_0$为$Z$，则$Z(x)=0<\lVert x\rVert + 2$；若$f_0$为$S$，则$S(x)=x+1<\lVert x\rVert + 2$；若$f_0$为$P^n_i$，则$P^n_i(\overrightarrow{x})<\lVert x\rVert + 2$。

假设$0\leq i\leq k$时，对于$f_i$有结论成立。

当$k+1$时， $$ \begin{align} f_{k+1}(\overrightarrow{x}) &= f_{i_0}(f_{i_1}(\overrightarrow{x}),\dots,f_{i_t}(\overrightarrow{x})) \\ & < \max{ \{f_{i_j}(\overrightarrow{x}):1\leq j\leq t\}} + h_0 \\ & < \max{ \{\lVert \overrightarrow{x} \rVert + h_j:1\leq j\leq t\}} + h_0 \\ & = \lVert \overrightarrow{x} \rVert + h_0 + \max{\{ h_j:1\leq j\leq t\}} \end{align} $$

令$h=h_0+\max{\{ h_j:1\leq j\leq t\}}$，结论成立。

故存在$h$，使得$f(\overrightarrow{x})<\lVert\overrightarrow{x}\rVert+h$。

3

习题1.3

证明：二元数论函数$x+y\not\in \mathcal{BF}$。

证：

反设$x+y\in \mathcal{BF}$。由1.2，存在$h$，使得$x+y<\max{\{x,y\}}+h$。

令$x=y=h+1$，则$x+y=2h+2<h+1+h=2h+1$，矛盾。

4

习题1.4

证明：二元数论函数$x\dot- y\not\in \mathcal{BF}$。

证：

首先证明下面的命题

若$f:\mathbb{N}^n\rightarrow \mathbb{N}$，其中$n\in\mathbb{N}^+$，$f\in\mathcal{BF}$，则$f(\overrightarrow{x})$仅与$\overrightarrow{x}$某一分量有关，与其它分量无关。

证：

由于$f\in\mathcal{BF}$，故存在构造序列$f_0,f_1,\dots,f_n$使得$f=f_n$.

下面对$n$做数学归纳。

当$n=0$时，由$f_0\in\mathcal{IF}$。若$f_0$为$Z$或$S$，结论成立。若$f_0$为$P^n_i$，则$P^n_i(\overrightarrow{x})=x_i$，仅与$\overrightarrow{x}$的$i$分量有关，结论成立。

假设$0\leq i\leq k$时，对于$f_i$有结论成立。

当$k+1$时，$f_{k+1}(\overrightarrow{x}) = f_{i_0}(f_{i_1}(\overrightarrow{x}),\dots,f_{i_m}(\overrightarrow{x}))$。由于$f_{i_0}(\overrightarrow{x})$仅与$\overrightarrow{x}$某一分量有关，不妨设为第$j$分量。由于$f_{j}(\overrightarrow{x})$仅与$\overrightarrow{x}$某一分量有关，不妨设为第$t$分量。故$f_{k+1}(\overrightarrow{x})$仅与$\overrightarrow{x}$第$t$分量有关。

综上，结论成立。

对于$x\dot- y$，其函数值与$x,y$均有关系，故$x\dot- y\not\in \mathcal{BF}$。

5

习题1.5

设$\text{pg}(x,y)=2^x(2y+1)\dot-1$，证明：存在初等函数$K(x)$和$L(x)$使得 $$ \begin{align} K(\text{pg}(x,y)) &=x, \\ L(\text{pg}(x,y)) &= y, \\ \text{pg}(K(z),L(z)) &=z. \end{align} $$

证：

由于$x,y\in\mathbb{N}$，故$2^x(2y+1)\geq 2^0(2*0+1)=1$。令$\text{pg}(x,y)=z$，故$2^x(2y+1)=z+1$，故$x=\text{ep}_0(z+1)$，即 $$ K(z)=\text{ep}_0(z+1) $$ $2y+1=\left\lfloor\frac{z+1}{2^{\text{ep}_0(z+1)}}\right\rfloor$，故$y=\left\lfloor\frac{\left\lfloor\frac{z+1}{2^{\text{ep}_0(z+1)}}\right\rfloor\dot-1}{2}\right\rfloor$，即 $$ L(z)=\left\lfloor\frac{\left\lfloor\frac{z+1}{2^{\text{ep}_0(z+1)}}\right\rfloor\dot-1}{2}\right\rfloor $$ 易见，$\text{ran}(\text{pg})=\mathbb{N}$，即$\text{pg}$穷尽一切自然数，故$\{\text{pg},K,L\}$是一一对应的，有$\text{pg}(K(z),L(z)) =z$.

6

习题1.6

设$f:\mathbb{N}\rightarrow\mathbb{N}$，证明：$f$可以作为配对函数的左函数当且仅当对任何$i\in\mathbb{N}$， $$ |\{ x\in\mathbb{N}: f(x)=i \}|=\aleph_0\,. $$

证：

$``\Rightarrow"$：

设$f$为配对函数$\text{pg}(x,y)$的左函数，故对任意$j$，有$f(\text{pg}(i,j))=i$。

故对于任何$i\in\mathbb{N}$，$\{x\in\mathbb{N}:f(x)=i\}=\{\text{pg}(i,j):j\in\mathbb{N}\}$.

对于配对函数$\text{pg}(i,j)$，若$j_1\not=j_2$，必有$\text{pg}(i,j_1)\not=\text{pg}(i,j_2)$（否则右函数不存在）。故$|\{\text{pg}(i,j):j\in\mathbb{N}\}|=|\{j:j\in\mathbb{N}\}|=\aleph_0$.

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

$``\Leftarrow"$：

若对任意$i\in\mathbb{N}$，$|\{ z\in\mathbb{N}: f(z)=i \}|=\aleph_0$，即$f(z)=i$有$\aleph_0$个解。因为$\mathbb{N}$良序，解可记为$z_{i,0},z_{i,1},\dots$

可定义配对函数$\text{pg}(i,j)=z_{i,j}$，其中$i,j\in\mathbb{N}$. $f(\text{pg}(i,j))=i$为左函数，$g(\text{pg}(i,j))=j$为右函数。

7

习题1.7

证明：从本原函数出发，经复合和算子$\prod^m_{i=n}[\cdot]$可以生成所有的初等函数，这里 $$ \prod^m_{i=n}[f(i, \overrightarrow{x})]= \begin{cases} f(n, \overrightarrow{x})\cdot f(n+1, \overrightarrow{x})\cdot \cdots \cdot f(m, \overrightarrow{x}), &\text{若}m\geq n,\\ 1, &\text{若}m<n. \end{cases} $$

证：

只需证$\sum^n_{i=0},\prod^n_{i=0},\ddot-$可以表示出。

易见$\prod^n_{i=0}$可以表示出。

$x^y=\prod^y_{i=1}P^1_1(x)$，含义为$y$个$x$相乘。特别地，$y$个2相乘，$2^y=\prod^y_{i=1}SSZ(i)$，其中$P^1_1,S,Z\in\mathcal{IF}$.

$$N(x)=\prod^x_{i=1}Z(i)= \begin{cases} 0, \text{if } x\geq 1\\\\ 1, \text{if } x=0 \end{cases}$$

$$leq(x,y)=\prod^y_{i=x}Z(i)= \begin{cases} 0, \text{if } x\leq y\\\\ 1, \text{if } x>y \end{cases}$$

$$geq(x,y)=\prod^x_{i=y}Z(i)= \begin{cases} 0, \text{if } x\geq y\\\\ 1, \text{if } x<y \end{cases}$$

$$eq(x,y)=leq(x,y)^{N(geq(x,y))}= \begin{cases} 0, \text{if } x= y\\\\ 1, \text{if } x\not=y \end{cases}$$

其中，当$x=y$时，$eq(x,y)=0^{N(0)}=0^1=0$；当$x<y$时，$eq(x,y)=0^{N(1)}=0^0=1$；当$x>y$时，$eq(x,y)=1^{N(0)}=1^1=1$.

$$neq(x,y)=N(eq(x,y))= \begin{cases} 0, \text{if } x\not=y \\\\ 1, \text{if } x=y \end{cases}$$

$$ \log (x)=\prod^x_{i=0}i^{neq(2^i,x)} $$ 其中$\log$以2为底，输入$x$需要是2的整数幂，即存在$i$，使得$2^i=x$.

$$\sum^m_{i=n}f(i,\overrightarrow{x})=\log(2^{\sum^m_{i=n}f(i,\overrightarrow{x})})=\log(\prod^m_{i=n}2^{f(i,\overrightarrow{x})})$$

$$x\cdot y=\sum^x_{i=1}P^1_1(y)$$

$$x+y=\log(2^x\cdot 2^y)$$

$$x\ddot- y=\sum^x_{i=y+1}SZ(i)+\sum^y_{i=x+1}SZ(i)$$

8

习题1.8

设 $$ M(x)= \begin{cases} M(M(x+11)), &\text{若}x\leq 100,\\ x-10,&\text{若}x>100, \end{cases} $$ 证明： $$ M(x)= \begin{cases} 91, &\text{若}x\leq 100,\\ x-10,&\text{若}x>100. \end{cases} $$

证：

当$x=100$时，$M(100)=M(M(111))=M(101)=91$.

假设$100\geq k\geq 91$时，$M(k)=91$. $M(k-1)=M(M(k+10))=M(k)=91$. 即当$90\leq x\leq 100$时，$M(x)=91$.

假设$90\geq k$时，$M(k)=91$. $M(k-1)=M(M(k+10))=M(91)=91$.

综上，

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

9

习题1.9

证明： $$ \begin{align} \min x\leq n. [f(x,\overrightarrow{y})]&=n\dot- \max x \leq n. [f(n\dot-x,\overrightarrow{y})],\\ \max x\leq n. [f(x,\overrightarrow{y})]&=n\dot- \min x \leq n. [f(n\dot-x,\overrightarrow{y})]. \end{align} $$

证：

首先证明$\min x\leq n. [f(x,\overrightarrow{y})]=n\dot- \max x \leq n. [f(n\dot-x,\overrightarrow{y})]$.

当不存在$0\leq x\leq n$，使得$f(x,\overrightarrow{y})=0$时。$\min x\leq n. [f(x,\overrightarrow{y})]=n$，$\max x \leq n. [f(n\dot-x,\overrightarrow{y})]=0$，$n\dot-0=n$，故左式等于右式。

当存在$0\leq x\leq n$，使得$f(x,\overrightarrow{y})=0$时。设满足条件的最小的$x$为$i$，即$\min x\leq n. [f(x,\overrightarrow{y})]=i$. 易见当$n\dot-i\leq x\leq n$时，$f(n\dot-x,\overrightarrow{y})\not=0$；当$x=n\dot-i$时，$f(n\dot-x,\overrightarrow{y})=0$。故$\max x \leq n. [f(n\dot-x,\overrightarrow{y})]=n\dot-i$，此时右式$=n\dot-(n\dot-i)=i=$左式。

综上，$\min x\leq n. [f(x,\overrightarrow{y})]=n\dot- \max x \leq n. [f(n\dot-x,\overrightarrow{y})]$.

同理可证，$\max x\leq n. [f(x,\overrightarrow{y})]=n\dot- \min x \leq n. [f(n\dot-x,\overrightarrow{y})]$.

10

习题1.10

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

证：

由于$\mathcal{EF}$对于有界$\mu$-算子封闭，而$\max x\leq n. [f(x,\overrightarrow{y})]=n\dot- \min x \leq n. [f(n\dot-x,\overrightarrow{y})]$。故$\mathcal{EF}$对有界$\max$-算子封闭。

11

习题1.11

Euler函数 $\varphi:\mathbb{N}\rightarrow\mathbb{N}$ 定义为 $$ \varphi(n)=|\{ x:0<x\leq n \wedge \text{gcd}(x,n)=1 \}|, $$ 即 $\varphi(n)$ 表示小于等于 $n$ 且与 $n$ 互素的正整数个数。例如 $\varphi(1)=1$ ，因为1与其本身互素；$\varphi(9)=6$，因为9与1，2，4，5，7，8互素。证明：$\varphi\in\mathcal{EF}$.

证：

首先构造初等函数判断$x,y$是否互素。定义$f(x,y)=\begin{cases}1, \text{if gcd}(x,y)=1,\\ 0, \text{otherwise}. \end{cases}$

则$f(x,y)=N\left(\max z\leq x. [\text{rs}(x, z+1)+\text{rs}(y, z+1)]\right)$。当存在 $z\geq 1$ ，使得 $x,y$ 均可整除 $z+1$ 时，$\max z\leq x. [\text{rs}(x, z+1)+\text{rs}(y, z+1)]\geq 1$，则 $f(x,y)=0$ 。否则 $f(x,y)=1$ .

则$\varphi(n)=\sum^{n\dot-1}_{i=0}f(i+1,n)$.

当 $n=1$ 时，$\varphi(1)=f(1,1)=1$；当 $n=9$ 时，$\varphi(9)=6$.

12

习题1.12

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

证：

由命题1.29，$P(n)=$第n个素数，是初等函数。

$$h(x)=\max n\leq x. [\text{rs}(x, P(n))]$$

故$h\in\mathcal{EF}$.