递归函数总览

在第一章中，主要介绍了函数集：

1. 本原函数类：$\mathcal{IF}$
2. 基本函数类：$\mathcal{BF}$
3. 初等函数类：$\mathcal{EF}$
4. 原始递归函数：$\mathcal{PRF}$
5. 一般递归函数类：$\mathcal{GRF}$
6. 部分递归函数类：$\mathcal{RF}$

这些函数类有如下关系：

$$\mathcal{IF}\subset\mathcal{BF}\subset\mathcal{EF}\subset\mathcal{PRF}\subset\mathcal{GRF}\subset\mathcal{RF}$$

本原函数

本原函数（$\mathcal{IF}$）只包含三种函数：

1. 零函数$Z:\mathbb{N}\rightarrow \mathbb{N}$，$\forall x\in \mathbb{N}. Z(x)=0$
2. 后继函数$S:\mathbb{N}\rightarrow \mathbb{N}$，$\forall x\in \mathbb{N}. S(x)=x+1$
3. 投影函数$P^n_i:\mathbb{N}^n\rightarrow \mathbb{N}$，$\forall x_1,\dots,x_n\in \mathbb{N}. P^n_i(x_1,\cdots,x_n)=x_i$，其中$n\in\mathbb{N}$且$1\leq i\leq n$.

注意

$\mathcal{IF}$包含三类函数，并不是三个，其中投影函数有很多。

基本函数

基本函数类$\mathcal{BF}$是满足一下条件的最小函数集合：

1. $\mathcal{IF}\subseteq\mathcal{BF}$，这里$\mathcal{IF}$为本原函数集合
2. $\mathcal{BF}$对于复合封闭，即对于任意的$m,n\in\mathbb{N}^+$,$f:\mathbb{N}^m\rightarrow \mathbb{N}$,$g_1,\cdots,g_m:\mathbb{N}^n\rightarrow\mathbb{N}$，若$f,g_1,\cdots,g_m\in\mathcal{BF}$，则$\text{Comp}^n_m[f,g_1,\cdots,g_m]\in\mathcal{BF}$。

典型例子

$x+k$，其中$k$为固定的值。证明

注意

在习题2中，我们证明了$f(\overrightarrow{x})<\lVert\overrightarrow{x}\rVert+h$。即$\lVert\overrightarrow{x}\rVert+h$可以看成是$\mathcal{BF}$的控制函数，任何增长速度超过$\lVert\overrightarrow{x}\rVert+h$均不属于$\mathcal{BF}$。

在习题4中，我们证明了$f(\overrightarrow{x})$仅与$\overrightarrow{x}$某一分量有关，与其它分量无关。由此可见，$\mathcal{BF}$包含的函数非常有限。

初等函数

初等函数类$\mathcal{EF}$是满足一下条件的最小函数集合：

1. $\mathcal{IF}\subseteq\mathcal{EF}$，这里$\mathcal{IF}$为本原函数集合.
2. $x+y$, $x\ddot-y$, $x\times y$, $\lfloor x/y \rfloor$ $\in\mathcal{EF}$.
3. $\mathcal{EF}$对于复合、有界迭加算子$\sum[\cdot]$和有界迭乘算子$\prod[\cdot]$封闭.

典型例子

1. $x+y$, $x\ddot-y$, $x\dot-y$, $x\times y$, $\lfloor x/y \rfloor$
2. 有界$\mu$-算子（引理1.14），有界$\max$-算子（习题1.10）
3. $x^y$（命题1.23）, $\lfloor \sqrt[y]{x} \rfloor$（命题1.24），$rs(x,y)$（命题1.25），$G\ddot{o}del\text{ }\beta$-函数（定义1.14）
4. $\text{prime}(x)\equiv x$为素数（命题1.27），$\pi(x)\equiv$不超过 $x$ 的素数个数（命题1.28），$P(n)\equiv$第 $n$ 个素数（命题1.29），$\text{ep}(n,x)$（命题1.30）

原始递归函数

原始递归函数类$\mathcal{PRF}$是满足一下条件的最小函数集合：

1. $\mathcal{IF}\subseteq\mathcal{PRF}$，这里$\mathcal{IF}$为本原函数集合.
2. $\mathcal{PRF}$对于复合、带参原始递归算子和无参原始递归算子封闭.

一般递归函数（全函数)

一般递归函数类$\mathcal{GRF}$是满足一下条件的最小函数集合：

1. $\mathcal{IF}\subseteq\mathcal{GRF}$，这里$\mathcal{IF}$为本原函数集合.
2. $\mathcal{GRF}$对于复合和原始递归算子封闭.
3. $\mathcal{GRF}$对于正则 $\mu$-算子封闭.

注意

有界 $\mu$-算子，正则 $\mu$-算子， $\mu$-算子关系：

1. 在正则 $\mu$-算子中，我们无法给出 $x$的上界，故只能写成 $\mu x.[f(x,\overrightarrow{y})]$
2. 正则 $\mu$-算子要求 $f$是正则的，得到的函数处处有定义，这点主要区别于 $\mu$-算子。若不要求$f$正则，则正则$\mu$-算子提升为 $\mu$-算子，一般递归函数提升为部分递归函数。

部分递归函数

部分递归函数类$\mathcal{RF}$是满足一下条件的最小函数集合：

1. $\mathcal{IF}\subseteq\mathcal{RF}$，这里$\mathcal{IF}$为本原函数集合.
2. $\mathcal{RF}$对于复合和原始递归算子封闭.
3. $\mathcal{RF}$对于$\mu$-算子封闭.