基本介紹
- 中文名：部分遞歸函式
- 外文名：partial recursive function
- 所屬學科：數學
- 所屬問題：數理邏輯(遞歸論)
概括介紹,相關定義,相關定理,
概括介紹
部分遞歸函式是指由本原函式出發，經疊置、原始遞歸和μ運算元作用生成的部分函式。等價地部分遞歸函式類可定義為以本原函式為開始函式、以一般遞歸運算元reg為生成運算元的遞歸生成函式類。一般地，在λ可定義函式、HG可定義函式、有窮可定義函式等的定義中允許出現函式，便可得到一般遞歸函式的一種等價定義。若依一般遞歸運算元定義部分遞歸函式為例討論，則對任何一個部分遞歸函式φ，都有其導出過程：
。即
，並且對任何
，
或是本原函式，或是由某些
經代入或一般遞歸作用而得。這個序列也稱為φ的遞歸描述。從而，任何部分遞歸函式都有其遞歸描述。利用哥德爾編碼技巧，對任何遞歸描述都可進行能行編碼。相應地，全體部分遞歸函式也可能行編碼，由此可以給出全體部分遞歸函式的一種能行枚舉，通常以
表示全體n元部分遞歸函式的一種能行枚舉，e稱為
的下標，在元數不必明指的情形下，
常簡記為
。按丘奇論題，部分遞歸函式類恰好是全體能行可計算的部分(數論)函式類，其中的全函式恰好是全體遞歸函式(參見“丘奇論題”)，值得指出的是，部分遞歸函式類關於最小數運算元是不封閉的。
相關定義
定義1 我們需要用到非受於“最小數”運算元，或套用於函式的運算元
。回憶一下，我們會把附加於謂詞“
”上的運算元
稱為套用於函式
的運算元
，我們常把“套用於函式”這句話省略掉，因為運算元是被套用於謂詞或是“函式”(即看作套用於形如的謂詞)，套用(非受於)運算元
於函式的運算將簡稱為“
運算”。
定義2 如果一函式類：1° 包含函式
；2° 對代入運算、原始遞歸運算和運算是封閉的；則稱這函式類為部分遞歸封閉類。
由原始遞歸封閉類的定義，可以把“部分遞歸封閉類”的概念表述成另一種形式：如果函式類是原始遞歸封閉的，且對
運算封閉，則稱之為部分遞歸封閉類。
這樣，我們從一切原始遞歸封閉類的簇中分出了對
運算封閉的類，並且把它們稱為部分遞歸封閉類。當然，一切函式的類是部分遞歸封閉的，原始遞歸函式類
不是部分遞歸封閉的，因為一般來說，
運算不保持函式的處處有定義性，而任何原始遞歸函式都是處處有定義的，但對我們來說，最重要的是：一切直觀可計算函式的類是部分遞歸封團的。
定義3最小的部分遞歸封閉類(即包含在任何部分遞歸封閉類中的部分遞歸封閉類)稱為部分遞歸函式類，而它的元素則相應地稱為部分遞歸函式。
部分遞歸函式類顯然與一切部分遞歸封閉類的交類重合，這交類部分遞歸封閉、非空(包合)且包含在任何其他的部分遞歸封閉類之中。
函式串
稱為函式
的部分遞歸描述，如果
，且每個
或者1°是函式中之一，或者2°是由該串中位於它前面的一些函式經使用代入，或原始遞歸運算，或μ運算而得到的。
相關定理
定理1一函式是部分遞歸函式的充要條件是：它有某個部分遞歸描述。換言之，一函式是部分遞歸函式的充要條件是：它能由函式經有窮次使用代入、原始遞歸運算和
運算而得到。
推論2部分遞歸函式集是可數集。
推論3每個原始遞歸函式都是部分遞歸的，推論2也可由下述事實推出：包含在任何原始遞歸封閉類中的原始遞歸函式類，也包含在部分遞歸函式類中。
推論4 一函式是部分遞歸函式的充要條件是：它能由原始遞歸函式經有窮次使用代入、原始遞歸運算和
運算而得到。
推論5 一函式是部分遞歸函式的充要條件是：它能由函式和選揮自變元函式經有窮次使用正則代入、原始遞歸運算和
運算而得到。
部分遞歸函式不一定是處處有定義的，例如，甚至“處處無定義的”函式也可以是部分遞歸的。
可計算函式論的基本假設：任何
型可計算(在直觀的意義下)函式都是部分遞歸的。也可把可計算函式論的基本假設表述成下面的形式：部分遞歸函式的概念，是直觀意義下可計算函式這一概念的精確的數學之比。
