遞歸函數（四）：全函數與計算的可終止性

遞歸函數（四）：全函數與計算的可終止性

來自專欄 業餘程序員的個人修養

回顧

上文我們討論了集合上的關係，還討論了數學歸納法的一種普遍形式，稱為良基歸納法，

它建立在集合上的良基關係之上。

本文開始討論函數，我們將回顧函數的定義，

然後解釋什麼是全函數（total function），什麼是部分函數（partial function）。

我們會看到，在證明一個遞歸函數是全函數時，

良基歸納法起到了重要作用。

在分析學中，人們似乎很少關心函數的完全性，

只關心它的連續性，可導性，可微性與可積性，等等。

而在計算機科學領域中，人們更在意計算的可終止性，

因此一個函數在某個點是否有定義將經常被提及。

程序中定義的函數，往往對應於某個集合上的數學函數，

為了描述程序的非終止性，就得擴充這個數學函數的定義域和值域。

為了理解這些事情，我們先要從函數的定義開始。

函數

集合 上的關係，是笛卡爾積 的一個子集。

而函數 ，則是集合 上的一種特殊關係，

它要求 中的每一個元素，都有 中唯一確定的元素與之對應。

其中，集合 稱為函數 的定義域，集合 稱為函數的值域。

函數是我們熟悉的概念，這裡只是提到了它本質上是集合上的一個關係。

（1）部分函數（partial function）

如果 是從 到 的二元關係，且 ， 或 ，

則稱 是從 到 的部分函數，或 上的部分函數。

其中，如果 ，則稱 有定義，記為 ，

也稱 為 在 點的函數值，記為 。

如果 ，則稱 無定義，記為 。

（2）全函數（total function）

如果 都有 ，則稱 是 上的全函數，

此時，可以記為 。

可見，我們熟悉的函數，指的是全函數。

值得注意的是，部分函數的定義已經包含了我們學過的「函數」的定義，

後文中，我們提到的「函數」如果不強調它的完全性的話，都泛指部分函數。

非終止性

部分函數在計算機科學中是非常重要的，

因為對於每一個 ，一個演算法可以表示為，計算出集合 中與之對應元素的過程，

這個演算法可能對於某些值 不會終止，而這種情況是很常見的。

例如：

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

這樣定義的函數f，對應了數學上的一個部分函數 ，它只在某些情況下有意義，

只有當n是奇數時，我們才能得到終止性的結果。

而當n是偶數時，演算法會無限的遞歸下去，直到堆棧溢出。

因此，將Int解釋為整數集 ，將f :: Int -> Int解釋為整數集上的函數，

似乎是有問題的，因為， 並不是一個整數，它的計算不能終止。

為了描述非終止性，就需要對整數集進行擴充，

我們給整數集加上一個特殊元素「 」，稱為bottom，來表示非終止性，

而將f :: Int -> Int解釋為集合 上的一個數學函數。

像這種通過構造表達程序含義的數學對象，來對程序進行分析的方法，來自指稱語義學。

指稱語義中，人們會區分函數的嚴格性，一個函數稱為嚴格的（strict），

如果接受一個非終止的輸入表達式，函數的計算仍然不會終止，即， 。

否則，稱函數為不嚴格的（non-strict）。

原始遞歸函數

我們看到在程序中使用遞歸，可能會導致非終止性的計算，而有些遞歸又不會。

這是為什麼呢？

我們可以從遞歸函數論中找到一些線索。

遞歸函數論是和圖靈機以及 演算相等價的計算模型，它從另一個角度刻畫了可計算性。

可計算性是一個有趣的話題，後續文章中，我們會詳細討論。

在遞歸函數論中，人們把函數劃分為了3個層次，

原始遞歸函數，遞歸函數，和其他的不能用遞歸函數表示的「函數」。

這些函數集合的範圍越來越大。

本文我們先介紹原始遞歸函數，

為此，我們需要先定義兩種運算。

（1）合成運算

設 是 元部分函數， 是 個 元部分函數，令，

則稱 是由 和 ，經過合成運算得到的。

（2）原始遞歸運算

設 是一個 元全函數， 是 元全函數，令，

則稱 是由 和 經過原始遞歸運算得到的。

於是，我們就可以定義原始遞歸函數了。

設初始函數包括，

（1）零函數

（2）後繼函數

（3）投影函數 ，

則由初始函數經過有限次合成運算和原始遞歸運算得到的函數，稱為原始遞歸函數。

原始遞歸函數有以下這些性質：

由原始遞歸函數經過合成或原始遞歸得到的函數仍為原始遞歸函數，

因此，原始遞歸函數的集合在合成與原始遞歸運算下是封閉的。

此外，每一個原始遞歸函數都是全函數。

這是因為合成運算雖然是在部分函數上定義的，

但是如果 和 是全函數，那麼 也一定是全函數。

另一方面，在進行原始遞歸運算時，如果 和 是全函數，則 也一定是全函數，

這是因為原始遞歸運算在 的參數集上的定義了一個良基關係，

由良基歸納法可證， 是全函數。

總結

本文介紹了全函數與部分函數，以及計算可終止性相關的概念，

我們對程序中函數的指稱，進行了定義域和值域的擴充，

隨後，我們進一步了解了原始遞歸函數，以及它的完全性，良基歸納法起到了關鍵作用。

下文，我們將深入到可計算性理論，

討論部分可計算函數和可計算函數的區別，討論遞歸函數與原始遞歸函數的關係，

引出遞歸可枚舉集這個重要的概念。

---

參考

function (mathematics)

strict function

可計算性與計算複雜性導引

---

下一篇：遞歸函數（五）：遞歸集與遞歸可枚舉集

推薦閱讀：