一般递归函数

百科含义

一般递归函数(general recursive function)亦称递归函数，是指一类具有能行可计算的全数论函数。不仅如此，现在一般认为，能行可计算的全数论函数恰好就是一般递归函数，一般递归函数的概念最初是由美籍奥地利数学家哥德尔于1934年定义的，也就是现在所谓的埃尔布朗-哥德尔可计算函数，即若一个数论函数可由某个等式系ε定义，则哥德尔称f为一般递归的。1936年，美国逻辑学家、数学家克林(S.C.Kleene)引进了μ递归函数的概念，并进而证明了它恰好与哥德尔的一般递归函数类一致。此后，一般递归函数的概念便经常用μ递归的形式给出。莫绍揆于1965年利用一般递归式的概念提出了一般递归函数...