# Multiple recursion

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A form of recursion using several variables simultaneously. The set of values of these variables is ordered lexicographically. This definition subsumes numerous concrete recursive descriptions. If in such a description the unknown function is not substituted into itself, then it results in a primitive recursion. In general, multiple recursion leads outside the limits of the set of primitive recursive functions, since by a double recursion (performed with respect to two variables) it is possible to construct a function which is universal for the primitive recursive functions (similarly, for $k$- recursive functions there is a $( k+ 1 )$- multiple universal function); cf. Universal function. All possible forms of multiple recursion can be reduced to the following normal form:

$$\phi ( n _ {1} \dots n _ {k} ) = 0 \ \textrm{ if } n _ {1} \dots n _ {k} = 0,$$

$$\phi ( n _ {1} + 1 \dots n _ {k} + 1 ) = \beta ( n _ {1} \dots n _ {k} , \phi _ {1} \dots \phi _ {k} ) ,$$

where

$$\phi _ {i} = \phi ( n _ {1} + 1 \dots n _ {i-} 1 + 1 , n _ {i} ,$$

$$\gamma _ {1} ^ {(} i) ( n _ {1} \dots n _ {k} , \phi ( n _ {1} + 1 \dots n _ {k-} 1 + 1 , n _ {k} )) \dots$$

$$\dots {}\gamma _ {k-} 1 ^ {(} i) ( n _ {1} \dots n _ {k} , \phi ( n _ {1} + 1 \dots n _ {k-} 1 + 1 , n _ {k} ) ) ) .$$

#### References

 [1] R. Peter, "Recursive functions" , Acad. Press (1967) (Translated from German)