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

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}\).