View source for Multiple recursion

<!--
m0653901.png
$#A+1 = 7 n = 0
$#C+1 = 7 : ~/encyclopedia/old_files/data/M065/M.0605390 Multiple recursion
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A form of [[Recursion|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|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|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,   "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR></table>

====Comments====
It is more common to speak of simultaneous recursion, rather than multiple recursion; cf., e.g., [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.C. Kleene,   "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>