部分遞歸函數

部分遞歸函數是指由本原函數出發，經疊置、原始遞歸和μ算子作用生成的部分函數。等價地部分遞歸函數類可定義為以本原函數為開始函數、以一般遞歸算子reg為生成算子的遞歸生成函數類。一般地，在λ可定義函數、HG可定義函數、有窮可定義函數等的定義中允許出現函數，便可得到一般遞歸函數的一種等價定義。若依一般遞歸算子定義部分遞歸函數為例討論，則對任何一個部分遞歸函數φ，都有其導出過程：

。即

，並且對任何

，

或是本原函數，或是由某些

經代入或一般遞歸作用而得。這個序列也稱為φ的遞歸描述。從而，任何部分遞歸函數都有其遞歸描述。利用哥德爾編碼技巧，對任何遞歸描述都可進行能行編碼。相應地，全體部分遞歸函數也可能行編碼，由此可以給出全體部分遞歸函數的一種能行枚舉，通常以

表示全體n元部分遞歸函數的一種能行枚舉，e稱為

的下標，在元數不必明指的情形下，

常簡記為

。按丘奇論題，部分遞歸函數類恰好是全體能行可計算的部分(數論)函數類，其中的全函數恰好是全體遞歸函數(參見“丘奇論題”)，值得指出的是，部分遞歸函數類關於最小數算子是不封閉的 ^[1]  。

定義1 我們需要用到非受於“最小數”算子，或應用於函數的算子

。回憶一下，我們會把附加於謂詞“

”上的算子

稱為應用於函數

的算子

，我們常把“應用於函數”這句話省略掉，因為算子是被應用於謂詞或是“函數”(即看作應用於形如

的謂詞)，應用(非受於)算子

於函數的運算將簡稱為“

運算”。

定義2 如果一函數類：1° 包含函數

；2° 對代入運算、原始遞歸運算和

運算是封閉的；則稱這函數類為部分遞歸封閉類。

由原始遞歸封閉類的定義，可以把“部分遞歸封閉類”的概念表述成另一種形式：如果函數類是原始遞歸封閉的，且對

運算封閉，則稱之為部分遞歸封閉類。

這樣，我們從一切原始遞歸封閉類的簇中分出了對

運算封閉的類，並且把它們稱為部分遞歸封閉類。當然，一切函數的類是部分遞歸封閉的，原始遞歸函數類

不是部分遞歸封閉的，因為一般來説，

運算不保持函數的處處有定義性，而任何原始遞歸函數都是處處有定義的，但對我們來説，最重要的是：一切直觀可計算函數的類是部分遞歸封團的。

定義3最小的部分遞歸封閉類(即包含在任何部分遞歸封閉類中的部分遞歸封閉類)稱為部分遞歸函數類，而它的元素則相應地稱為部分遞歸函數。

部分遞歸函數類顯然與一切部分遞歸封閉類的交類重合，這交類部分遞歸封閉、非空(包合

)且包含在任何其他的部分遞歸封閉類之中。

函數串

稱為函數

的部分遞歸描述，如果

，且每個

或者1°是函數

中之一，或者2°是由該串中位於它前面的一些函數經使用代入，或原始遞歸運算，或μ運算而得到的 ^[2]  。

定理1一函數是部分遞歸函數的充要條件是：它有某個部分遞歸描述。換言之，一函數是部分遞歸函數的充要條件是：它能由函數

經有窮次使用代入、原始遞歸運算和

運算而得到 ^[2]  。

推論2部分遞歸函數集是可數集。

推論3每個原始遞歸函數都是部分遞歸的，推論2也可由下述事實推出：包含在任何原始遞歸封閉類中的原始遞歸函數類，也包含在部分遞歸函數類中。

推論4 一函數是部分遞歸函數的充要條件是：它能由原始遞歸函數經有窮次使用代入、原始遞歸運算和

運算而得到。

推論5 一函數是部分遞歸函數的充要條件是：它能由函數

和選揮自變元函數經有窮次使用正則代入、原始遞歸運算和

運算而得到。

部分遞歸函數不一定是處處有定義的，例如，甚至“處處無定義的”函數也可以是部分遞歸的。

可計算函數論的基本假設：任何

型可計算(在直觀的意義下)函數都是部分遞歸的。也可把可計算函數論的基本假設表述成下面的形式：部分遞歸函數的概念，是直觀意義下可計算函數這一概念的精確的數學之比 ^[2]  。