recursive function

Intuitively, a recursive function is a positive integer valued function of one or more positive integer arguments which may be computed by a definite algorithm.

Recursive functions may be defined more rigorously as the smallest class of partial functions from ${\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ satisfying the following six criteria:

1. The constant function $c:{\mathbb{Z}}_{+}\to {\mathbb{Z}}_{+}$ defined by $c(x)=1$ for all $x\in {\mathbb{Z}}_{+}$ is a recursive function.

2. The addition function $+:{\mathbb{Z}}_{+}^2\to {\mathbb{Z}}_{+}$ and the multiplication function $\times :{\mathbb{Z}}_{+}^2\to {\mathbb{Z}}_{+}$ are recursive function.

3. The projection functions $I_m^n:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ with $1\le m\le n$ defined as $I_m^n(x_1,\mathrm{\dots },x_n)=x_m$ are recursive functions.

4. (Closure under composition) If $f:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ is a recursive function and $g_i:{\mathbb{Z}}_{+}^m\to {\mathbb{Z}}_{+}$ with $i=1,\mathrm{\dots }n$ are recursive functions, then $h:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$, defined by $h(x_1,\mathrm{\dots },x_n)=f(g_1(x_1,\mathrm{\dots },x_m),\mathrm{\dots },g_n(x_1,\mathrm{\dots },x_m))$ is a recursive function.

5. (Closure under primitive recursion) If $f:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ and $g:{\mathbb{Z}}_{+}^{n+2}\to {\mathbb{Z}}_{+}$ are recursive function, then $h:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$, defined by the recursion

   $$h(n+1,x_1,\mathrm{\dots },x_k)=g(h(n,x_1,\mathrm{\dots },x_k),n,x_1,\mathrm{\dots },x_k)$$

   with the initial condition

   $$h(0,x_1,\mathrm{\dots },x_k)=f(x_1,\mathrm{\dots },x_k)$$

   is a recursive function.

6. (Closure under minimization) If $f:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$ is a recursive function then $g:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ is a recursive function, where

   • $g(x_1,\mathrm{\dots },x_n)$ is defined to be $y$, if there exists a $y\in {\mathbb{Z}}_{+}$ such that

     1. $f(0,x_1,\mathrm{\dots },x_n),f(1,x_1,\mathrm{\dots },x_n),\mathrm{\dots },f(y,x_1,\mathrm{\dots },x_n)$ are all defined,

     2. $f(z,x_1,\mathrm{\dots },x_n)\ne 0$ when , and

     3. $f(y,x_1,\mathrm{\dots },x_n)=0$.

   • $g(x_1,\mathrm{\dots },x_n)$ is undefined otherwise.

The operation whereby $h$ was constructed from $f$ and $g$ in criterion 5 is known as primitive recursion. The operation described in criterion 6 is known as minimization. That is to say, for any given function $f:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$, the partial function $g:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}_{+}$ constructed as in criterion 6 is known as the minimization of $f$ and is denoted by $g=\mu f$.

The smallest set of functions satisfying criteria 1-5, but not criterion 6, is known as the set of primitive recursive functions. Therefore, the set $ℛ$ of all recursive function is the closure of the set $𝒫ℛ$ of primitive recursive function with respect to minimization. It can be shown that $ℛ$ is exactly the set of Turing-computable functions. In terms of programming languages, a function is recursive iff it can be computed by a program involving the DO WHILE loops (minimization).

With some work, it can be shown that the class of recursive functions can be characterized by considerably weaker sets of criteria than those given above. See the entry “alternative characterizations of recursive functions (http://planetmath.org/AlternativeCharacterizationsOfRecursiveFunctions)” for several such characterizations.

Title	recursive function
Canonical name	RecursiveFunction
Date of creation	2013-03-22 14:34:35
Last modified on	2013-03-22 14:34:35
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	27
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 03D20
Synonym	unbounded minimization
Related topic	PrimitiveRecursive
Related topic	RecursiveFunctionIsURMComputable
Related topic	BoundedMinimization
Defines	primitive recursion
Defines	minimization