递归函数与关系 (Recursive functions and relations)
递归函数类
初始函数
定义：初始函数
初始函数 (initial functions) 是如下对于所有 \(k,n\in \omega\) 且 \(i<k\) 都成立的函数：
(1) 常数(constant)函数：$$ \mathrm{Cs}_n^k(m_0,\cdots,m_{k-1}) = n $$
(2) 投射(projection)函数：$$ \mathrm{Pr}_i^k(m_0,\cdots,m_{k-1}) = m_i $$
(3) 后继(successor)函数：$$ \mathrm{Sc}_i^k(m_0,\cdots,m_{k-1}) = m_i+1 $$
部分教材上常数函数被换成了零函数，但是实际上这套体系仍然是等价的.
这几个操作都比较简单，常数函数就是将所有输入变为一个常数，投射函数是保留其中一个输入然后输出，后继则是输出其中一个输入的后继.
需要注意的是，\(m_i+1\) 仅仅是后继的一种记法，它不代表加法运算. 因此加法运算的原始递归性我们后续仍然需要证明.
为方便记述，一元的后继直接写为 \(\mathrm{Sc}(x)=x+1\) .
原始递归
定义：复合运算
对于任意的函数 \(G,H_0,\cdots,H_{l-1}\) ，复合函数 \(\mathrm{Cmp}_l^k(G,H_0,\cdots,H_{l-1})\) 是符合如下定义的函数 \(F\) ：
- 如果 \(G\) 是 \(l\)-元函数，且 \(H_0,\cdots,H_{l-1}\) 都是 \(k\)-元的，那么 $$ F(m_0,\cdots,m_{k-1})=G(H_0(m_0,\cdots,m_{k-1}),\cdots,H_{l-1}(m_0,\cdots,m_{k-1})) $$
- 否则，\(F(m_0,\cdots,m_{k-1})=0\).
这里的复合运算就是我们通常理解的复合运算.
定义：原始递归
对于任意函数 \(G\) 和 \(H\) ，\(\mathrm{Rec}^{k+1}(G,H)\) 是对于所有 \(m_0,\cdots,m_{k-1}\) 和 \(n\in \omega\) 的，满足如下定义的函数 \(F\) ：
- 如果 \(G\) 是 \(k\)-元的且 \(H\) 是 \((k+2)\)-元的，那么 $$ \begin{cases}F(m_0,\cdots,m_{k-1},0)=G(m_0,\cdots,m_{k-1}); \ F(m_0,\cdots,m_{k-1},n+1)=H(F(m_0,\cdots,m_{k-1},n),m_0,\cdots,m_{k-1},n)\end{cases} $$
- 否则，\(F(m_0,\cdots,m_{k-1},n)=0\).
称 \(F\) 是 \(G\) 和 \(H\) 通过原始递归生成出来的.
同时，借用集合论的说法，将上述的原始递归函数全体记为原始递归函数类 \(\mathrm{Prim}\) .
此外，需要注意其中的 \(G\) 可能变成零元函数，零元函数一般情况下默认为常值函数.
这是一个自下而上的定义，换句话说，如果
- 初始函数在 \(\mathrm{Prim}\) 中；
- 函数复合运算封闭；
那么得到的函数类就是原始递归的函数类.
常见的原始递归函数
命题：常见的原始递归函数
- \(+,\times,m^n\) 和阶乘运算 \(!\).
- \(\mathrm{Pred}(0)=0;\mathrm{Pred}(n+1)=n\). （前趋函数）
-
\[ m\dot{-}n = \begin{cases}m-n, & m \geqslant n, \\ 0, & \text{Otherwise}.\end{cases} \]
- \(|m-n|\);
- \(\mathrm{Sg}(0)=0; \mathrm{Sg}(m+1)=1\).
提示
这里我们将详细地走一遍思维上的流程，熟悉原始递归函数的意义.
(1) 对于加法，我们实际上就是要证明如下函数是原始递归函数：
那么根据定义，我们要找到一个一元函数 \(G(x)\) 以及三元函数 \(H(x,y,z)\) 使得
一元函数 \(G(x)\) 显然很好找，取一元投射函数 \(\mathrm{Pr}_0^1\) 即可；对 \(H(x,y,z)\) ，由于 \(F(m,n) = m+n\) ，那么 取后继函数 \(\mathrm{Sc}_2^3\) 即可. 故加法是原始递归函数.
结合加法，可以得到乘法的两个函数取 \(G(m)=0\) 和 \(H(m,n,F(m,n)) = F(m,n)+m\) 即可.
对于乘方，和乘法基本一致的推导思路，在此略. 对于阶乘， 有
因此零元函数 \(G() = \mathrm{Cs}_0^1\) . 同理对于 \(H(m,F(m))\) ，取 \(\mathrm{Sc}(m)\times F(m)\) 即可.
我们不难发现，实际上如果我们能写出递归方程，我们就无需费劲按照定义去写明了，例如加法有
递归方程的第二项能使用的元仅有 \(x,y,F(x,y)\) ，运算仅能是初始函数和已经证明出的原始递归函数.
(2) 考虑递归方程：
易知成立.
(3) 我们可以利用已知的原始递归函数.
考虑
可知为原始递归函数.
(4) \(|m-n| = (m\dot{-}n)+(n\dot{-}m)\).
(5) \(\mathrm{Sg}(x) = x- \mathrm{Pred}(x)\) . （这个函数可以理解为 \(\left\lbrace 0 \right\rbrace\) 的特征函数，在后续有作用） \(\square\)
例题：原始递归函数证明
证明：\(\min\left\lbrace m,n \right\rbrace\) 是原始递归函数.
考虑
然后
\(\square\)
正则极小化
定义：正则极小化
对于任意的 \(k\in \omega\) 以及任意函数 \(G\) ，\(\mathrm{Se}^k(G)\) 是满足如下条件的函数 \(F\) ：
- 如果 \(G\) 是 \(k+1\) 元的，且对于所有 \(m_0,\cdots,m_{k-1}\) ，都存在 \(n\) 使得 \(G(m_0,\cdots,m_{k-1},n)=0\) ，那么对于所有的 \(m_0,\cdots,m_{k-1}\) ，$$ F(m_0,\cdots,m_{k-1}) = \text{least } n[G(m_0,\cdots,m_{k-1},n) = 0]. $$
- 对于其他的情形，\(F(m_0,\cdots,m_{k-1})=0\).
那么，\(F\) 称为由 \(G\) 通过正则极小化(unbounded search)得到的，我们称条件：
$$ \forall m_0 \cdots \forall m_{k-1} \exists n [G(m_0,\cdots,m_{k-1},n)=0]. $$
为 \(G\) 的正则极小化条件 (search condition).
递归函数
定义：递归函数
递归函数类 \(\mathrm{Rec}\) 是包含初始函数以及复合运算、原始递归、正则极小化封闭的最小类.
命题
\(\mathrm{Prim}\) 以及 \(\mathrm{Rec}\) 都是可数的.
这里的可数性证明和命题逻辑当中的 \(L\) 语句的可数性证明是基本一致的. \(\square\)
“自下而上”和“自上而下”
究其原因，是“自下而上”的递归定义生成的集合与类在操作有限时也仅能生成可数个对象.
如果是自上而下，相对来说就会要麻烦很多.
原始递归关系
定义：关系的特征函数以及原始递归关系
对于任意的 \(k\in \omega\) 以及任意的关系 \(R \subseteq \omega^k\) ，
- 对于任意的 \(m\_0,\cdots,m\_{k-1}\in \omega\) ，$$ \mathrm{K}_R(m_0,\cdots,m_{k-1}) = \begin{cases}0, & \text{if }\sim R(m_0,\cdots,m_{k-1}); \\ 1, & \text{if } R(m_0,\cdots,m_{k-1}).\end{cases} $$ 其中 \(\mathrm{K}\_R\) 称为 \(R\) 的特征函数.
- 如果 \(\mathrm{K}\_R\) 是（原始）递归函数，则 \(R\) 称为（原始）递归关系.
例题：原始递归关系
证明：二元谓词 \(=\) ， \(\leqslant\) 和 \(<\) 都是原始递归的.
首先 \(\mathrm{K}_<(m,n) = \mathrm{Sg}(n\dot{-}m)\) ，易知
对于等于，考虑 \(\mathrm{K}_=(m,n) = \mathrm{K}_\leqslant (m,n) \times \mathrm{K}_\geqslant (m,n)\) . \(\square\)
分情形定义
引理：分情形定义
如果 \(f_1\) 和 \(f_2\) 都是原始递归函数，并且 \(P\) 是原始递归谓词，则函数
$$ f(x) = \begin{cases}f_1(x), & \text{如果}P(x)\text{成立}, \\ f_2(x), & \text{其他}. \end{cases} $$
也是原始递归的.
这个引理的意义实际上就是在说明 if else 的逻辑指令在程序语言当中是可行的. 具体后续将说明.
证明：考虑如下的函数即可
\(\square\)
带余除法
接下来，四则运算的原始递归性我们只剩下除法需要处理了，由于我们讨论的内容限定在自然数，所以除法自然就是带余除法.
记
为带余除法式，且规定 \(\mathrm{quo}(0,y) =0\) 且 \(\mathrm{rem}(0,y) = 0\) ，此时我们有如下的引理：
引理：带余除法的原始递归性
函数 \(\mathrm{quo}(x,y)\) 和 \(\mathrm{rem}(x,y)\) 都是原始递归的.
首先定义二元谓词 \(P(x,y)\) 为
如果该谓词是原始递归的，那么利用下面的递归定义即可：
以及
下面证明该谓词是原始递归的，设其示性函数为 \(\mathrm{K}(x,y)\) ，则利用如下的递归方程即可证明：
\(\square\)
有界极小算子
定义：有界极小算子 (bounded search)
令 \(P(\boldsymbol{x},z)\) 为一个 \((k+1)\)-元性质，定义：
$$ (\mu z \leqslant y) P (\boldsymbol{x},z) = \begin{cases}最小的满足 P(\boldsymbol{x},z) 且 \leqslant y 的 z, & 如果它存在; \\ y+1, & 否则.\end{cases} $$
引理
如果 \(f(\boldsymbol{x},y)\) 是原始递归的，则有界和 \(\sum\limits_{y \leqslant z} f(\boldsymbol{x},y)\) 与有界积 \(\prod\limits_{y \leqslant z}f(\boldsymbol{x},y)\) 都是原始递归的.
引理
假定 \(P(\boldsymbol{x},z)\) 是一个原始递归的谓词，则
- 谓词 \(E(\boldsymbol{x},y):= (\exists z \leqslant y)P(\boldsymbol{x},z)\) 和 \(A(\boldsymbol{x},y):=(\forall z \leqslant y)P(\boldsymbol{x},z)\) 都是原始递归的；
- 函数 \(f(\boldsymbol{x},y):= (\mu z \leqslant y)P(\boldsymbol{x},z)\) 也是原始递归的.
这个引理的意义在于：有界的 for 循环是原始递归的操作.
(1) 根据特征函数的定义，有 \((\forall z \leqslant y)P(\boldsymbol{x},z)\) 为真当且仅当 \(\prod\limits_{z \leqslant y}\chi_P(\boldsymbol{x},z)=1\) ，存在量词的形式作否定即可.
(2) 注意到
即可. \(\square\)
编码与素数可计算性
接下来讨论有关素数的可计算性问题.
整除与素数
命题：整除关系
\(m\) 整除 \(n\) 的关系是原始递归的.
注意到 \(m\mid n\iff (\exists p < n+1)[m\times p = n]\) . 根据前面的结果它显然是原始递归的. \(\square\)
命题：素数关系
谓词“\(x\) 是素数”是原始递归的.
回忆 Euclid 的无穷素数证明：给定 \(p_0,\cdots,p_n\) ，\(\prod\limits_{j=0}^n p_j+1\) 显然是素数，此时我们在 \(p_{n+1}\) 和 \(\prod\limits_{j=0}^n p_j+1\) 之间寻找素数即可，利用如下的原始递归方程：
\(\square\)
定义：素数函数
定义 \(p_n\) 为第 \(n\) 个素数，有 \(p_0=2,p_1=3,\cdots\).
命题：素数函数是原始递归的
函数 \(n\mapsto p_n\) 是原始递归的.
根据上面的证明，这个函数显然也是原始递归的.
编码
利用数论的算术基本定理，有如下的定理：
定理：自然数有穷序列编码
对任意自然数 \(a\) ，都存在唯一的自然数序列 \(\left\langle a_0,\cdots,a_n \right\rangle\) ，使得
$$ a = p_0^{a_0+1}\cdots p_n^{a_n+1} $$
其中 \(p_i\) 为第 \(i\) 个素数.
编码方式
需要注意的是，实际上这个编码的定义方式借用了数论当中的基本定理，也就是一个自然数可以分解为素数的乘积.
这并不意味这分拆成素数是唯一的编码方式，只不过这里使用素数相对更为简单而已.
此外，在部分教材当中，由于我们用序列表示了这样的乘积，它可以被称为哥德尔数，注意空序列的哥德尔数是 \(1\) .
定义：长度函数
定义函数 \(\mathrm{lh}: \mathbb{N}\to \mathbb{N}\) 为 \(\mathrm{lh}(a) = \mu k \leqslant a (p_k\not\mid a)\) ，称 \(\mathrm{lh}(a)\) 为长度函数，因为 \(\mathrm{lh}(1)=0\) 且对于任意的哥德尔数 \(a = \left\langle a_0,\cdots,a_n \right\rangle\) ，都有 \(\mathrm{lh}(a)=n+1\).
定义：\((s)_i\) 分量函数
对于任意的 \(s,i\in \omega\) ，定义 \((s)_i\) 为小于 \(s\) 且满足
$$ p_i^{m+2} \not| s $$
的最小的 \(m\).
对于具体的数的编码，来看个例子，例如 \(9\) ：
我们容易写出 \(9\) 的编码序列：
分量函数之所以称为分量函数，是由于它刚好能从中挑出第 \(i\) 项，例如 \((9)_1 = 1\) （注意从 \(0\) 开始是首项）.
定义：串接函数
对自然数 \(a,b\) ，定义串接函数 \(a\hat{\quad}b\) 如下
$$ a\hat{\quad} b = a\cdot \prod_{i < \mathrm{lh}(b)}p_{\mathrm{lh}(a)+i}^{(b)_i+1} $$
最后，上述的函数都是原始递归的，这里略去证明.
历史函数
递归函数
非原始递归函数
我们来看一个例子叫做 Ackerman 函数，记为 \(A(x,y)\) ，它有如下的递推关系：
它的增长是非常快的，我们不妨列表：
通过归纳法，不难证明 \(A(x,y)\) 对所有的自然数 \(x,y\) 都是有定义的.
对于给定的 \(p\) ，我们设 \(A_p(n) = A(p,n)\) ，此时我们将二元函数转变为一元函数研究 .