通用函數

[universal function theorem]

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

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

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

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

（3）存在 元部分遞歸函數，使得對任何

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

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