Recursive Function

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 (a₁ …, a_n) of natural numbers the term a_j 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 g₁,…, g_n of m variables the function h of m variables such that, for any natural numbers x₁,…, x_m,

h(x₁…,x_m ≃ f (g₁ǀ(x₁,…,x_m,…,g_n(x₁,…, x_m)

(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 x₁…..,x_n,y,

h(x₁,…,x_n, 0) ≃ f(x₁…, x_n)

h(x₁,…x_n, y + 1) ≃ (x₁,…,x_n,y,h(x₁,…,x_n,y)

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

h(x₁,…,x_n) ≃ (x₁,…,x_n-1,y)

Here, y is such that f(x₁,…,x_n-1, 0),…,f(x₁, …, x_n-1, y - 1) are all defined and not equal to x_n, whereas f(x₁,…, x_n-1, y) is defined and equal to x_n.. If, however, no y with these properties exists, the value of h(x₁ …, x_n) 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 T_n of n + 2 variables can be found such that, for any recursive function Φ of n variables and for any natural numbers x₁, …, x_n, the equation Φ(x₁,…, x_n) ≃ U(y) holds. Here, y is the least of the numbers z such that T_n (Φ, x₁,…, x_n, 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 x₁, …, x_n, the following conditional equation holds:

Φ(x₁,…,x_n) ≃ Φ_n (Φ, x₁,…,x₂)

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