通用函式

通用函式是遞歸證明中常用的一種函式。又稱為枚舉函式。通用函式定理亦稱枚舉定理。

基本介紹

• 中文名：通用函式
• 外文名：universal function
• 適用範圍：數理科學

通用函式定理

[universal function theorem]

通用函式定理亦稱枚舉定理。該定理指出：

存在一個函式列 滿足下列條件：

（1）對任何 e ，是 n 元部分遞歸函式；

（2）若為 n 元部分遞歸函式；

（3）存在 n+1 元部分遞歸函式，使得對任何

上述的函式被稱為 n 元部分遞歸函式的通用函式或枚舉函式(enumeration function)。

遞歸函式

最早由哥德爾於1934年提出，被稱為埃爾布朗-哥德爾函式。而教科書中給出的遞歸函式的定義通常是克林給出的μ遞歸函式的定義的全函式。全遞歸函式常常被稱為一般遞歸函式（general recursive function），而不一定是全的遞歸函式被稱為部分遞歸函式（partial ecursive function）。