PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
recursive function (Definition)

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. (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_n) = f(g_1(x_1, \ldots, x_m), \ldots, g_n(x_1, \ldots, x_m))$ is a recursive function.
  5. (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
    $\displaystyle h(n+1,x_1,\ldots,x_{k}) = g(h(n,x_1,\ldots,x_k),n,x_1,\ldots, x_k)$
    with the initial condition
    $\displaystyle h(0,x_1,\ldots,x_k) = f(x_1,\ldots,x_k)$
    is a recursive function.
  6. (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
    • $ 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,
    • $ f(z, x_1, \ldots, x_n) = 0$ when $ 1 \le z <y$, and
    • $ 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$ 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\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.



"recursive function" is owned by rspuzio. [ full author list (3) ]
(view preamble)

View style:

Also defines:  primitive recursive function, primitive recursion

Attachments:
alternative characterizations of recursive functions (Topic) by rspuzio

Cross-references: characterizations, weaker, operation, initial condition, composition, closure, projection, constant function, partial functions, class, arguments, function, integer, positive
There are 11 references to this entry.

This is version 18 of recursive function, born on 2004-09-04, modified 2006-11-09.
Object id is 6135, canonical name is RecursiveFunction.
Accessed 6028 times total.

Classification:
AMS MSC03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies)

Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy
Arabic maths by pahio on 2004-09-06 09:06:54

Hi all who know the Arabic mathematics! I am curious to know, how in Arabic mathematical texts the mathematical expressions and formulae are written (among other text which goes from right to left)? Are they written from left to right as in European and Chinese languages?

Jussi
[ reply | up ]

Interact
rate | post | correct | update request | add derivation | add example | add (any)