一般递归函数

一般递归函数

一般递归函数(general recursive function)亦称递归函数，是指一类具有能行可计算的全数论函数。不仅如此，现在一般认为，能行可计算的全数论函数恰好就是一般递归函数，一般递归函数的概念最初是由美籍奥地利数学家哥德尔于1934年定义的，也就是现在所谓的埃尔布朗-哥德尔可计算函数，即若一个数论函数可由某个等式系ε定义，则哥德尔称f为一般递归的。1936年，美国逻辑学家、数学家克林(S.C.Kleene)引进了μ递归函数的概念，并进而证明了它恰好与哥德尔的一般递归函数类一致。此后，一般递归函数的概念便经常用μ递归的形式给出。莫绍揆于1965年利用一般递归式的概念提出了一般递归函数的另一种等价定义形式：从本原函数出发，经叠置和一般递归式作用而生成的函数称为一般递归式。注意到，比起等式系或μ算子来，一般递归式更好地体现了一般递归的意义，因此，利用一般递归式引入一般递归函数概念当是最为合理的。而且也是原始递归函数概念的一种自然推广。此外，一般递归函数恰好是部分递归函数中的全函数，不过与全体部分递归函数不一样，全体一般递归函数不是能行可列的 。

想要了解更多“一般递归函数”的信息，请点击：一般递归函数百科