Namespaces
Variants
Actions

Difference between revisions of "Multiple recursion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653901.png" />-recursive functions there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653902.png" />-multiple universal function); cf. [[Universal function|Universal function]]. All possible forms of multiple recursion can be reduced to the following normal form:
+
<!--
 +
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.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653903.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653904.png" /></td> </tr></table>
+
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
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653905.png" /></td> </tr></table>
+
$$
 +
\phi _ {i}  = \phi ( n _ {1} + 1 \dots n _ {i-} 1 + 1 , n _ {i} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653906.png" /></td> </tr></table>
+
$$
 +
 +
\gamma _ {1}  ^ {(} i) ( n _ {1} \dots n _ {k} , \phi (
 +
n _ {1} + 1 \dots n _ {k-} 1 + 1 , n _ {k} )) \dots
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m065/m065390/m0653907.png" /></td> </tr></table>
+
$$
 +
\dots
 +
{}\gamma _ {k-} 1  ^ {(} i) ( n _ {1} \dots n _ {k} , \phi (
 +
n _ {1} + 1 \dots n _ {k-} 1 + 1 , n _ {k} ) ) ) .
 +
$$
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,  "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,  "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 08:02, 6 June 2020


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)

Comments

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

References

[a1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[a2] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
How to Cite This Entry:
Multiple recursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Multiple_recursion&oldid=47932
This article was adapted from an original article by N.V. Belyakin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article