Namespaces
Variants
Actions

Difference between revisions of "Primitive recursion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: better)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A means of defining functions with natural number arguments and values. One says that an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746001.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746002.png" /> is obtained by primitive recursion from an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746003.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746004.png" /> and an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746005.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746006.png" /> if for all natural number values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p0746007.png" /> one has
+
{{TEX|done}}
 +
A means of defining functions with natural number arguments and values. One says that an $(n+1)$-place function $f(x_1,\dots,x_n,y)$ is obtained by primitive recursion from an $n$-place function $g(x_1,\dots,x_n)$ and an $(n+2)$-place function $h(x_1,\dots,x_n,y,z)$ if for all natural number values of $x_1,\dots,x_n,y$ one has
  
<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/p/p074/p074600/p0746008.png" /></td> </tr></table>
+
$$f(x_1,\dots,x_n,0)=g(x_1,\dots,x_n)$$
  
 
and
 
and
  
<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/p/p074/p074600/p0746009.png" /></td> </tr></table>
+
$$f(x_1,\dots,x_n,y+1)=h(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)).$$
  
For given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460011.png" /> such a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460012.png" /> exists always and is unique. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460013.png" /> the defining equations for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460014.png" /> can be written as
+
For given $g$ and $h$ such a function $f$ exists always and is unique. For $n=0$ the defining equations for $f$ can be written as
  
<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/p/p074/p074600/p07460015.png" /></td> </tr></table>
+
$$f(0)=a,\quad f(x+1)=h(x,f(x)).$$
  
A fundamental property of primitive recursion is that for any meaningful specification of the notion of computability, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460016.png" /> obtained from computable functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074600/p07460018.png" /> by means of primitive recursion is itself computable (cf. [[Computable function|Computable function]]). Primitive recursion is one of the basic ways for generating all primitive recursive and all partial recursive functions from an initial set of basic functions (cf. [[Primitive recursive function|Primitive recursive function]]; [[Partial recursive function|Partial recursive function]]).
+
A fundamental property of primitive recursion is that for any meaningful specification of the notion of computability, a function $f$ obtained from computable functions $g$ and $h$ by means of primitive recursion is itself computable (cf. [[Computable function|Computable function]]). Primitive recursion is one of the basic ways for generating all primitive recursive and all partial recursive functions from an initial set of basic functions (cf. [[Primitive recursive function|Primitive recursive function]]; [[Partial recursive function|Partial recursive function]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR>
 +
</table>
  
  
Line 22: Line 27:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Calude,  "Theories of computational complexity" , North-Holland  (1988)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1959)  pp. Chapts. IX; XI, §54</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. Chapt. II; esp. pp. 199ff</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Calude,  "Theories of computational complexity" , North-Holland  (1988)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1959)  pp. Chapts. IX; XI, §54</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. Chapt. II; esp. pp. 199ff</TD></TR>
 +
</table>
 +
 
 +
[[Category:Logic and foundations]]

Latest revision as of 21:13, 2 November 2014

A means of defining functions with natural number arguments and values. One says that an $(n+1)$-place function $f(x_1,\dots,x_n,y)$ is obtained by primitive recursion from an $n$-place function $g(x_1,\dots,x_n)$ and an $(n+2)$-place function $h(x_1,\dots,x_n,y,z)$ if for all natural number values of $x_1,\dots,x_n,y$ one has

$$f(x_1,\dots,x_n,0)=g(x_1,\dots,x_n)$$

and

$$f(x_1,\dots,x_n,y+1)=h(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)).$$

For given $g$ and $h$ such a function $f$ exists always and is unique. For $n=0$ the defining equations for $f$ can be written as

$$f(0)=a,\quad f(x+1)=h(x,f(x)).$$

A fundamental property of primitive recursion is that for any meaningful specification of the notion of computability, a function $f$ obtained from computable functions $g$ and $h$ by means of primitive recursion is itself computable (cf. Computable function). Primitive recursion is one of the basic ways for generating all primitive recursive and all partial recursive functions from an initial set of basic functions (cf. Primitive recursive function; Partial recursive function).

References

[1] V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[2] A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[3] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165


Comments

References

[a1] C. Calude, "Theories of computational complexity" , North-Holland (1988)
[a2] Yu.I. Manin, "A course in mathematical logic" , Springer (1977) (Translated from Russian)
[a3] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1959) pp. Chapts. IX; XI, §54
[a4] P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. Chapt. II; esp. pp. 199ff
How to Cite This Entry:
Primitive recursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Primitive_recursion&oldid=17879
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article