递归函数

---

函数的概念是一个很一般的概念。

在定义函数时，不一定要具体给出通过自变量求函数值的方法。因此，可将函数分成两类，一类是所谓能行可计算函数，另一类是非能行可计算的函数。这前一种函数无论在理论上或在实际上都是非常重要的，因此人们便试图给它们以精确的数学刻画。递归函数便是许多这种刻画中的一种。

我们以下考虑的函数都是从自然数到自然数的函数。

我们先定义几个初等函数

(1)零函数 Z(x)=0；

(2)后继函数 S(x)=x+1；

(3)广义函数；

显然，上面这些函数都是能行可计算的。

再介绍几个将函数变换为函数的算子。

(1)复合算子 设f是n元函数，g₁…g_n是m元函数，复合算子将f，g₁…g_n变换成为如下的m元函数h：

h(x₁…x_m)=f₁g₁(x₁，…x_m)，…g_n(x₁，…x_m))

(2)递归算子 设f是n元函数(≥0)，g是n+2元函数，递归算子将f，g变换成满足下列条件的n+1元函数h：

h(x₁，…，x_n，0)=f(x₁，…x_n)

h(x₁，…x_n，y+1)=g(x₁，…x_n，y，h(x₁，…x_n))

(3)μ－算子，设f是n+1元函数，如果存在y，使f(x₁，…x_n，y)=0，我们以μyf(x₁…x_ny)表示这样的y中的最小者，如果使f(x₁，…x_ny)=0的y不存在，我们说μyf(x₁，…x_ny)无定义。μ－算子将n+1元函数f变换成下面的几元函数h

h(x₁，…x_n)=μyf(x₁…x_ny)

注意，μ算子可以将一个全函数变换成一个部分函数(即在自然数的某个子集上有定义的函数)。

可以看出，上述所有算子都是将能行可计算函数变换为能行可计算函数。

所谓递归函数类便是包含零函数、广义么函数，并在复合算子、递归算子，μ－算子下封闲的最小函数类。

容易相信，任何递归函数都是能行可计算的。

反过来，是否存在直观上能行可计算的，但不是递归的函数呢?人们直到现在还没有发现这样的函数。相反，人们证明了，现已遇到的直观上能行可计算的函数都是递归函数。

进一步，人们还证明了，递归函数类与其他的一些刻画能行可计算函数的方法产生的函数类是完全一致的，这些事实促使车尔赤(Church)提出了他的著名的论点：

递归函数类与直观能行可计算函数类是重合的。

这个论点已被大多数递归论学者所接受。