# Enumerable Function

## Enumerable Function

one of the basic concepts of the theory of algorithms. Function f is called enumerable if there exists an algorithm that transforms any object x, for which there exists a function f, into the object f(x) and that is not applicable to any other x for which f is not defined. Examples: x is a natural number, f(x) = x2; x is a pair of rational numbers x1 and x2, f(x) = x1: x2 (this function is defined only for those x in which x2 ≠ 0); X is a pair of matrices X1 and X2 with whole-number elements, f(X) = X1X2 (this function is defined only for those X in which the number of columns in X1 coincides with the number of lines in X2). Only so-called constructive objects can be arguments and values of an enumerable function (for algorithms can only operate with such objects). Thus, function f is such that f(x)≡x is not enumerable if it is examined on the whole real straight line, but it is enumerable if it is seen as the function of a natural or rational argument. An enumerable function whose domain of definition is a natural series is called an enumerable sequence.

V. A. USPENSKII

Site: Follow: Share:
Open / Close