Algorithms, theory of

The branch of mathematics dealing with the general properties of algorithms (cf. Algorithm). Preliminary notions about algorithms have played a role in mathematics throughout history. However, the concept of an algorithm itself was only formulated in the 20th century and became the object of independent study (at first only in its rather vaguely defined form) in the 1920s by the intuitionistic school of L.E.J. Brouwer and H. Weyl [1] (cf. Intuitionism). Systematic studies began in 1936, with the publication by A. Church [2] of the first formalization of the concept of a computable function (he suggested that the concept of an everywhere-defined computable function with natural arguments and natural values be identified with the concept of a general recursive function) and of the first example of a non-computable function. A.M. Turing [3], [4] and E.L. Post [5] gave the first formalizations of the concept of an algorithm (in terms of idealized computers, cf. Turing machine). Subsequent development of the theory of algorithms is due to the studies of Kleene, Post [6], [7], [8], A.A. Markov [9], [10], [11], and others. In particular, Markov rendered the concept of an algorithm more precise by the introduction of the concept of a normal algorithm [10]. A.N. Kolmogorov [12], [13] suggested the most general approach to the concept.

Since algorithms exclusively deal with the so-called constructive objects (cf. Constructive object), the ideas and methods of the theory of algorithms can be applied to non-constructive objects only if these are encoded, or re-named, as constructive objects. The study of the general properties of such encodings (mainly of situations in which such encodings, or names, are natural numbers) is the subject of the theory of enumeration [14], which is an important part of the theory of algorithms.

Fundamental concepts in the theory of algorithms.

The domain of applicability of an algorithm is the set of the objects to which it is applicable. It is said that an algorithm $ \mathfrak A $ 1) "computes a function f" if its domain coincides with the range of definition of $ f , $ and if $ \mathfrak A $ converts any $ x $ from its domain into $ f(x) $; 2) "solves a set A with respect to a set X" if it is applicable to any $ x $ from $ X $ and converts all $ x $ from $ X \cap A $ to the word "yes" , and all $ x $ from $ X \setminus A $ to the word "no" ; and 3) "counts (enumerates) a set B" if its domain is the sequence of natural numbers, and the set of results is $ B $. A function is called computable if an algorithm which evaluates the function exists. A set is said to be solvable with respect to $ X $ if there exists an algorithm which solves it with respect to $ X $. A set is said to be enumerable if it is empty or if there exists an algorithm enumerating it.

A detailed analysis of the concept of an algorithm reveals that: 1) the range of possible initial data and the range of applicability of an algorithm are enumerable sets. In turn, 2) for any pair of enumerable sets, one of which is included in the other, it is possible to find an algorithm in which the larger set is the range of possible inputs, while the smaller set is the range of outputs. The following basic theorems hold: 3) a function $ f $ is computable if and only if its graph, i.e. the set of all pairs of the form $ \langle x, f(x) \rangle $, is enumerable; 4) a subset $ A $ of an enumerable set $ X $ is solvable with respect to $ X $ if and only if $ A $ and $ X \setminus A $ are enumerable; 5) if $ A $ and $ B $ are enumerable, $ A \cup B $ and $ A \cap B $ are also enumerable; 6) in each infinite enumerable set $ X $ there exists an enumerable subset with a non-enumerable complement (in view of 4) this enumerable subset will not be solvable with respect to $ X $); and 7) for each infinite enumerable set $ X $ there exists a computable function, defined on a subset of this set, which cannot be extended to a computable function defined on all of $ X $. Statements 6) and 2) in combination yield an example (cf. Algorithm) of an algorithm with an unsolvable domain of applicability. Solvable and enumerable sets represent the simplest (and the most important) examples of sets, the structure of which is defined by certain algorithmic procedures. A systematic study of sets of constructive objects from the point of view of the properties of these sets as related to the availability of some of algorithms, constitutes the so-called algorithmic theory of sets; certain concepts, methods and results of this theory find analogues in descriptive set theory.

Algorithmic problems.

The problem of constructing an algorithm with certain given properties is known as the algorithmic problem. As a rule, the property of the algorithm which is sought is formulated in terms of the correspondence which should hold between the inputs and the results of the algorithm. Some important examples of algorithmic problems are: the problem of computing a given function (i.e. finding an algorithm which computes the function); the problem of solving a given set (i.e. finding an algorithm which solves this set with respect to some other set); and the problem of enumeration of a given set (i.e. to find an algorithm enumerating the given set). All the examples of algorithmic problems in various branches of mathematics, given in the section "Applications" below, are problems of solving. That an algorithmic problem is unsolvable means that there is no corresponding algorithm; theorems which establish the unsolvability of such problems belong to the most important theorems in the theory of algorithms. For instance, if an algorithm has an unsolvable domain, the algorithmic problem of solving this domain with respect to the set of all possible inputs is unsolvable. By reducing to this problem unsolvability, most other solvability problems were found to be unsolvable; this applies, in particular, to all the problems listed in the section "Applications" below. The question as to whether or not the unsolvability of any unsolvable problem can be established in this way, forms the so-called algorithmic reducibility problem.

The metric theory of algorithms.

The theory of algorithms comprises the descriptive (qualitative) and the metric (quantitative) theory. The former deals with algorithms from the point of view of the correspondence they establish between the initial data and the results; in particular, all algorithmic problems discussed in the preceding section belong to the qualitative theory. The latter studies algorithms from the point of view of the complexity both of the algorithms themselves (cf. Algorithm, complexity of description of an) and of the "computations" defined by the algorithms, i.e. the processes of successive transformations of constructive objects (cf. Algorithm, computational complexity of an). It is important to note that both the computational complexity of the algorithm and the complexity of description may be defined in various ways, and it may well be that $ A $ will turn out to be more complex than $ B $ when one definition is adopted, while $ B $ will turn out to be more complex than $ A $ according to another definition. In order to be able to speak about the complexity of algorithms, one must first specify some exact language in which the algorithms are to be written, and define the complexity of an algorithm as the complexity of its notation; the complexity of notation can in turn be determined in various ways (e.g. as the number of symbols of a given type which are included in the notation, or as a selection of such numbers computed for the various types of symbols). In order to speak about computational complexity, one must specify the exact form of the computation as a chain of constructive objects successively replacing each other, as well as some criterion of the complexity of such a chain — the number of "links" (or steps) in the chain alone or in combination with the "dimension" of the links, etc. In any event, the computational complexity will depend on the input with which the computation is begun; for this reason, the computational complexity is a function which assigns to each object within the domain of the algorithm the complexity of the corresponding chain. The development of the methods of evaluation of the complexity of algorithms and of computations has a high theoretical and practical importance; however, as distinct from the descriptive theory of algorithms, which has now crystallized into an integral mathematical discipline [11], [15], [16], the metric theory of algorithms is only in the process of being created [17], [18], [19], [20].

Applications of the theory of algorithms.

These are encountered in all branches of mathematics in which algorithmic problems are encountered. Such problems may arise in mathematical logic and in model theory; for each theory, the problem which arises is to solve the set of all true or demonstrable statements of this theory with respect to the set of all its statements (the theories divide into solvable or unsolvable theories, depending on the solvability or unsolvability of the problem in question). Church [21], [22] proved in 1936 that the problem of solving the set of all true assumptions of predicate logic was unsolvable; other important results on the subject are due to A. Tarski, A.I. Mal'tsev and to others [23]. Unsolvable algorithmic problems are encountered in algebra (the word (identity) problem for semi-groups and, in particular, for groups). The first examples of semi-groups with unsolvable word problem were found, independently of each other, by Markov [9] and by Post [8] in 1947, while an example of a group with unsolvable word problem was found by P.S. Novikov [24], [25] in 1952. Markov [26] in 1958 proved that the problem of homeomorphy in topology was unsolvable for an important class of cases. In number theory, Yu.V. Matiyasevich proved in 1970 that the problem of solvability of Diophantine equations was unsolvable [27], [28]. Similar examples can also be quoted from many other branches of mathematics.

The theory of algorithms is closely connected with mathematical logic, since the concept of an algorithm forms the base of one of the central concepts of mathematical logic — the concept of a calculus, as a result of which the Gödel incompleteness theorem of formal systems may be obtained from theorems of the theory of algorithms [29]. Finally, the theory of algorithms is closely connected with the foundations of mathematics, where one of the key problems is the relation between the constructive and the non-constructive. In particular, the theory of algorithms provides the apparatus for the development of the constructive direction in mathematics. It was suggested by Kolmogorov [30] in 1965 that the theory of algorithms be used as the foundation of information theory (cf. Algorithmic information theory). The theory of algorithms is the theoretical foundation for a number of problems in computational mathematics, and is closely related to cybernetics, in which an important subject is the study of control algorithms.

References

[1]	H. Weyl, "Philosophie der Mathematik und Naturwissenschaften" , Leibniz Verlag , München (1950)
[2]	A. Church, "An unsolvable problem of elementary number theory" Amer. J. Math. , 58 (1936) pp. 345–363
[3]	A.M. Turing, "On computable numbers, with an application to the Entscheidungsproblem" Proc. London Math. Soc. (2) , 42 (1937) pp. 230–265
[4]	A.M. Turing, "On computable numbers with an application to the Entscheidungsproblem, a correction" Proc. London Math. Soc. (2) , 43 (1937) pp. 544–546
[5]	E.L. Post, "Finite combinatory processes - formulation 1" J. Symbolic Logic , 1 : 3 (1936) pp. 103–105
[6]	E.L. Post, "Formal reductions of the general combinatorial decision problem" Amer. J. Math. , 65 (1943) pp. 197–215
[7]	E.L. Post, "Recursively enumerable sets of positive integers and their decision problems" Bull. Amer. Math. Soc. , 50 (1944) pp. 284–316
[8]	E.L. Post, "Recursive unsolvability of a problem of Thue" J. Symbolic Logic , 12 : 1 (1947) pp. 1–11
[9]	A.A. Markov, Dokl. Akad. Nauk SSSR , 55 : 7 (1947) pp. 587–590
[10]	A.A. Markov, "Theory of algorithms" Trudy Mat. Inst. Steklov. , 38 (1951) pp. 176–189 (In Russian)
[11]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[12]	A.N. Kolmogorov, "On the concept of an algorithm" Uspekhi Mat. Nauk , 8 : 4 (1953) pp. 175–176 (In Russian)
[13]	A.N. Kolmogorov, V.A. Uspenskii, "On the definition of an algorithm" Uspekhi Mat. Nauk , 13 : 4 (1958) pp. 3–28 (In Russian)
[14]	Yu.L. Ershov, "Theorie der Numierungen" , I-II , Deutsch. Verlag Wissenschaft. (1973–1976) (Translated from Russian)
[15]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[16]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)
[17]	A.A. Markov, "Normal algorithms connected with the computation of Boolean functions" Izv. Akad. Nauk SSSR Ser. Mat. , 31 (1967) pp. 161–208 (In Russian)
[18]	B.A. Trakhtenbrot, "Complexity of algorithms and calculations" , Novosibirsk (1967) (In Russian)
[19]	, Problems of mathematical logic. Complexity of algorithms and of classes of computable functions , Moscow (1970) (In Russian; translated from English)
[20]	, Complexity of computation of algorithms , Moscow (1974) (In Russian; translated from English) (Collection of translations)
[21]	A. Church, "A note on the Entscheidungsproblem" J. Symbolic Logic , 1 : 1 (1936) pp. 40–41
[22]	A. Church, "Correction to "a note on the Entscheidungsproblem" " J. Symbolic Logic , 1 : 3 (1936) pp. 101–102
[23]	Yu.L., et al. Ershov, "Elementary theories" Russian Math. Surveys , 20 : 4 (1965) pp. 35–105 Uspekhi Mat. Nauk , 20 : 4 (1965) pp. 37–108
[24]	P.S. Novikov, "On algorithmic unsolvability of the word problem" Dokl. Akad. Nauk SSSR , 85 : 4 (1952) pp. 709–712 (In Russian)
[25]	P.S. Novikov, "On algorithmic unsolvable problems of word identity in group theory" , Amer. Math. Soc. (1958) (Translated from Russian)
[26]	A.A. Markov, "Unsolvability of the homeomorphy problem" Dokl. Akad. Nauk SSSR , 121 : 2 (1958) pp. 218–220 (In Russian)
[27]	Yu.V. Matiyasevich, "The Diophantiness of enumerable sets" Dokl. Akad. Nauk SSSR , 191 : 2 (1970) pp. 279–282 (In Russian)
[28]	Yu.V. Matiyasevich, "Diophantine sets" Russian Math. Surveys , 27 : 5 (1972) pp. 124–164 Uspekhi Mat. Nauk , 27 : 5 (1972) pp. 185–222
[29]	V.A. Uspenskii, "An elementary exposition of Gödel's incompleteness theorem" Russian Math. Surveys , 29 : 1 (1974) pp. 63–106 Uspekhi Mat. Nauk , 29 : 1 (1974) pp. 3–47
[30]	A.N. Kolmogorov, "Three approaches to the definition of the concept of "quantity of information" " Probl. Peredachi Inform. , 1 : 1 (1965) pp. 3–11 (In Russian)

Comments

Since the above text was prepared also the theory of complexity of algorithms has matured into a well-developed branch of mathematics.

See also the comments to Algorithm, computational complexity of an.

In addition to [27], [28] one may consult [a1], [a2]. A thorough treatise on computational complexity is [a3].

References

[a1]	M. Davis, "Hilbert's tenth problem is unsolvable" Amer. Math. Monthly , 80 (1973) pp. 233–269
[a2]	J.V. Matijasevic, "A new proof of the theorem of exponential Diophantine representation of enumerable sets" J. Soviet Math. , 14 (1980) pp. 1475–1486
[a3]	K. Wagner, G. Wechsung, "Computational complexity" , Reidel (1986)