看到网上一个题目，证明x开y次方是原始递归函数(primitive recursive function)。这个问题并不难，只要把x开y次方实现出来即可。于是，正好把《递归论》相关内容补一补。
【原始递归函数】
首先，我们明确，《递归论》里研究的都是自然数里的函数。
所谓自然数，在这里的意思是指非负整数，我们可以用Peano五公理定义。
那么原题的x开y次方，x和y当然都是自然数，而且应该都是正整数，自然数下x开y次方的结果为实数下x开y次方得到的结果向下取整。当然，为了方便，x取0或者y取0的函数值可以随便定义。
在讲原始递归函数之前，我们先要定义几个基本函数，我们一般称之为本原函数：
零函数$z$，对于任何自然数，返回0。
后继函数$s$，对于任何自然数，返回它的后继数，也就是传入n返回n+1。
投影函数$p_k^i$，
$p_k^i(a_1,…a_k)=a_i$
以上，零函数和后继函数都是带一个元的函数，投影函数可以带任意多个元(当然，投影函数其实是一堆函数，而不是一个)。
但我们知道，我们平常遇到的自然数下的函数远远不止上面这么点，这就需要不断的用规则来合成新的函数，用于合成原始递归函数的规则有两个：
复合规则：
一个n元函数$f$和n个m元函数$g_0,…g_n$可以通过以下规则得到一个m元函数
$h(a_0,…a_m)=f(g_0(a_0,…a_m),…g_n(a_0,…a_m))$
递归规则:
一个n元函数$f$和一个n+2元函数$g$可以通过以下规则得到一个n+1元函数
$h(a_0,…a_n,0)=f(a_0,…a_n)$
$h(a_0,…a_n,t+1)=g(a_0,…a_n,t,h(a_0,…a_n,t))$
从本原函数开始出发，有限次通过上述规则所得到的函数，就叫原始递归函数了。当然，本原函数自己也是原始递归函数。
这个原始递归函数基本上覆盖了我们常见的几乎所有的自然数下的函数了。当然，既然有原始递归函数，就有一般递归函数了，函数产生规则多了个μ算子，不过这是本文叙述范围之外的事情。不过既然提到，说一下，一般认为，一般递归函数是可计算的，也就是图灵机可以解决的(可停机)。我们平常见到的绝大多数自然数下的函数都是原始递归函数。
【原始递归函数的可计算性】
原始递归函数的可计算性很容易证明。
首先，本原函数是可计算的。
然后，我们来看复合规则，如果$f$和$g_0,…g_n$都是可计算的，那么对于
$h(a_0,…a_m)=f(g_0(a_0,…a_m),…g_n(a_0,…a_m))$
$g_0(a_0,…a_m),…g_n(a_0,…a_m)$都是可计算的，
从而$f(g_0(a_0,…a_m),…g_n(a_0,…a_m))$是可计算的，
从而复合得到的函数$h$是可计算的。
最后，我们来看递归规则，如果$f$和$g$是可计算的，
$h(a_0,…a_n,0)=f(a_0,…a_n)$是可计算的，
$h(a_0,…a_n,1)=g(a_0,…a_n,0,h(a_0,…a_n,0))$是可计算的
…
$h(a_0,…a_n,t+1)=g(a_0,…a_n,t,h(a_0,…a_n,t))$是可计算的
$h(a_0,…a_n,t+2)=g(a_0,…a_n,t+1,h(a_0,…a_n,t+1))$是可计算的
…
根据数学归纳法，
$h$是可计算的。
于是，我们根据复合规则和递归规则得到的总是可计算函数。从而所有的原始递归函数都是可计算的。
【实现】
我们就用Scheme来描述。
零函数z、后继函数s都很容易实现，
而投影函数p则是一堆函数，于是使用p函数来产生投影函数
两种函数产生规则可以看成是两个高阶函数，写起来并不复杂，毕竟这只是环境的基础，复杂的在后面
既然目的是为了写出开方，大致能想的出依次需要造出哪些函数，主方向上大致可以想到比如加法、比较、减法、乘法、乘方以及一些过程中的别的函数。
加法的定义可以这样：
$a+0=a$
$a+(n+1)=s(a+n)$
显然，这已经很像用递归规则可以写出的样子。
改一下上面的递推式，用符号$\oplus$来表示加法函数，
$add(a,0)=p_1^1(a)$
$add(a,n+1)=s(p_3^3(a,n,add(a,n)))$
为了区别+，我们在Scheme中用+~来表示加法，于是，很容易就写出代码
之后，我们Scheme里构造的函数都加上~来区别。
为了构造减法，我们想先构造一个后继函数的”相反”函数，前趋函数pre。
定义这个函数用在其他自然数上都是返回传入值减1，而对于0则返回0.
则定义如下：
$pre(0)=0$
$pre(n+1)=n$
这也很像用一次递归规则就可以完成的事，只可惜，无法构造出不带参数的函数，所以需要一个技巧，先构造一个带两元的函数。
$pre2(a,0)=0$
$pre2(a,n+1)=n$
那么也就是
$pre2(a,0)=z(a)$
$pre2(a,n+1)=p_3^2(a,n,pre2(a,n))$
再用pre2来通过复合规则构造pre函数。
有了前趋函数，就可以构造减法。递归论的减法有一点不一样，在于a-b在a
Original: https://www.cnblogs.com/Colin-Cai/p/9459940.html
Author: 窗户
Title: 原始递归函数及模拟运行的优化
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/801431/
转载文章受原作者版权保护。转载请注明原作者出处！