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) = x²; x is a pair of rational numbers x₁ and x₂, f(x) = x₁: x² (this function is defined only for those x in which x₂ ≠ 0); X is a pair of matrices X₁ and X₂ with whole-number elements, f(X) = X₁X₂ (this function is defined only for those X in which the number of columns in X₁ coincides with the number of lines in X₂). 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