递归泛函

在较早的文献(如1970年前的许多文献)中与近年的文献中，泛函的定义有所不同．

按早期文献的说法，泛函常指从N×到N的映射(N是自然数集，是全体一元自然数函数集)。设F(x，…，x，f，…，f)(其中x为自然数变元，f为函数变元)为一泛函，如果存在部分递归函数φ(u，x，…，x，y，…，y)使

F(x，…，x，f，…，f)=ω

当且仅当

u(φ(u，x，…，x，f(n)，…，f(n)=w)，

则称F为递归泛函。

说泛函F(x，…，x，f，…，f)是递归的，与说算子λx，…，xF(x，…，x，f，…，f)是递归算子是一回事(参见递归算子)。

在近年的文献中，常不限于N上的函数，但往往只考虑单调的映射。

设A是一无穷集合，NA，从An到N的全体部分函数的类记作ψ，从A×ψ×…×ψ到N的单调的部分映射称为(A上的)泛函。所谓单调映射是说：

如果fg…fg，

则F(x，…，x，f，…，f)=ωF(x，…，x，g，…，g)=ω．

由于这里定义的泛函都是单调的，所以它们所对应的算子也自然都是单调的。

设F：A×ψ×…×ψ→N是一泛函，称数组(n，k，…，k)为F的标记。

设F(x，…，x，f，g，…，g)是标记为(n，n，k，…k)的泛函，将g，…，g看作参变量，则F是关于x，…，x，f的泛函。利用相应的单调算子λx…xF(x，…，x，f)可以(超穷)归纳定义一个泛函序列：

令 F(，)=∪F(，)，F(，)称为由F(，f，)归纳定义的泛函。F(，)是关于f的不动点，它满足

以及，如果对每个都有FG，则λF(，λ′G(′，)，)λxG(，)。

设ψ是A上的一个泛函类，由ψ中的泛函F(x，…，x，f，)所定义的泛函F(，)称为不动点。

如果存在不动点F(，，)及k元自然数组=(n，…，n)使

则称泛函G为递归泛函。

设是泛函类。如果含有以下初始泛函(i)～(v)，并对规则(vi)～(x)封闭，则称之为合适的泛函类：

(i)N的特征函数

(ii)N上的恒同函数

(iii)后继函数

(iv)N上等词的特征函数

(v)赋值函数

(vi)附加变元规则：由F(，f)得到G：

(vii)复合规则：由F(a，，f)和G(，f)得到H：

(viii)分情况定义：从F(，f)和G(，f)得到H：

(ix)投影函数的代入：从F(y，…，y，f)得到G：

(是投影函数，参看原始递归函数)。

(x)泛函代入：从F(，g，…，g)和Z(，，)…，Z(，，)，得到G：

以ψ(A)表示A上泛函的最小合适类，以ψ表示ψ(N)，则：

部分函数f：D→N(DN)是ψ递归的，当且仅当f是部分递归函数。

递归函数的许多性质和结果都可推广到递归泛函上来，如范式定理，枚举定理，s-m-n定理，等等。