一般递归函数

也称艾尔布朗－哥德尔－克利尼一般递归函数，是一种用等式系统定义函数的方法。所谓等式系统是一种其公式全为等式的形式系统，其组成如下：

形式语言

1．初始符号

　(1)可数无穷多个个体变元：x，y，z，…，

　(2)个体常元0，

　(3)一元函数常元S，

　(4)对每个n≥0，有可数无穷多个函数符号，依次记作

　………

　(5)等词=

　(6)辅助符号：括号、逗号。

2．项。

　(1)单独一个个体变元是项；

　(2)0是项；

　(3)若τ是项，则S(τ)是项；

　(4)若F是n元函数符号(n≥0)，τ，…，τ是项，则F(τ，…，τ)是项。

形如0，S(0)，S(S(0))…的项称数字，它们是自然数0，1，2，…的形式表达式，表示自然数a的数字记作ā

如果τ，…，τ是数字，F是n元函数符号，则项F(τ，…，τ)称为F项。

3．等式，如果τ，τ是项，则

τ=τ

是等式。

变形规则

1．项的代入：设τ是项，x是个体变元，τ是项，

τ｜x←τ

表示将τ中的x都代之以τ所得到的项。

2．对等式的代入

(1)SR规则：设τ，τ是项，x是个体变元，v是数字，此规则说：由等式

τ=τ

可得到等式

τ1｜x←v=τ｜x←v

(2)RR规则：设v是数字，Φ是F项，RR规则是说从等式

Φ=v

和等式

τ｜x←Φ=τ｜x←Φ

可得等式

τ｜x←v=τ｜x←v

形式推演。

给定有穷的等式集Φ，如果存在有穷的等式序列

ε，ε，…，ε

满足：对每个1≤k≤n，

ε∈Φ

或

ε是由某个ε(i＜k)经SR规则得到，

或

εk是由某两个ε，ε(i，j＜k)经RR规则得到，则称ε可由等式集Φ推出，记作

Φ┝ε。

一般递归函数就是可由某个等式组推出的函数。

设f(x，…，x)是一n元部分函数，如果存在一个有穷的等式组Φ和一个n元函数符号F，使得对任何自然数a，…，a，a，

f(a，…，a)=a当且仅当Φ┝F(ā，…，(ā)=ā

则称f是一般递归函数。

例如由等式组Φ：

F(x，0，)=0

F(x，S(x))=G(F(x，x)，x)

G(x，0)=x

G(x，S(x，))=S(G(x，x))

和二元函数符号F可以生成f(x，y)=xy，于是乘函数xy是一般递归函数。

一般递归函数与部分递归函数等价，也就是说：n元部分函数f是一般递归函数当且仅当f是部分递归函数。(参见部分递归函数，λ可定义函数)