Algorithmic problem

The problem of finding a (unique) method (an algorithm) to solve an infinite series of individual problems of the same type. Algorithmic problems arose and were solved in various branches of mathematics throughout its history; however, some of them could not be solved for a long time. The reason for this only became apparent in the 1930s, when an exact definition of an algorithm was given in mathematical logic. It was found that algorithmic problems can be unsolvable, i.e. that the algorithm sought need not exist at all. As a result, the approach to algorithms on the part of mathematicians underwent a radical change, and new algorithmic problems began to be formulated as problems of existence of an algorithm for the solution of a given infinite series of problems of a given type, and of finding such an algorithm if it exists.

Several more exact definitions of algorithm appeared in the theory of algorithms (cf. Algorithms, theory of) practically all at the same time, and they all proved to be essentially equivalent. In each such definition a sufficiently broad class of specific algorithms, closed with respect to the natural operation of combination of algorithms, is singled out. Each statement to the effect that some algorithmic problem is unsolvable is a precise and proved mathematical theorem on the unsolvability of the algorithmic problem under consideration by an algorithm of the given class. In this form these theorems may be regarded as specific, i.e. related to a given class of algorithms. However, all results of this kind may be expressed in terms of the intuitive idea of an algorithm as understood by all mathematicians. This "translation" is based on the so-called Church thesis (depending on the exact specification of the given algorithm, it may also be called Turing's thesis or the normalization principle), which says that the class of algorithms under consideration is universal, i.e. that the essential function of any intuitive algorithm may be performed by algorithms of this class. This thesis is a scientific fact confirmed by the history of mathematics: all algorithms known in mathematics satisfy it and all attempts to construct algorithms not satisfying it have failed. Finally, the thesis is also confirmed by the equivalence of the various proposed definitions of algorithm. Church' thesis cannot be proved, since it deals with the mathematically vague concept of an intuitive algorithm, but it is highly important nevertheless, since it makes it possible to speak of unsolvability of given algorithms in a wide sense, which is generally understood by mathematicians.

The first examples of unsolvable algorithmic problems were noted in the theory of algorithms itself. These include the problem of recognition of belonging to a given non-recursive set of natural numbers, the halting problem of a universal Turing machine, the problem of the recognition of self-applicability of a normal algorithm, etc.

As concerns algorithmic problems outside the theory of algorithms itself, one must mention, first of all, the problem of recognition of validity of formulas of first-order predicate calculus, the unsolvability of which was first proved by A. Church in 1936. Numerous studies of algorithmic problems in model theory are related to these results. Model theory, which deals with non-empty sets with relations defined on them using predicate calculus, was created in the 1930s by A.I. Mal'tsev and A. Tarski. They must also be credited with exact formulations of many algorithmic problems in model theory and with several fundamental results in this field. The elementary theory of a given class $ K $ of models is the set of all closed formulas of first-order predicate calculus that are true for all models of $ K $. The class $ K $ may consist of one model. An elementary theory $ T $ is solvable or unsolvable, depending on whether or not an algorithm for the recognition of whether or not any given formula belongs to the theory $ T $ exists. For a partial review of the methods of studying algorithmic problems in model theory and the results obtained, see [3]. The problem of the solvability of the elementary theory of free groups is the most interesting one mentioned in [3], and one which has not yet (1977) been solved.

Numerous and varied algorithmic problems also arise during the constructive interpretation of various branches of mathematics. The principal results concerning algorithmic problems in traditional branches of mathematics are given below.

A naturally arising question remained open for a long time: Are unsolvable algorithmic problems specific to the theory of algorithms and mathematical logic? In other words, do there exist unsolvable algorithmic problems in traditional branches of mathematics far removed from mathematical logic? The first result of this kind was obtained in 1949 and 1947 by A.A. Markov and E.L. Post, independently of one another. They proved that the problem of equality (identity) of words for semi-groups — posed by A. Thue as early as 1914 — was unsolvable. In this problem one considers semi-groups defined by a finite number of generators (an alphabet)

$$ \tag{1 } a _ {1} \dots a _ {n} $$

and defining relations

$$ \tag{2 } A _ {i} = B _ {i} ,\ i = 1 \dots k . $$

An elementary transformation of the semi-group $ \Pi $ here considered is a transition from the word $ P A _ {i} Q $ to the word $ P B _ {i} Q $ or vice versa, where $ P $ and $ Q $ are arbitrary words in the alphabet (1). Two words $ X $ and $ Y $ in the alphabet (1) are said to be equivalent in $ \Pi $ if they coincide, or if one can be obtained from the other through a finite sequence of elementary transformations. The set of all equivalence classes with a multiplication operation which is naturally defined by the operation of concatenation of words is just the semi-group $ \Pi $ defined by the generators (1) and relations (2). The problem of word equality (identity) (the word problem) in the semi-group $ \Pi $ consists in finding an algorithm for recognizing if any pair of words $ X $ and $ Y $ of $ \Pi $ are equivalent in $ \Pi $ or not, i.e. if the elements of $ \Pi $ defined by them are identical or not. Markov and Post constructed specific semi-groups for which there is no algorithm for solving the equality problem [1].

The most noteworthy result in this context was obtained by P.S. Novikov [4], [5]. He showed that the classical word problem in group theory (the equality or identity of words problem) posed by M. Dehn in 1912, which was studied by many experts in algebra throughout the world, was unsolvable. It may be formulated in the same way as the word problem for semi-groups, except that only such systems of relations (2) are considered for which inverse elements for all generators (1) exist in the given semi-group. Novikov also showed that the isomorphism problem, which is very important in group theory — to wit, how to find an algorithm to tell whether or not any two groups are isomorphic — is unsolvable. It was subsequently shown that for any given group $ G $ it is impossible to find an algorithm that would tell whether or not an arbitrary group is isomorphic to $ G $[6].

Markov studied the problem of recognition of invariant properties of semi-groups, i.e. of properties that are preserved on passing to isomorphic semi-groups [2]. He showed that if for an invariant semi-group property $ \alpha $ there exists a semi-group with property $ \alpha $ and another semi-group which is not imbeddable in any semi-group with this property, then there is no algorithm by which it is possible to tell whether a given semi-group has the property $ \alpha $ or not. This actually means that almost-all invariant semi-group properties are algorithmically unrecognizable in the class of semi-groups. An analogue of this fundamental theorem has also been obtained in group theory [7], [8], [9]. In particular, the conclusion in this case is as follows. Let $ K _ \alpha $ be the class of all groups with an invariant property $ \alpha $. Two algorithmic problems are related to each such class: the word problem for groups from $ K _ \alpha $, and the problem of recognizing whether or not an arbitrary group belongs to $ K _ \alpha $. It was found that for any non-empty class $ K _ \alpha $ at least one of these algorithmic problems is unsolvable. The same applies to semi-groups as well.

Another problem studied was the specification of the simplest groups and semi-groups in which the word problem is unsolvable. Of the numerous studies on this subject one may mention the proof of the unsolvability of the word problem for the semi-group specified by the following seven simple defining relations [10]:

$$ ac = ca ,\ ad = da ,\ bc = cb ,\ bd = db , $$

$$ eca = ce ,\ edb = de ,\ cca = ccae . $$

At a later date [11] an example was given of a semi-group with three defining relations and an unsolvable equality problem. No algorithm for solving the word problem in the general case has yet (1977) been found, not even for semi-groups with a single defining relation; it was only constructed for irreducible defining relations [12]. The algorithm solving the word problem for groups with one defining relation dates a long time back [13], but even for two such relations the question still remains open. The minimum number of defining relations for which examples of groups with unsolvable word problem are known is 12. The problem of word equality for commutative semi-groups has been shown to be solvable. For commutative groups the isomorphism problem has been solved as well. The problem of word equality is solvable for finite groups, for finitely-defined simple groups, for nilpotent groups and for solvable groups of the second order. However, even in the class of solvable groups of the fifth order one can indicate a group given by a corresponding identity of the fifth order and a finite number of defining relations with unsolvable word problem [15].

The study of the word problem for groups with a limited measure of overlap of the defining words, i.e. with overlap of the left-hand sides of the defining relations, had begun before the unsolvability of the word problem in its general form was demonstrated. The strongest result on this subject at the time of writing (1977) is the proof of the solvability of the word problem in the class of groups defined by systems of defining relations in which the defining words may overlap by less than 1/5 of their length [14]. If the overlap between the words may be as large as 1/3 of their length, an example of a group with unsolvable word problem becomes quite simple. In the range between 1/5 and 1/3 the problem remains open. Similar studies were also conducted for semi-groups. It was found that for semi-groups with maximum measure of overlap of the defining words less than 1/2 the word problem is solvable, but examples are known of semi-groups with an unsolvable word problem in which the maximum overlap of the defining words is 1/2.

The most prominent topological algorithmic problem is the classical decision problem for homeomorphism of $ n $- dimensional manifolds. Markov constructed an example of a four-dimensional manifold $ \mathfrak M $ for which it is impossible to construct an algorithm to tell whether or not an arbitrary four-dimensional manifold is homeomorphic to $ \mathfrak M $[17]. It is known that for $ n = 2 $ the solution of this problem is positive; for $ n = 3 $ the problem remains open; for four-dimensional and higher-dimensional manifolds the problems of recognition of combinatorial and homotopy equivalence of manifolds are also unsolvable. One may also mention that if $ P $ is a polyhedron for which the word identity problem of its fundamental group is unsolvable, no algorithm can be constructed for $ P $ that recognizes the bounded homotopy (or the free homotopy) of two arbitrary paths on $ P $ passing through a common point. A positive solution was obtained for the problem of conjugation in braid groups; this problem is equivalent to the topological problem of recognizing the equivalence of braids [16].

One of the most famous algorithmic problems in mathematics is Hilbert's 10th problem: To find an algorithm by which to tell whether or not a system of Diophantine equations with integer coefficients has a solution in integers. After many examples of unsolvable algorithmic problems had become known, it was suggested that this problem was unsolvable as well. Moreover, a team of American mathematicians succeeded in proving that the unsolvability of Hilbert's tenth problem follows from the existence of a two-place Diophantine predicate of exponential growth [18], [19]. However, they were unsuccessful in constructing such a predicate; they merely demonstrated that the recognition of the existence of integer solutions of exponential equations was an unsolvable problem. The desired Diophantine predicate of exponential growth was first constructed in 1970 [20], [21]; this was the first proof ever given of the unsolvability of Hilbert's tenth problem.

In the theory of algorithms the existence of unsolvable algorithmic problems of various degrees of unsolvability was proved. Many studies of algorithmic problems arising in mathematics showed that each such problem had, in the general case, a maximum degree of unsolvability, while their special instances (e.g. the word identity problem in specific semi-groups or groups) may have any pre-given degree of unsolvability.

References

[1]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[2]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[3]	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
[4]	P.S. Novikov, Dokl. Akad. Nauk SSSR , 85 : 4 (1952) pp. 709–712
[5]	P.S. Novikov, "On algorithmical unsolvability of the word problem" Trudy Mat. Inst. Akad. Nauk SSSR , 44 (1955) (In Russian)
[6]	S.I. Adyan, "Unsolvability of some algorithmic problems in group theory" Trudy Moskov. Mat. Obshch. , 6 (1957) pp. 231–298 (In Russian)
[7]	S.I. Adyan, "Finitely defined groups and automorphisms" Dokl. Akad. Nauk SSSR , 117 : 1 (1957) pp. 9–12 (In Russian)
[8]	S.I. Adyan, "On algorithmic problems in effectively complete classes of groups" Dokl. Akad. Nauk SSSR , 123 : 1 (1958) pp. 13–16 (In Russian)
[9]	M.O. Rabin, "Recursive unsolvability of group theoretic problems" Ann. of Math. (2) , 67 : 1 (1958) pp. 172–194
[10]	G.S. Tseitin, "An associative calculus with unsolvable equivalence problem" Trudy Mat. Inst. Steklov. , 52 (1958) pp. 172–189 (In Russian)
[11]	Yu.V. Matiyasevich, "Simple examples of undecidable associative calculi" Soviet Math. Dokl. , 8 : 2 (1967) pp. 555–557 Dokl. Akad. Nauk SSSR , 173 : 6 (1967) pp. 1264–1266
[12]	S.I. [S.I. Adyan] Adjan, "Defining relations and algorithmic problems for groups and semigroups" Proc. Steklov Inst. Math. , 85 (1967) Trudy Mat. Inst. Steklov. , 85 (1966)
[13]	W. Magnus, Uspekhi Mat. Nauk , 8 (1941) pp. 365–376
[14]	R.C. Lyndon, "On Dehn's algorithm" Math. Ann. , 166 (1966) pp. 208–228
[15]	V.N. Remeslennikov, "Example of a finitely presented group in the variety with the unsolvable word problem" Algebra and Logic , 12 : 5 (1973) pp. 327–345 Algebra i Logika , 12 : 5 (1973) pp. 577–602
[16]	F.A. Garsaid, "The braid group and other groups" Quart. J. Math. Oxford Ser. (2) , 20 (1969) pp. 235–254
[17]	A.A. Markov, "On the unsolvability of certain problems in topology" Dokl. Akad. Nauk SSSR , 123 : 6 (1958) pp. 978–980 (In Russian)
[18]	M. Davis, M. Maschler, "Reductions of Hilbert's tenth problem" J. Symbolic Logic , 23 (1958) pp. 183–187
[19]	J. Robinson, "Existential definability in arithmetic" Trans. Amer. Math. Soc. , 72 (1952) pp. 437–449
[20]	Yu.V. Matiyasevich, "Enumerable sets are Diophantine" Soviet Math. Dokl. , 11 : 2 (1970) pp. 354–357 Dokl. Akad. Nauk SSSR , 191 : 2 (1970) pp. 279–282
[21]	Yu.V. Matiyasevich, "Diophantine representation of enumerable predicates" Math. USSR-Izv. , 5 : 1 (1971) pp. 1–28 Izv. Akad. Nauk SSSR Ser. Mat. , 35 (1971) pp. 3–30

Comments

Church' thesis is often formulated as stating that the idea of a recursive function (as defined in various equivalent ways, e.g. via Turing machines, cf. Turing machine), is the correct formalization of our intuitive concept of effective computability. Church' thesis is now almost universally accepted.

The halting problem asks whether there exists an effective procedure to decide, given a Turing machine $ M $ and input $ x $, whether the calculation ever terminates. A subset of $ \mathbf N ^ {k} $ is recursive if its characteristic function is recursive. Let all Turing machines be enumerated and let $ M _ {x} $ be the machine with index $ x $. Then the theorem that "x, yMx with inputy halts" is not a recursive set is a precise statement of the unsolvability of the halting problem.

The theorem to the effect that there exists a group with a presentation (i.e. given by generators and relations) for which the word problem is unsolvable is often known as the Boone–Novikov theorem.

A class of groups $ \mathfrak G $ is invariant if $ G \in \mathfrak G $ and $ H $ isomorphic to $ G $ imply $ H \in \mathfrak G $. It is non-trivial if there exist finitely-presented groups both inside and outside $ \mathfrak G $; and it is hereditary if a subgroup of an element of $ \mathfrak G $ is an element of $ \mathfrak G $. The Adyan–Rabin theorem now says that if $ \mathfrak G $ is an invariant, non-trivial and hereditary class, then there is no algorithm that determines whether the group given by a finite problem belongs to that class or not. Properties to which the Adyan–Rabin theorem applies include being cyclic, commutative, free, solvable, finite and equal to the identity group.

The original papers in which Church' thesis was advanced and defended are [a2], [a3]. Together [a4] and [a5] give an excellent introduction to algorithmic unsolvability. Reference [a1] contains a wealth of interesting material and references on the word problem in groups.

References

[a1]	W.W. Boone (ed.) F.B. Cannonito (ed.) R.C. Lyndon (ed.) , Word problems , North-Holland (1973)
[a2]	A. Church, "An unsolvable problem of elementary number theory (abstract)" Bull. Amer. Math. Soc. , 41 (1935) pp. 332–333
[a3]	A. Church, "An unsolvable problem of elementary number theory" Amer. J. Math. , 58 (1936) pp. 345–363
[a4]	M. Davis, "Unsolvable problems" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 567–594
[a5]	H.B. Enderton, "Elements of recursion theory" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 527–566