In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G {\displaystyle G} is the algorithmic problem of deciding whether two words in the generators represent the same element of G {\displaystyle G} . The word problems for certain groups provide well-known examples of undecidable problems. If A {\displaystyle A} is a finite set of generators for G {\displaystyle G} , then the word problem is the membership problem for the formal language of all words in A {\displaystyle A} and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A {\displaystyle A} to the group G {\displaystyle G} . If B {\displaystyle B} is another finite generating set for G {\displaystyle G} , then the word problem over the generating set B {\displaystyle B} is equivalent to the word problem over the generating set A {\displaystyle A} . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G {\displaystyle G} . The related but different uniform word problem for a class K {\displaystyle K} of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P {\displaystyle P} for a group G {\displaystyle G} in the class K {\displaystyle K} and two words in the generators of G {\displaystyle G} , whether the words represent the same element of G {\displaystyle G} . Some authors require the class K {\displaystyle K} to be definable by a recursively enumerable set of presentations.
History Throughout the history of the subject, computations in groups have been carried out using various normal forms. These usually implicitly solve the word problem for the groups in question. In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, together with the conjugacy problem and the group isomorphism problem. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems. It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G {\displaystyle G} such that the word problem for G {\displaystyle G} is undecidable. It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by William Boone in 1958. The word problem 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. The word problem is in fact solvable for many groups G {\displaystyle G} . For example, polycyclic groups have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the Todd–Coxeter algorithm and the Knuth–Bendix completion algorithm. On the other hand, the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has an unsolvable word problem. For instance Dehn's algorithm does not solve the word problem for the fundamental group of the torus. However this group is the direct product of two infinite cyclic groups and so has a solvable word problem.
A more concrete description In more concrete terms, the uniform word problem can be expressed as a rewriting question, for literal strings. For a presentation P {\displaystyle P} of a group G {\displaystyle G} , P {\displaystyle P} will specify a certain number of generators
x , y , z , … {\displaystyle x,y,z,\ldots }
for G {\displaystyle G} . We need to introduce one letter for x {\displaystyle x} and another (for convenience) for the group element represented by x − 1 {\displaystyle x^{-1}} . Call these letters (twice as many as the generators) the alphabet Σ {\displaystyle \Sigma } for our problem. Then each element in G {\displaystyle G} is represented in some way by a product
a b c . . . p q r {\displaystyle abc...pqr}
… excerpt ends here. Continue reading the full article.
