In abstract algebra, the word problem for groups is the problem of deciding whether two given words of a presentation of a group represent the same element. There exists no general algorithm for this problem, as was shown by Pyotr Sergeyevich Novikov. The proof was announced in 1952 and published in 1955. A much simpler proof was obtained by Boone in 1959. Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ... In mathematics, one method of defining a group is by a presentation. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... Flowcharts are often used to represent algorithms. ... Pyotr Sergeyevich Novikov (August 15, 1901 - January 9, 1975) was a Russian mathematician who was born in Moscow, Russia and died in Moscow, Russia. ...

The word problem is only concerned with finitely presented groups, i.e. those groups which can be specified by finitely many generators and finitely many relations among those generators. A word is a product of generators, and two such words may denote the same element of the group even if they appear to be different, because by using the group axioms and the given relations it may be possible to transform one word into the other. The problem then is to find an algorithm which for any two given words decides whether they denote the same group element.

In more concrete terms, the problem can be expressed as a rewriting question, for literal strings. For a presentation P of a group G, P will specify a certain number of generators Rewriting in mathematics, computer science and logic covers a wide range of non-deterministic methods of replacing subterms of a formula with other terms. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...

x, y, z, ...

for G. We need to introduce one letter for x and another (for convenience) for the group element represented by x⁻¹. Call these letters (twice as many as the generators) the alphabet A for our problem. Then each element in G is represented in some way by a product

abc ... pqr

of symbols from A, of some length, multiplied in G. The effect of the relations in G is to make various such strings represent the same element of G. In fact the relations provide a list of strings that can be either introduced where we want, or cancelled out whenever we see them, without changing the 'value', i.e. the group element that is the result of the multiplication.

For a simple example, take the presentation <x|x³>. Writing y for the inverse of x, we have possible strings of x′s and y′s. Whenever we see xxx, or xy or yx we may strike these out. We should also remember to strike out yyy; this says that since the cube of x is the identity element of G, so is the cube of the inverse of x. Under these conditions the word problem becomes easy. First reduce strings to e, x, xx, y or yy. Then note that we may also multiply by xxx, so we can convert yy to x. The result is that we can prove that the word problem here, for what is the cyclic group of order three, is soluble. In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a. ...

This is not, however, the typical case. For the example, we have a canonical form available that reduces any string to one of length at most three, by decreasing the length monotonically. In general, it is not true that one can get a canonical form for the elements, by stepwise cancellation. One may have to use relations to expand a string many-fold, in order eventually to find a cancellation that brings the length right down. Generally, in mathematics, a canonical form is a function that is written in the most standard, conventional, and logical way. ...

The upshot is, in the worst case, that the relation between strings that says they are equal in G is not decidable. The word decidable has formal meaning in computability theory, the theory of formal languages, and mathematical logic. ...

It is important to realize that the word problem is in fact solvable in many special cases; algorithms for many group presentations can be readily given. For example, see Todd-Coxeter algorithm and Knuth-Bendix completion algorithm. Novikov's result says that there are some finitely presented groups for which no algorithm solving the word problem exists. The Todd-Coxeter algorithm, discovered by Todd and Coxeter in 1936, is a procedure that can solve the coset enumeration problem. ... The Knuth-Bendix completion algorithm is an algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. ...

The word problem is sometimes called the Dehn problem, after Max Dehn who first posed it in 1911. It was one of the first examples of an unsolvable problem to be found not in mathematical logic or the theory of algorithms, but in one of the central branches of classical mathematics, algebra. As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well. Max Dehn (November 13, 1878 – June 27, 1952) was a German mathematician. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ... Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...

References:

• Boone, Cannonito, Lyndon. Word Problems: Decision Problem in Group Theory. Netherlands: North-Holland. 1973.
• P. S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov 44 (1955), pp 1-143. (in Russian)
• W. W. Boone. The word problem. Annals of Mathematics, 70(2) (1959), pp 207-265
• J.J. Rotman. The Theory of Groups: An Introduction. Boston: Allyn and Bacon. 1965.
• J. Stillwell. The word problem and the isomorphism problem for groups. Bulletin AMS 6 (1982), pp 33-56