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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

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. An artistic representation of a Turing Machine . ...

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 algorithm is 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, whether they represent the same element of the algebra. Algebra is a branch of mathematics concerning the study of structure, relation and quantity. ...

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 name lattice is suggested by the form of the Hasse diagram depicting it. ... In mathematics, in the area of order theory, a free lattice is the free object corresponding to a 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; its just that one might require an infinite number of algorithms to find all equivalences). In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... This picture illustrates how the hours on a clock form a group under modular addition. ... In abstract algebra, the word problem for groups is the problem of deciding whether two given words of a presentation of a group represent the same element. ...

The word problem on free Heyting algebras is difficult^[1] 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). In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ... In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. ...

See also

• Munn tree

References

1. ^ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)