递归函数的哲学意义及其演进历史

Recursive Function:Philosophical Significance and Evolution History

递归函数的根本特征在于其逐步计算和分解计算,即通过某函数带入到(返回,即"递归")自身或另一个函数的变量来求解被带入函数。这个定义是历史上逐步定型化的,其定型的过程始终保持了其这一原始意义,但其函数的形式是逐步严格化的,其类型是逐步扩大的。当前,普遍地接受的"递归函数"即指哥德尔于1934年定义的"广义递归函数(一般递归函数)",包括μ-递归函数、阿克曼递归函数以及在逻辑上可能出现的其他递归函数;广义递归函数在外延上与下列概念具有逻辑等值意义:递归函数、能行可计算函数、λ-可定义函数、图灵可计算函数——这些函数都是广义递归函数的不同侧面的反映。

The eigenvalues of recursive function lie in step-by-step and decomposed calculations, or the solution of a certain function through the variables. The definition has been fixed gradually over time, preserving its original meaning. Nevertheless, the forms of function have gradually become rigid while its types have been increased. At present the generally accepted “recursive function” refers to the “general recursive function” defined by Kurt Godel in 1934, including μ recursive function, Wilhelm Ackermann’s recursive function, and other possible recursive functions in logic. General recursive function is equivalent with the following concepts in denotation, namely, recursive function; effectively computable function, λ definable function, and Turing calculable function, which reflect the former in different ways. Key words：