Editing Word problem for groups (section)

== A more concrete description ==

In more concrete terms, the uniform word problem can be expressed as a [[rewriting]] question, for [[literal string]]s.{{sfn|Rotman|1994}} For a presentation <math>P</math> of a group <math>G</math>, <math>P</math> will specify a certain number of generators

:<math>x, y, z, \ldots </math>

for <math>G</math>. We need to introduce one letter for <math>x</math> and another (for convenience) for the group element represented by <math>x^{-1}</math>. Call these letters (twice as many as the generators) the alphabet <math>\Sigma</math> for our problem. Then each element in <math>G</math> is represented in ''some way'' by a product

:<math>abc ... pqr</math>

of symbols from <math>\Sigma</math>, of some length, multiplied in <math>G</math>. The string of length 0 ([[Empty string|null string]]) stands for the [[identity element]] <math>e</math> of <math>G</math>. The crux of the whole problem is to be able to recognise ''all'' the ways <math>e</math> can be represented, given some relations.

The effect of the ''relations'' in <math>G</math> is to make various such strings represent the same element of <math>G</math>. 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, consider the group given by the presentation <math>\langle a \, | \, a^3 = e \rangle</math>. Writing <math>A</math> for the inverse of <math>a</math>, we have possible strings combining any number of the symbols <math>a</math> and <math>A</math>. Whenever we see <math>aaa</math>, or <math>aA</math> or <math>Aa</math> we may strike these out. We should also remember to strike out <math>AAA</math>; this says that since the cube of <math>a</math> is the identity element of <math>G</math>, so is the cube of the inverse of <math>a</math>. Under these conditions the word problem becomes easy. First reduce strings to the empty string, <math>a</math>, <math>aa</math>, <math>A</math> or <math>AA</math>. Then note that we may also multiply by <math>aaa</math>, so we can convert <math>A</math> to <math>aa</math> and convert <math>AA</math> to <math>a</math>. The result is that the word problem, here for the [[cyclic group]] of order three, is solvable.

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.

The upshot is, in the worst case, that the relation between strings that says they are equal in <math>G</math> is an ''[[Undecidable problem]]''.