|
|
|
Viewing Version
9
of
'recursive function'
|
[ view 'recursive function'
|
back to history
]
| Title of object: |
recursive function |
| Canonical Name: |
RecursiveFunction |
| Type: |
Definition |
| Created on: |
2004-09-04 03:47:58 |
| Modified on: |
2004-09-06 13:52:43 |
| Classification: |
msc:03D20 |
| Defines: |
recursive function, primitive recursive function, primitive recursion |
Revision comment (for changes between this and next version):
| Changes for correction #6093 ('quote marks should look like ``this'''). |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
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 largest 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^n_m \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ with $1 \le m \le n$ defined as $I^n_m (x_1, \ldots x_n) = x_m$ are recursive functions.
4) {\it (Closure under composition)} If $f \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ is a recursive function and $g_i \colon \mathbb{Z}_+^m \to \mathbb{Z}_+$ with $i = 1, \ldots n$ are recursive functions, then $h \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$, defined by $h(x_1, \ldots x_m) = f(g_1(x_1, \ldots x_m), \ldots g_n(x_1, \ldots x_m))$ is a recursive function.
5) {\it (Closure under primitive recursion)}If $f \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ and $g \colon \mathbb{Z}_+^{n+2} \to \mathbb{Z}_+$ are recursive function, then $h \colon \mathbb{Z}_+^{n+1} \to \mathbb{Z}_+$, defined by the recursion
$$h(n+1,x_1,...,x_{k}) = g(h(n,x_1,...,x_k),n,x_1,..., x_k)$$
with the initial condition
$$h(0,x_1,...,x_k) = f(x_1,...,x_k)$$
is a recursive function.
6) {\it (Closure under minimization)} If $f \colon \mathbb{Z}_+^{n+1} \to \mathbb{Z}_+$ is a recursive function then $g \colon \mathbb{Z}_+^n \to \mathbb{Z}_+$ is a recursive function, where $g$ is defined to equal $y$ if there exists a $y \in \mathbb{Z}_+$ such that a) $f(0, x_1, \ldots x_n), f(1, x_1, \ldots x_n), \ldots f(y, x_1, \ldots x_n)$ are all defined, b) $f(z, x_1, \ldots x_n) = 0$ when $1 \le z <y$, and c) $f(y, x_1, \ldots x_n) = 0$, otherwise $g(x_1, \ldots x_n)$ is undefined.
The operation whereby $h$ was constructed from $f$ ang $g$ in criterion 6 is known as primitive recursion. The operation described in criterion 6 is known as minimization. That is to say, for any given function $f\colon \mathbb{Z}_+^{n+1} \to \mathbb{Z}_+$, the partial function $g \colon \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.
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" for several such characterizations. |
|
|
|
|
|
