標籤：

函數遞歸論

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

04-16

回顧

上文中我們討論了全函數和部分函數，以及計算的可終止性。

本文我們從數論函數開始，給原始遞歸函數集增加一種新的運算，得到了一個更大的集合。

然後根據遞歸函數，我們可以定義遞歸集和遞歸可枚舉集，

為以後討論可計算性與可判定性打好基礎。

數論函數

自然數集一般記為 $N=lbrace 0,1,2,cdots brace$ ，那麼 $n$ 個自然數集的笛卡爾積記為 $N^n$ ，

於是，我們稱集合 $N^n$ 到 $N$ 的部分函數為 $n$ 元部分數論函數。

作為數論函數， $2x$ 是一個全函數，而 $x/2$ ， $x-y$ ， $sqrt{x}$ 只是部分函數，

它們的計算結果， $3/2$ ， $4-6$ ， $sqrt{5}$ 都不在 $N$ 中，

於是相應定義域中的點可視為沒有定義。

為什麼討論數論函數呢，其一是因為它是一個典型數學的問題，

另外一點，則是因為我們經常把其他數學問題轉換成數論問題，例如，哥德爾編碼。

本文中，使用數論函數，可以簡化我們的描述方式。

一個謂詞，指的是返回布爾值的函數，

我們還可以將謂詞看做值域為 $lbrace 0,1 brace$ 的一個數論函數。

$0$ 代表True， $1$ 代表False。

極小化運算元

在前一篇中，我們從三個初始函數出發，

通過合成運算和原始遞歸運算，得到了原始遞歸函數集，

遞歸函數集是相對於這兩種運算封閉的。

然而，這樣定義的原始遞歸函數，並不能包括所有的數論函數，

一個典型的例子就是，阿克曼函數，

ackermann :: Int -> Int -> Int ackermann 0 x = x+1ackermann k 0 = ackermann (k-1) 1ackermann k x = ackermann (k-1) $ ackermann k x-1

它並不是一個原始遞歸函數，（證略

因此原始遞歸函數集並不足以表示計算機程序中的所有函數。

為此，我們需要對原始遞歸函數集進行擴充，我們定義一個新的運算，稱為極小化運算，

設 $P(x_1,cdots ,x_n,t)$ 是一個謂詞，令 $f(x_1,cdots ,x_n)=min P(x_1,cdots ,x_n,t)$ 。

$f(x_1,cdots ,x_n)$ 的值，或者是使 $P(x_1,cdots ,x_n,t)$ 為真的最小 $t$ 值，

或者無定義，此時不存在 $t$ 使得 $P(x_1,cdots ,x_n,t)$ 為真。

這樣通過 $min$ 得到 $f(x_1,cdots ,x_n)$ 的過程稱為極小化運算，

也稱部分函數 $f(x_1,cdots ,x_n)$ 是由謂詞經過極小化運算得到的。

以上我們給謂詞定義了極小化運算，現在我們將極小化運算推廣到一般的函數上面，

設 $g(x_1,cdots ,x_n,t)$ 是一個 $n+1$ 元函數，令

$f(x_1,cdots ,x_n)=minlbrace g(x_1,cdots ,x_n,t)=0 brace$

則稱部分函數 $f(x_1,cdots ,x_n)$ 是由函數 $g(x_1,cdots ,x_n,t)$ 經過極小化運算得到的。

遞歸函數集

和定義原始遞歸函數集一樣，我們從以下三個初始函數出發，

（1）零函數 $n(x)=0$

（2）後繼函數 $s(x)=x+1$

（3）投影函數 $u^n_i(x_1,cdots ,x_n)=x_i$ ， $1leqslant ileqslant n$

由初始函數，經過有限次合成運算，原始遞歸運算，以及極小化運算，

得到的函數稱為遞歸函數。

遞歸函數並不一定是全函數，因為極小化運算可能會導致結果函數在某些點無定義，

遞歸的部分函數稱為部分遞歸函數。

可以證明阿克曼函數是遞歸函數，但不是原始遞歸函數，

因此，原始遞歸函數集是遞歸函數集的真子集。

遞歸可枚舉集

在具體實踐中，我們經常會遇到這樣的問題，

給定一個元素，我們需要判斷這個元素是否屬於某個集合。

這種問題，稱為集合的成員資格問題。

沿用這一思路，我們可以使用一個謂詞 $chi _B$ 來定義相應的集合 $Bsubseteq N$ ，

$B=lbrace xin N|chi _B(x) brace$

謂詞 $chi _B(x)$ 為真，則 $xin B$ 。

這個謂詞 $chi _B(x)$ ，通常稱為集合 $B$ 的特徵函數。

如果特徵函數 $chi _B$ 是一個遞歸的全函數，

則我們總是可以判斷 $chi _B(x)$ 等於 $0$ 還是 $1$ ，

這樣的集合 $B$ 稱為遞歸集。

如果存在部分遞歸函數 $g$ ，使得 $B=lbrace xin N|g(x)downarrow brace$ ，

即， $xin B$ 當且僅當 $g$ 在 $x$ 處有定義，

則稱集合 $B$ 是一個遞歸可枚舉集。

每一個部分遞歸函數，都確定出一個遞歸可枚舉集。

因此，對於每一個自然數 $xin N$ ，

我們總是可以通過遞歸集 $B$ 的特徵函數 $chi _B$ ，來判斷 $x$ 是否 $B$ 的成員。

而對於遞歸可枚舉集，就不容樂觀了，

如果某個自然數 $xin N$ 是 $B$ 的成員，那麼我們可以斷定這件事，因為 $g(x)$ 有定義，

但是如果某個自然數 $yin N$ 不是 $B$ 的成員，我們就不能確定，因為這時候 $g(x)$ 無定義。

（ $g(x)$ 無定義，則它對應的圖靈機不停機，後文我們詳細討論

因此，集合 $B$ 是遞歸的當且僅當 $B$ 和 $ar{B}$ 是遞歸可枚舉的，

其中 $ar{B}$ 為 $B$ 的補集。

總結

本文介紹了數論函數，遞歸函數集，然後用遞歸函數分別定義了遞歸集和遞歸可枚舉集，

可是為什麼遞歸可枚舉集是「可枚舉」的呢？

是因為每一個遞歸可枚舉集可以一一對應一個自然數，這是怎樣做到的呢？

這需要我們理解總共有多少個可能的程序，以及什麼是通用程序。

參考

遞歸集

遞歸可枚舉集

下一篇：遞歸函數（六）：最多有多少個程序

推薦閱讀：

TAG:函數 | 遞歸論 |