標籤：

程序編碼遞歸論

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

04-21

回顧

上一篇中，我們通過引入極小化運算元定義了遞歸函數，

使用遞歸函數，我們又定義了遞歸集與遞歸可枚舉集，

本文我們要討論，為什麼遞歸可枚舉集是「可枚舉」的，以及什麼是可計算函數。

可計算性

我們聽說過，現代計算機在計算能力上是與圖靈機等價的，

什麼叫做計算能力呢？

它指的是圖靈機可計算的函數集，與現代計算機可計算的函數集是相等的。

為了簡單起見，我們不去討論圖靈機，而是從現代計算機直接說起，

設 $mathscr{P}$ 是一段程序， $n$ 是一個正整數，

我們稱數論函數 $psi (x_1,x_2,cdots ,x_n)$ 為程序 $mathscr{P}$ 所計算的 $n$ 元部分函數，

如果對於相同的輸入，

要麼：（1）程序 $mathscr{P}$ 的計算可以終止，此時計算結果等於 $psi (x_1,x_2,cdots ,x_n)$ 的相應函數值；

要麼：（2）程序 $mathscr{P}$ 的計算不能終止，此時 $psi (x_1,x_2,cdots ,x_n)$ 無定義。

設 $f(x_1,x_2,cdots ,x_n)$ 是一個部分函數，

如果存在程序 $mathscr{P}$ 可計算 $f$ ，則稱 $f$ 是部分可計算的。

如果一個函數，既是部分可計算的，又是全函數，則稱這個函數是可計算的。

可以證明，所有的原始遞歸函數和遞歸函數都是部分可計算的。

通用程序

我們使用現代計算機進行編程的時候，並不是直接把程序的輸入傳給程序，

而是將程序本身以及它的輸入，傳給計算機，最後由計算機得到計算結果，

像這種接受任何程序和它的輸入作為自己的輸入，返回程序執行結果的程序，稱為通用程序。

為此，通用程序需要把輸入的程序進行編碼。

常用的編碼方法，涉及配對函數和哥德爾編碼。

為了不引入太多的複雜性，我們可以將程序的編碼理解為存儲程序的二進位數據，

不同的程序會有不同的二進位表示，每一個二進位表示可以對應一段程序

（雖然可能不合法）。

哥德爾編碼做的事情就是將程序和自然數集一一對應起來。

因此，所有程序的個數是可數的，而這些程序可計算的函數個數也一定是可數的，

它們可能是全函數，也可能是部分函數。

（其中，「可數」指的是可數集，可數集是與自然數集之間存在一一映射的集合。

然而，自然數集上的函數全體並不可數，（證略

所以肯定存在程序不可計算的函數。

集合個數的可枚舉性

程序 $mathscr{P}$ 所計算的函數，我們可以記為 $psi (x_1,x_2,cdots ,x_n)$ ，

由此，我們可以定義通用程序 $Phi$ ，則有，

$Phi (x_1,x_2,cdots ,x_n,y)=psi (x_1,x_2,cdots ,x_n)$

其中， $y$ 是程序 $mathscr{P}$ 的編碼。

因為，所有的程序與自然數集一一對應，

所以， $Phi (x_1,x_2,cdots ,x_n,0),Phi (x_1,x_2,cdots ,x_n,1),cdots$ 枚舉了所有的 $n$ 元可計算函數。

我們定義 $W_y=lbrace xin N|Phi(x,y)downarrow brace$ ，

根據遞歸可枚舉集的定義，每一個 $W_y$ 是一個遞歸可枚舉集。

又因為 $Phi(x,0),Phi(x,1),cdots$ 枚舉了所有的可計算函數，

而上一篇中我們看到，遞歸可枚舉集是由部分遞歸函數（即，可計算函數）定義的，

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

所以， $W_0,W_1,cdots$ 枚舉了所有的遞歸可枚舉集。

因此，集合 $B$ 是遞歸可枚舉的，當且僅當存在 $yin N$ ，使得 $B=W_y$ ，

稱為枚舉定理，這就是「枚舉」的含義。

令 $K=lbrace nin N|nin W_n brace$ ，

則 $K$ 是遞歸可枚舉的，但不是遞歸的，（證略

因此， $ar{K}$ 不是遞歸可枚舉的，否則 $K$ 就是遞歸集了。

（根據，集合 $B$ 是遞歸的當且僅當 $B$ 和 $ar{B}$ 是遞歸可枚舉的，見上一篇

因此，我們找到了一個非遞歸的遞歸可枚舉集 $K$ ，

以及一個非遞歸可枚舉集 $ar{K}$ 。

停機問題

任給一個程序和一個自然數，問該程序對這個自然數輸入的計算是否停止，

這個問題稱為停機問題。

我們可以用謂詞 $H(x,y)$ 描述這個問題，

$H(x,y)$ ，表示以 $y$ 為代碼的程序對輸入 $x$ 的計算最終停止。

那麼， $H(x,y)$ 是不可計算的，即，不存在一個程序來計算 $H(x,y)$ 。

我們來證明一下，假設有一個程序可以計算 $H(x,y)$ ，

那麼我們就能用它來構造一個新程序 $mathscr{P}$ ，它的輸入是 $x$ ，

這段程序當 $H(x,x)$ 為真時，計算不停止，而當 $H(x,x)$ 為假時，計算停止。

程序 $mathscr{P}$ 也可以進行編碼，假設為 $y_0$ ，現在我們來判斷 $H(y_0,y_0)$ 。

如果 $H(y_0,y_0)$ 為真，意味著編碼為 $y_0$ 的程序以 $y_0$ 作為輸入最終停止，

即程序 $mathscr{P}$ ，輸入為 $y_0$ 時，最終停止，

可是根據 $mathscr{P}$ 的定義，此時 $H(x,x)=H(y_0,y_0)$ 為假才會停止，矛盾。

如果 $H(y_0,y_0)$ 為假，意味著編碼為 $y_0$ 的程序以 $y_0$ 作為參數最終不會停止，

即程序 $mathscr{P}$ ，輸入為 $y_0$ 時，最終不停止，

可是根據 $mathscr{P}$ 的定義，此時 $H(x,x)=H(y_0,y_0)$ 為真才不會停止，矛盾。

$H(y_0,y_0)$ 不能為真也不能為假，矛盾，

因此，計算 $H(x,y)$ 的程序不存在，我們也無法用它來構造程序 $mathscr{P}$ 。

可判定性

可判定性問題，指的是一個詢問真或者假的問題是否可以被回答。

如果我們總能回答出這個問題是真或者是假，就稱該問題是可判定的，

如果我們只能當問題為真的時候確定為真，為假的時候所進行的計算可能不會終止，

那麼就稱該問題是半可判定的。

某元素是否屬於一個遞歸集，是可判定的，

某元素是否屬於一個遞歸可枚舉集，是半可判定的。

因為，遞歸集是使用一個遞歸的全函數定義的，

而遞歸可枚舉集是使用第一個部分遞歸函數定義的，

我們無法判斷某個部分遞歸函數，在接受某參數時，是沒有定義，還是計算尚未停止。

即，判斷元素是否屬於某遞歸可枚舉集的程序可能永不停機。

總結

本文介紹了函數的可計算性，通用程序，以及最多有多少個程序，

還了解了停機問題和可判定性問題。

這些都是可計算性理論的基礎，我們清晰的看到了人類的計算能力，

以及用遞歸所能計算的函數範圍，後文中我們開始討論不動點理論，

這同樣是一個有趣的話題。

附

配對函數和哥德爾數，是對數偶和有窮數列的一種編碼方式。

（1）配對函數

令 $langle x,y angle=2^x(2y+1)-1$ ，稱 $langle x,y angle$ 為配對函數，它是一個原始遞歸函數。

任給一個數 $z$ ，存在唯一的一對數 $x$ 和 $y$ ，使得 $langle x,y angle =z$ 。

$x$ 是 $z+1$ 含有因子 $2$ 的個數，即使得 $2^t|(z+1)$ 的 $t$ 的最大值。

$(z+1)/2^x$ 必為奇數， $y$ 是 $2y+1=(z+1)/2^x$ 的唯一解。

一般的，記 $l(z)=x$ ， $r(z)=y$ ，則 $l(z)$ 和 $r(z)$ 也是原始遞歸函數。

（2）哥德爾數

記 $[a_1,a_2,cdots ,a_n]=prod_{i=1}^{n}p_i^{a_i}$ ，

$[a_1,a_2,cdots ,a_n]$ 稱為有窮數列 $(a_1,a_2,cdots ,a_n)$ 的哥德爾數，其中， $p_i$ 是第 $i$ 個素數。

例如，[ $[2,0,1,3]=2^2cdot 3^0cdot 5^1cdot 7^3=6860$ 。

對於每一個固定的 $n$ ， $[a_1,a_2,cdots ,a_n]$ 是原始遞歸函數，並且這種編碼具有唯一性。

參考

配對函數

哥德爾數

可數集

可判定性

康托爾定理

下一篇：遞歸函數（七）：不動點運算元

推薦閱讀：

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

TAG:編碼 | 程序 | 遞歸論 |