部分递归函数

部分递归函数(partial recursive function)是一般递归函数概念对部分函数的一种自然推广，它是具有能行可计算性的一类部分(数论)函数。部分递归函数概念最初是由美国逻辑学家、数学家克林(S.C.Kleene)于1936年引进的，是指由本原函数出发，经叠置、原始递归和μ算子作用生成的部分函数。等价地部分递归函数类可定义为以本原函数为开始函数、以一般递归算子reg为生成算子的递归生成函数类。部分递归函数是指由本原函数出发，经叠置、原始递归和μ算子作用生成的部分函数。等价地部分递归函数类可定义为以本原函数为开始函数、以一般递归算子reg为生成算子的递归生成函数类。一般地，在λ可定义函数、HG可定义函数、有穷可定义函数等的定义中允许出现函数，便可得到一般递归函数的一种等价定义。若依一般递归算子定义部分递归函数为例讨论，则对任何一个部分递归函数φ，都有其导出过程：。即，并且对任何，或是本原函数，或是由某些经代入或一般递归作用而得。这个序列也称为φ的递归描述。从而，任何部分递归函数都有其递归描述。利用哥德尔编码技巧，对任何递归描述都可进行能行编码。