Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group ${\displaystyle G}$ is the algorithmic problem of deciding whether two words in the generators represent the same element. The word problem is a well-known example of an undecidable problem.

For example, given two bijections ${\displaystyle g}$ and ${\displaystyle h}$ on the interval ${\displaystyle [0,1]}$ such that and ${\displaystyle g(g(g(x)))=h(h(x))=h(g(h(g(x))))=x}$ is known, can you prove that the compositions of ${\displaystyle g}$ and ${\displaystyle h}$ can only generate a finite number of other bijections on ${\displaystyle [0,1]}$ without more information about ${\displaystyle g}$ and ${\displaystyle h}$? The functions ${\displaystyle g}$ and ${\displaystyle h}$ are called the generators, and the set of all finite compositions of ${\displaystyle g}$ and ${\displaystyle h}$ and their inverses^[clarify] is the group they generate. In this case, generators generate a finite group of order 6 isomorphic to the symmetry group of an equilateral triangle, ${\displaystyle D_{3}}$, hence the equality of two arbitrary finite compositions can be decided.

More precisely, if ${\displaystyle A}$ is a finite set of generators for ${\displaystyle G}$ then the word problem is the membership problem for the formal language of all words in ${\displaystyle A}$ and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on ${\displaystyle A}$ to the group ${\displaystyle G}$. If ${\displaystyle B}$ is another finite generating set for ${\displaystyle G}$, then the word problem over the generating set ${\displaystyle B}$ is equivalent to the word problem over the generating set ${\displaystyle A}$. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group ${\displaystyle G}$.

The related but different uniform word problem for a class ${\displaystyle K}$ of recursively presented groups is the algorithmic problem of deciding, given as input a presentation ${\displaystyle P}$ for a group ${\displaystyle G}$ in the class ${\displaystyle K}$ and two words in the generators of ${\displaystyle G}$, whether the words represent the same element of ${\displaystyle G}$. Some authors require the class ${\displaystyle K}$ to be definable by a recursively enumerable set of presentations.