更新时间：2022-09-23 09:35
部分递归函数(partial recursive function)是一般递归函数概念对部分函数的一种自然推广，它是具有能行可计算性的一类部分(数论)函数。部分递归函数概念最初是由美国逻辑学家、数学家克林(S.C.Kleene)于1936年引进的，是指由本原函数出发，经叠置、原始递归和μ算子作用生成的部分函数。等价地部分递归函数类可定义为以本原函数为开始函数、以一般递归算子reg为生成算子的递归生成函数类。
部分递归函数是指由本原函数出发，经叠置、原始递归和μ算子作用生成的部分函数。等价地部分递归函数类可定义为以本原函数为开始函数、以一般递归算子reg为生成算子的递归生成函数类。一般地，在λ可定义函数、HG可定义函数、有穷可定义函数等的定义中允许出现函数，便可得到一般递归函数的一种等价定义。若依一般递归算子定义部分递归函数为例讨论，则对任何一个部分递归函数φ，都有其导出过程：。即，并且对任何，或是本原函数，或是由某些经代入或一般递归作用而得。这个序列也称为φ的递归描述。从而，任何部分递归函数都有其递归描述。利用哥德尔编码技巧，对任何递归描述都可进行能行编码。相应地，全体部分递归函数也可能行编码，由此可以给出全体部分递归函数的一种能行枚举，通常以表示全体n元部分递归函数的一种能行枚举，e称为的下标，在元数不必明指的情形下，常简记为。按丘奇论题，部分递归函数类恰好是全体能行可计算的部分(数论)函数类，其中的全函数恰好是全体递归函数(参见“丘奇论题”)，值得指出的是，部分递归函数类关于最小数算子是不封闭的。
定义1 我们需要用到非受于“最小数”算子，或应用于函数的算子。回忆一下，我们会把附加于谓词“”上的算子称为应用于函数的算子，我们常把“应用于函数”这句话省略掉，因为算子是被应用于谓词或是“函数”(即看作应用于形如的谓词)，应用(非受于)算子于函数的运算将简称为“运算”。
定义2 如果一函数类：1° 包含函数；2° 对代入运算、原始递归运算和运算是封闭的；则称这函数类为部分递归封闭类。
由原始递归封闭类的定义，可以把“部分递归封闭类”的概念表述成另一种形式：如果函数类是原始递归封闭的，且对运算封闭，则称之为部分递归封闭类。
这样，我们从一切原始递归封闭类的簇中分出了对运算封闭的类，并且把它们称为部分递归封闭类。当然，一切函数的类是部分递归封闭的，原始递归函数类不是部分递归封闭的，因为一般来说，运算不保持函数的处处有定义性，而任何原始递归函数都是处处有定义的，但对我们来说，最重要的是：一切直观可计算函数的类是部分递归封团的。
定义3最小的部分递归封闭类(即包含在任何部分递归封闭类中的部分递归封闭类)称为部分递归函数类，而它的元素则相应地称为部分递归函数。
部分递归函数类显然与一切部分递归封闭类的交类重合，这交类部分递归封闭、非空(包合)且包含在任何其他的部分递归封闭类之中。
函数串称为函数的部分递归描述，如果，且每个或者1°是函数中之一，或者2°是由该串中位于它前面的一些函数经使用代入，或原始递归运算，或μ运算而得到的。
定理1一函数是部分递归函数的充要条件是：它有某个部分递归描述。换言之，一函数是部分递归函数的充要条件是：它能由函数经有穷次使用代入、原始递归运算和运算而得到。
推论2部分递归函数集是可数集。
推论3每个原始递归函数都是部分递归的，推论2也可由下述事实推出：包含在任何原始递归封闭类中的原始递归函数类，也包含在部分递归函数类中。
推论4 一函数是部分递归函数的充要条件是：它能由原始递归函数经有穷次使用代入、原始递归运算和运算而得到。
推论5 一函数是部分递归函数的充要条件是：它能由函数和选挥自变元函数经有穷次使用正则代入、原始递归运算和运算而得到。
部分递归函数不一定是处处有定义的，例如，甚至“处处无定义的”函数也可以是部分递归的。
可计算函数论的基本假设：任何型可计算(在直观的意义下)函数都是部分递归的。也可把可计算函数论的基本假设表述成下面的形式：部分递归函数的概念，是直观意义下可计算函数这一概念的精确的数学之比。