递归算子

一种从函数到函数的映射。从函数到函数的映射称为算子，一般说来，我们不能像计算函数那样计算一个算子．因为算子中的自变量(输入)和值(输出)都是函数，常是无穷对象，无法在有穷时间内完成输入和输出。但对某些算子(如一元算子φ：，其中是全体m元函数的类)，对φ(f)(x)(输出函数的函数值)的计算可以只用到输入f的有穷部分，并在有穷时间内完成。这样的算子就是可计算(递归)的。

对于有穷函数(即定义域是有穷集的函数)θ，可以通过一种能行的方法给它编号，比如说，可以定义

(其中P是第x个素数)，称为有穷函数θ的号码．利用这种编号，可以定义递归算子：

设Φ：，如果存在递归函数φ(z，x，…，x)使对任何f∈，y∈N，有

Φ(f)(x，…，x)=y当且仅当存在有穷函数θf使

则称Φ为递归算子。

此外，设Φ：，如果对任何f∈及任何x，…，x，y∈N

Φ(f)(x，…，x)=y 当且仅当存在有穷的θf使Φ(θ)(x，…，x)=y则称Φ为连续算子。

设Φ：，如果f，g∈且fg蕴涵Φ(f)Φ(g)，则称Φ为单调算子。

递归算子有如下基本性质：

定理1 递归算子都是连续的，也都是单调的。

定理2 算子Φ：是递归的，当且仅当

(a)Φ是连续的，

(b)由下式定义的函数φ(z，x，…，x)是递归函数：

类似地，也可以定义多元的递归算子Φ：，×…×·

递归算子可以用带神谕的图灵机(UR机)来计算，神谕的作用是由f∈产生(θf的号码)，然后转入递归函数φ(，x，…，x)的计算。

算子与泛函有一种自然的对应关系：若Φ：×…×是算子，则

是一泛函；反之，若F(x，…，x，f，…，f)是泛函，则

是一算子。(参见递归泛函)