Recursive Function

(redirected from Non-recursive)
Also found in: Dictionary.

Recursive Function

 

a term that has come to be applied to one of the most widely used variants of the precise definition of the general concept of an arithmetic algorithm. By an arithmetic algorithm we mean an algorithm such that the permissible input data are finite sequences of natural numbers and the possible results of its application are natural numbers. Recursive functions were introduced in the 1930’s by S. C. Kleene, whose work was based on investigations by such mathematicians as K. Gödel and J. Herbrand.

Every recursive function can be specified by a finite system of equations of a precisely defined type. In other words, the values of the function can be computed by means of this system of equations in accordance with precisely formulated rules. Moreover, the function can be specified in such a way that a particular type of algorithm for computing the values of the given recursive function results.

Arithmetic functions are said to be computable if there exist algorithms for the computation of their values. Computable functions play an important role in mathematics. It should be noted that if the concept of an algorithm is not given a precise definition, the concept of a computable function will also be somewhat vague. By the very nature of their definition, recursive functions are computable. The converse is in a certain sense also true; there are substantial reasons for regarding the concept of recursiveness, which by its nature is mathematical, to be the precise equivalent of the somewhat vague concept of computability. The proposal to identify the concept of comput-ability with the concept of recursiveness is known in the theory of recursive functions as Church’s thesis, after the American mathematician A. Church, who formulated this hypothesis and gave arguments for it in the 1930’s. The adoption of Church’s thesis permits a precise mathematical meaning to be assigned to the concept of a computable arithmetic function and allows the concept to be investigated by means of rigorous methods.

Recursive functions are partial functions—that is, functions that are not necessarily everywhere defined. In order to emphasize this fact, the term “partial recursive functions” is often used as a synonym. Recursive functions defined for all values of the arguments are called general recursive functions.

The definition of a recursive function can be given in the following form. One selects a small number of extremely simple initial functions that are computable in the above intuitive sense: a function identically equal to zero, a function whose value is one more than its argument, and functions that choose from finite sequences (a1 …, an) of natural numbers the term aj with a given index j. One selects a small number of operations on functions, transforming computable functions into computable functions: substitution, primitive recursion, and minimization. Recursive functions are then defined as functions that can be obtained from the initial functions by a finite number of applications of these operations.

The substitution operator associates with the function f of n variables and the functions g1,…, gn of m variables the function h of m variables such that, for any natural numbers x1,…, xm,

h(x1…,xmf (g1ǀ(x1,…,xm,…,gn(x1,…, xm)

(Here and below the conditional equality sign ≃ denotes that each of the two expressions connected by it is defined if and only if the other expression is and that, if the expressions are defined, they have the same value.)

The primitive recursion operator associates with the functions f of n variables and g of n + 2 variables the function h of n + 1 variables such that, for any natural numbers x1…..,xn,y,

h(x1,…,xn, 0) ≃ f(x1…, xn)

h(x1,…xn, y + 1) ≃ (x1,…,xn,y,h(x1,…,xn,y)

The minimization operator associates with the function f of n variables the function h of n variables such that, for any natural numbers x1,…,xn,

h(x1,…,xn) ≃ (x1,…,xn-1,y)

Here, y is such that f(x1,…,xn-1, 0),…,f(x1, …, xn-1, y - 1) are all defined and not equal to xn, whereas f(x1,…, xn-1, y) is defined and equal to xn.. If, however, no y with these properties exists, the value of h(x1 …, xn) is assumed to be undefined.

An important role in the theory of recursive functions is played by primitive recursive functions. A primitive recursive function is a recursive function obtained from the initial functions by a finite number of applications of only the substitution and primitive recursion operators. The primitive recursive functions form a proper subclass of the class of general recursive functions. By virtue of the well-known Kleene normal form theorem for recursive functions, particular primitive recursive functions U of one variable and Tn of n + 2 variables can be found such that, for any recursive function Φ of n variables and for any natural numbers x1, …, xn, the equation Φ(x1,…, xn) ≃ U(y) holds. Here, y is the least of the numbers z such that Tn (Φ, x1,…, xn, z) = 0, and Φ is the Gödel number of the function Φ—that is, a number that can be effectively constructed from the system of equations defining the function Φ. It follows from this theorem, in particular, that, for any recursive function of η variables, there can be constructed a universal recursive function of n + 1 variables—in other words, a recursive function Φn such that, for any recursive function Φ of n variables and for any natural numbers x1, …, xn, the following conditional equation holds:

Φ(x1,…,xn) ≃ Φn (Φ, x1,…,x2)

This is one of the key results of the general theory of recursive functions.

Although the theory of recursive functions is part of the theory of algorithms, it is itself a complex mathematical discipline with its own range of problems and with applications to other branches of mathematics. The concept of a recursive function can be made the basis of a constructive definition of the fundamental concepts of mathematics. The theory of recursive functions has found broad application in mathematical logic. In particular, the concept of a primitive recursive function was the basis for the first proof of Gödel’s famous incompleteness theorem for formal arithmetic. The concept of a recursive function was used, in its full sense, by S. C. Kleene to interpret intuition-istic arithmetic, an investigation that constitutes an entire epoch in the field of semantics. The theory of recursive functions is also made use of in the theory of computing machines and programming.

Studies have shown that all the known precise definitions of the general concept of an algorithm, including recursive functions, are equivalent to each other and, consequently, lead to the same concept of computable functions. This fact is a serious argument in favor of Church’s thesis.

REFERENCES

Kleene, S. C. Vvedenie ν metamalematiku. Moscow, 1957. (Translated from English.)
Uspenskii, V. A. Lektsii o vychislimykh funktsiiakh. Moscow, 1960.
Mal’tsev, A. I. Algoritmy irekursivnye funktsii. Moscow, 1965.
Rogers, H. Teoriia rekursivnykh funktsii i effektivnaia vychislimost’. Moscow, 1972. (Translated from English.)

N. M. NAGORNYI

References in periodicals archive ?
The receive QMFs shown in G.722 are two linear-phase non-recursive digital filters which interpolate the outputs, [r.sub.L] and [r.sub.H], of the lower and higher sub-band ADPCM decoders from 8 kHz to 16 kHz and which then produce an output, [x.sub.out], sampled at 16 kHz which forms the input to the receive audio parts.
where [b.sub.1], [b.sub.2], ..., [b.sub.n] are the coefficients of the non-recursive filter; q is order of the MA model, [x.sub.t] are the elements of the (input) and [[epsilon].sub.t] are the white noise errors.
void inOrder (BiTree bt) {/* Non-recursive preorder binary tree */ BiTree stack[Point],t; int top; if (bt==NULL) return; top=0; t=bt; while(!
In Alves & Vale's (2011) formula, only a Drafter/Reviser profile can be further classified using the Recursive or Non-Recursive subprofiles.
A distinction must be made, therefore, between simplex forms (no affix), non-recursive formations (one affix), recursive formations with non-recursive base (two affixes) and recursive formations with recursive base (three affixes).
McClellan, "Chebyshev approximation for non-recursive digital filters with linear phase", IEEE Trans.
Then, two types of operations have been described: non-recursive operations that take up slot-1, such as prefixation in (4a) and suffixation in (4b), and operations that require an extra slot, slot-II, because slot-1 is already occupied.
A base case is non-recursive and represents a final solution, terminating condition, or end of the process.
Within non-basic predicates, a further distinction has to be made between non-recursive predicates (those which undergo a single derivational process of affixation, compounding or zero-derivation), and recursive predicates (those which undergo a derivational process that puts an end to the derivation, i.e.
The first model is a simple non-recursive model, where people have a particular type (corrupt or not-corrupt) that lasts for the duration of their employment.
In addition, the new release offers the following features: the updated UserGate DNS module now supports MX, PTR and non-recursive requests; the remote UserGate server restart function has been added to the UserGate Administration console for connection to a remote UserGate server; the UserGate Statistics module is now able to export statistical reports in an OpenOffice Calc format; resource filtering and Internet access control is achieved through web categorisation and web-filtering techniques; and the program interface offers Unicode support.