通用函數

[universal function theorem]

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

存在一個函數列

滿足下列條件：

（1）對任何 e ，

是 n 元部分遞歸函數；

（2）若

為 n 元部分遞歸函數；

（3）存在 n+1 元部分遞歸函數

，使得對任何

上述的函數

被稱為 n 元部分遞歸函數的通用函數或枚舉函數(enumeration function)。 ^[1] 

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