Word problem (mathematics)

In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements, is the algorithmic problem of deciding whether two given representatives represent the same element of the set.

Background and motivation

Many occasions arise in mathematics where one wishes to use a finite amount of information to describe an element of a (typically infinite) set. This issue is particularly apparent in computational mathematics. Traditional models of computation (such as the Turing machine) have storage capacity which is unbounded, so it is in principle possible to perform computations with the elements of infinite sets. On the other hand, since the amount of storage space in use at any one time is finite, we need each element to have a finite representation.

For various reasons, it is not always possible or desirable to use a system of "unique" encodings, that is, one in which every element has a single encoding. When using an encoding system without uniqueness, the question naturally arises of whether there is an algorithm which, given as input two encodings, decides whether they represent the same element. Such an algorithmis called a "solution to the word problem" for the encoding system.

The word problem in universal algebra

In algebra, one often studies infinite algebras which are generated (under the finitary operations of the algebra) by finitely many elements. In this case, the elements of the algebra have a natural system of finite encoding as expressions in terms of the generators and operations. The word problem here is thus to determine, given two such expressions, whetherthey represent the same element of the algebra.

The word problem occurs in the study of lattices; there it may be shown that the word problem has a solution, namely, the set of all equivalent words is the free lattice.

The most important and deeply studied case of the word problem is in the theory of semigroups and groups. There are many groups for which the word problem is not solvable, in that there is no Turing machine that can determine the equivalence of "any" two words in a finite time. (There do exist, however, algorithms to determine the equivalence of given words; it is just that one might require an infinite number of algorithms to find all equivalences).

The word problem on free Heyting algebras is difficult [Peter T. Johnstone, "Stone Spaces", (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. "(See chapter 1, paragraph 4.11)"] . The only known results are that the free Heyting algebra on one generator is infinite, and that the free complete Heyting algebra on one generator exists (and has one more element than the free Heyting algebra).

ee also

* Munn tree
* Word problem for groups
* Knuth-Bendix completion algorithm

References