• • -

回顾

上文我们讨论了集合上的关系，还讨论了数学归纳法的一种普遍形式，称为良基归纳法，

它建立在集合上的良基关系之上。

本文开始讨论函数，我们将回顾函数的定义，

然后解释什么是全函数（total function），什么是部分函数（partial function）。

我们会看到，在证明一个递归函数是全函数时，

良基归纳法起到了重要作用。

在分析学中，人们似乎很少关心函数的完全性，

只关心它的连续性，可导性，可微性与可积性，等等。而在计算机科学领域中，人们更在意计算的可终止性，因此一个函数在某个点是否有定义将经常被提及。

程序中定义的函数，往往对应于某个集合上的数学函数，

为了描述程序的非终止性，就得扩充这个数学函数的定义域和值域。为了理解这些事情，我们先要从函数的定义开始。

函数

集合\(A,B\)上的关系，是笛卡尔积\(Atimes B\)的一个子集。

而函数\(f:Arightarrow B\)，则是集合\(A,B\)上的一种特殊关系，

它要求\(A\)中的每一个元素，都有\(B\)中唯一确定的元素与之对应。其中，集合\(A\)称为函数\(f\)的定义域，集合\(B\)称为函数的值域。

函数是我们熟悉的概念，这里只是提到了它本质上是集合上的一个关系。

（1）部分函数（partial function）

如果\(f\)是从\(A\)到\(B\)的二元关系，且\(forall ain A\)，\(f(a)=varnothing \)或\(lbrace brbrace \)，则称\(f\)是从\(A\)到\(B\)的部分函数，或\(A\)上的部分函数。

其中，如果\(f(a)=lbrace brbrace\)，则称\(f(a)\)有定义，记为\(f(a)downarrow \)，

也称\(b\)为\(f\)在\(a\)点的函数值，记为\(f(a)=b\)。如果\(f(a)=varnothing \)，则称\(f(a)\)无定义，记为\(f(a)uparrow \)。

（2）全函数（total function）

如果\(forall ain A\)都有\(f(a)downarrow \)，则称\(f\)是\(A\)上的全函数，此时，可以记为\(f:Arightarrow B\)。

可见，我们熟悉的函数，指是全函数。

值得注意的是，部分函数的定义已经包含了我们学过的“函数”的定义，后文中，我们提到的“函数”如果不强调它的完全性的话，都泛指部分函数。

非终止性

部分函数在计算机科学中是非常重要的，

因为对于每一个\(ain A\)，一个算法可以表示为，计算出集合\(B\)中与之对应元素的过程，这个算法可能对于某些值\(ain A\)不会终止，而这种情况是很常见的。

例如：

f :: Int -> Intf 1 = 1f n = n + f(n-2)

这样定义的函数f，对应了数学上的一个部分函数\(f\)，它只在某些情况下有意义，

只有当n是奇数时，我们才能得到终止性的结果。而当n是偶数时，算法会无限的递归下去，直到堆栈溢出。

因此，将Int解释为整数集\(N\)，将f :: Int -> Int解释为整数集上的函数，似乎是有问题的。

因为，\(f(2)\)并不是一个整数，它的计算不能终止。

为了描述非终止性，就需要对整数集进行扩充，

我们给整数集加上一个特殊元素“\(perp \)”，称为bottom，来表示非终止性，而将f :: Int -> Int解释为集合\(Ncup lbrace perp rbrace \)上一个的数学函数。

像这种通过构造表达程序含义的数学对象，来对程序进行分析的方法，来自。

指称语义中，人们会区分函数的严格性，一个函数称为严格的（strict），

如果接受一个非终止的输入表达式，函数的计算仍然不会终止，即，\(f(perp )=perp \)。否则，称函数为不严格的（non-strict）。

原始递归函数

我们看到在程序中使用递归，可能会导致非终止性的计算，而有些递归又不会。

这是为什么呢？

我们可以从递归函数论中找到一些线索。

递归函数论是和图灵机以及\(lambda \)演算相等价的计算模型，它从另一个角度刻画了可计算性。可计算性是一个有趣的话题，后续文章中，我们会详细讨论。

在递归函数论中，人们把函数划分为了3个层次，

原始递归函数，递归函数，和其他的不能用递归函数表示的“函数”。这些函数集合的范围越来越大。

本文我们先介绍原始递归函数，

为此，我们需要先定义两种运算。

（1）合成运算

设\(f\)是\(k\)元部分函数，\(g_1,g_2,cdots ,g_k\)是\(k\)个\(n\)元部分函数，令，\(h(x_1,cdots ,x_n)=f(g_1(x_1,cdots ,x_n),cdots ,g_k(x_1,cdots ,x_n))\)则称\(h\)是由\(f\)和\(g_1,g_2,cdots ,g_k\)，经过合成运算得到的。

（2）原始递归运算

设\(f\)是一个\(n\)元全函数，\(g\)是\(n+2\)元全函数，令，\(h(x_1,cdots ,x_n,0)=f(x_1,cdots ,x_n)\)\(h(x_1,cdots ,x_n,t+1)=g(t,h(x_1,cdots ,x_n,t),x_1,cdots ,x_n)\)则称\(h\)是由\(f\)和\(g\)经过原始递归运算得到的。

于是，我们就可以定义原始递归函数了。

设初始函数包括，

（1）零函数\(n(x)=0\)（2）后继函数\(s(x)=x+1\)（3）投影函数\(u^n_i(x_1,cdots ,x_n)=x_i\)，\(ileqslant ileqslant n\)则由初始函数经过有限次合成运算和原始递归运算得到的函数，称为原始递归函数。

原始递归函数有以下这些性质：

由原始递归函数经过合成或原始递归得到的函数仍为原始递归函数，因此，原始递归函数的集合在合成与原始递归运算下是封闭的。

此外，每一个原始递归函数都是全函数。

这是因为合成运算虽然是在部分函数上定义的，但是如果\(f\)和\(g_1,g_2,cdots ,g_k\)是全函数，那么\(h\)也一定是全函数。

另一方面，在进行原始递归运算时，如果\(f\)和\(g\)是全函数，则\(h\)也一定是全函数，

这是因为原始递归运算在\(h\)的参数集上的定义了一个良基关系，由良基归纳法可证，\(h\)是全函数。

总结

本文介绍了全函数与部分函数，以及计算可终止性相关的概念，

我们对程序中函数的指称，进行了定义域和值域的扩充，随后，我们进一步了解了原始递归函数，以及它的完全性，良基归纳法起到了关键作用。

下文，我们将深入到可计算性理论，

讨论部分可计算函数和可计算函数的区别，讨论递归函数与原始递归函数的关系，引出递归可枚举集这个重要的概念。

参考

)