Enumeration

A basic concept in the branch of the theory of algorithms called enumeration theory, which investigates general properties of classes of objects numbered by arbitrary constructive objects (cf. Constructive object). Most often, natural numbers appear in the role of the constructive objects that serve as numbers of the elements of the classes in question.

The idea of an enumeration of objects of a non-numerical nature (for example, logical formulas) by natural numbers and the transfer of meaningful assertions about these objects into the domain of the formal arithmetic of natural numbers was first used by K. Gödel in the proof of the Gödel incompleteness theorem of Peano arithmetic. Subsequently these ideas were used for the enumeration of fundamental objects in the theory of algorithms such as Turing machines, partial recursive functions and recursively-enumerable sets (cf. Turing machine; Partial recursive function). The assignment of suitable enumerations to these classes of objects made it possible in many cases to clarify more distinctly the nature of these objects and to make manifest a number of important new properties of them. Thus arose the idea of a systematic use of enumeration of arbitrary sets. In the realization of this idea it was noticed that many known results in the theory of algorithms turn out to be consequences of general regularities in enumeration theory. (About the structure of enumeration theory, the creation of its specific concepts and methods, and the formation of guiding principles in enumeration theory, see [1]–[4].) In particular, it was fruitful to use the language of category theory, which permitted one to look at problems in enumeration theory from a new point of view (see [4]).

An enumerated set is a pair , where is a countable set and is a mapping of the set of natural numbers onto . The mapping is called an enumeration of the set . If , then is called the number of the object in the enumeration . An enumeration of a set reduces to an enumeration of (the relation of reducibility of enumerations is denoted by ) if there is a one-place general recursive function such that for all . Two enumerations and of a set are called equivalent if and . From the point of view of enumeration theory equivalent enumerations of one and the same set are not distinguished. For this reason the object of study is usually the set of equivalence classes of enumerations of a set , partially ordered by the relation of reducibility of enumerations. Often one examines the set of equivalence classes of enumerations of that can be reduced to . In many cases and are a "measure of the complexity" of .

For the comparison of the enumerations of two sets and the basic concept is that of a morphism. A morphism of an enumerated set into an enumerated set is a mapping from into for which there is a one-place general recursive function such that for all . The set of all morphisms from to is denoted by . Many problems in the general theory of algorithms are closely connected with the study of the sets , in particular, with clarifying whether it is possible to impose "good" enumerations on this set.

The category of enumerated sets consists of enumerated sets and morphisms. The study of the properties of this category is the basic task of enumeration theory. Frequently, the starting point of such a study is the examination of connections between enumerated sets and the most important specific enumerations: the Kleene enumeration of all one-place partial recursive functions and the Post enumeration of all recursively-enumerable sets. In the theory of algorithms it is shown that there exists a two-place partial recursive function that is universal for the class of all one-place partial recursive functions, that is, is such that for any partial recursive function there is a number such that . The Kleene enumeration is then defined as follows: . If denotes the range of values of , then one obtains the Post enumeration of all recursively-enumerable sets.

A fundamental role in the study of is played by the concept of a complete enumeration, which was introduced by A.I. Mal'tsev and which, in its most general form, is a synthesis of the main features of the enumerations of Kleene and Post. An enumeration of a set is called complete if among the elements of there is a distinguished one, , such that for any one-place partial recursive function there is a one-place general recursive function such that

Complete enumerations play the role of "injective" objects in , and the possibility of having complete enumerations on indicates a considerable universality and importance of the class of objects . In particular, both the Kleene enumeration of partial recursive functions and the Post enumeration of recursively-enumerable sets are complete. (In the first case the distinguished element is a function that is nowhere defined, and in the second case it is the empty set.) An important trend in research on the category is also the selection and study of various kinds of subobjects of enumerated sets (see [4]).

The part of enumeration theory concerned with the study of the Kleene and Post enumerations and their subobjects has been well worked out, so that in these cases the use of the methods and the theory of algorithms is most effective. Here, one first studied the so-called computable enumerations. If is, e.g., a family of recursively-enumerable sets, then an enumeration of this family is said to be computable if the relation itself is recursively enumerable. The set of equivalence classes of computable enumerations of a family is denoted by . This set, like , is partially ordered by the reducibility relation . The maximal element of , if it exists, is called the principal computable enumeration of . In particular, the enumerations of Kleene and Post are principal computable for the families (of all one-place partial recursive functions) and (of all recursively-enumerable sets), respectively. A large amount of work in enumeration theory is devoted to the study of the sets and . Here it must be borne in mind that many properties of partial recursive functions and recursively-enumerable sets discovered in the theory of algorithms are in essence reflections of algebraic properties of and . For example, the so-called -step sets, which are studied in the theory of algorithms and play an important role there, fit easily into the scheme of enumeration theory. If one considers the family consisting of the two sets and only, then the -step sets are none other than , and the -step recursively-enumerable sets are . There is a complete algebraic description of the structure of and (see [4]).

Let be a family of recursively-enumerable sets (for partial recursive functions the concepts to be considered are introduced similarly). The indexing set (or enumerating set) of is the set

of numbers of recursively-enumerable sets of in the Post enumeration. In enumeration theory one studies indexing sets for various families . For example, the Rice–Shapiro theorem gives a description of those families for which the set is recursively enumerable. Such families are called, in enumeration theory, completely-enumerable classes. There are also descriptions of other forms of subobjects of the Post enumeration: special standard classes, factorizations and retracts. The so-called standard classes play an important role.

A family of recursively-enumerable sets is called a standard class if there exists a general recursive function such that ; if here , then . Standard classes are closely connected with complete enumerations. At present (1982) there is no satisfactory description of standard classes. Such a description could throw light on many problems in the theory of algorithms. In enumeration theory, principal, effectively principal and other kinds of subobjects of the Post enumeration have also been considered.

The algorithmic analogue of the concept of an algebraic system, that is, a set with functions and predicates given on it, is that of an indexed, or constructive, algebraic system. The idea is the following. An enumeration is imposed on the set in question. Instead of functions and predicates on the objects of one considers "translations" of these functions and predicates, operating in the appropriate manner on natural numbers as on the numbers of the objects of . If one can achieve that these "translations" of functions and predicates are general recursive, then one says that the given algebraic system is constructive. The first systematic study of the theory of constructive algebraic systems was undertaken by Mal'tsev [3].

Two brilliant applications of enumeration theory to problems in the theory of algorithms should be mentioned: the completion of the construction of Myhill's theory about universal objects, and the construction of a theory of computable functionals of finite types (see [4]). The methods and results of enumeration theory can be used in areas close to mathematical logic and the theory of algorithms, in particular in programming. Thus, by means of enumeration theory certain problems of the semantics of programming languages can be solved.

References

[1]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[2]	A.I. Mal'tsev, "Constructive algebras I" Russian Math. Surveys , 16 : 3 (1961) pp. 77–129 ((Also in: A.I. Mal'cev, The metamathematics of algebraic systems, North-Holland, 1971, Chapt. 18)) Uspekhi Mat. Nauk , 16 : 3 (1962) pp. 3–60
[3]	V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[4]	Yu.L. Ershov, "Theorie der Numierungen" , I-II , Deutsch. Verlag Wissenschaft. (1973–1976) (Translated from Russian)

References

[a1]	Yu.I. Manin, "A course in mathematical logic" , Springer (1977) (Translated from Russian)