跳转至

递归函数总览

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

  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\)-算子封闭.