多重递归式

英文

multiple recursion schema

简介

原始递归式的一种等价形式.指具有多个递归变元的递归定义函数的模式.当递归变元个数为n时，称为n重递归式，简称n递归.以二重递归为例，首先考虑二元数对的字典排列次序≺，即〈x，y〉≺〈u，v〉指x<u或x=u & y<v.二重递归是关于次序≺进行递归定义，即在定义f于〈x，y〉处的值f(x，y)时，允许利用满足〈u，v〉≺〈x，y〉的〈u，v〉处的值f(u，v).以下是一种(带参数的)二重递归形式：

其中x～_i≤x_i，x^_i取值没有限制，而它们本身又可以是u，x₁，x₂的函数，并且不同的出现可以是不同的函数.若在x^_i表达式中仍含有新函数f的出现，则称为嵌套的二重递归，否则便是无嵌套的.例如，下列的阿克曼函数定义式便是一个嵌套的二重递归式：

对一般的n重递归式也有嵌套和无嵌套之分.若n重递归式是无嵌套的，则它可化归到原始递归式.而嵌套的多重递归式则不然.例如，上述函数A就不是原始递归的.一般地，彼得(Peter，R.)证明了n重递归式都可化归成正规n重递归式：

其中　f_i＝f(x₁+1，…，x_i-1+1，x_i，

　B⁽ⁱ⁾₁(x₁，x₂，…，x_n，f(x₁+1，…，x_n-1+1，x_n))，…，

　B⁽ⁱ⁾_n-i(x₁，x₂，…，x_n，f(x₁+1，…，x_n-1+1，x_n)))

(i=1，2，…，n)，　　

A，B均为已知函数.