View source for Primitive recursion

{{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

$$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|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====
<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>



====Comments====


====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>

[[Category:Logic and foundations]]