Word problem for groups

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.

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.

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. Novikov's result says that there are some finitely presented groups for which no algorithm solving the word problem exists.

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 fundamental 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.

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