Editing Word problem for groups (section)

{{Short description|Problem in finite group theory}}
{{CS1 config|mode=cs2}}
In [[mathematics]], especially in the area of [[abstract algebra]] known as [[combinatorial group theory]], the '''word problem''' for a [[finitely generated group]] <math>G</math> is the algorithmic problem of deciding whether two words in the generators represent the same element of <math>G</math>.  The word problem is a well-known example of an [[undecidable problem]].

If <math>A</math> is a finite set of [[Generating set of a group|generators]] for <math>G</math>, then the word problem is the membership problem for the [[formal language]] of all words in <math>A</math> and a formal set of inverses that map to the identity under the natural map from the [[free monoid with involution]] on <math>A</math> to the group <math>G</math>.  If <math>B</math> is another finite generating set for <math>G</math>, then the word problem over the generating set <math>B</math> is equivalent to the word problem over the generating set <math>A</math>. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group <math>G</math>.

The related but different '''uniform word problem''' for a class <math>K</math> of recursively presented groups is the algorithmic problem of deciding, given as input a [[presentation of a group|presentation]] <math>P</math> for a group <math>G</math> in the class <math>K</math> and two words in the generators of <math>G</math>, whether the words represent the same element of <math>G</math>. Some authors require the class <math>K</math> to be definable by a [[recursively enumerable]] set of presentations.