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. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions? While answering this question may not seem hard, the remarkable (and deep) result that emerges, in many important cases, is that the problem is undecidable. 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. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions? While answering this question may not seem hard, the remarkable (and deep) result that emerges, in many important cases, is that the problem is undecidable. Many, if not most all, undecidable problems in mathematics can be posed as word problems; see the list of undecidable problems for many examples. 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 algorithm is called a solution to the word problem for the encoding system. The simplest example of an undecidable word problem occurs in combinatory logic: when are two strings of combinators equivalent? Because combinators encode all possible Turing machines, and the equivalence of two Turing machines is undecidable, it follows that the equivalence of two strings of combinators is undecidable. Likewise, one has essentially the same problem in (untyped) lambda calculus: given two distinct lambda expressions, there is no algorithm which can discern whether they are equivalent or not; equivalence is undecidable. For several typed variants of the lambda calculus, equivalence is decidable by comparison of normal forms. 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. Roughly speaking, the word problem in an algebra is: given a set E of identities (an equational theory), and two terms s and t, is it possible to transform s into t using the identities in E as rewriting rules in both directions?. A proper extension of the word problem is known as the unification problem (a.k.a. the equation solving problem).While the former asks whether two terms are equal, the latter asks whether they have instances that are equal.As a common example, ' 2 + 3 = ? 8 + ( − 3 ) {displaystyle 2+3{stackrel {?}{=}}8+(-3)} ' is a word problem in the integer group ℤ,while ' 2 + x = ? 8 + ( − x ) {displaystyle 2+x{stackrel {?}{=}}8+(-x)} ' is a unification problem in the same group; since the former terms happen to be equal in ℤ, the latter problem has the substitution { x ↦ 3 } {displaystyle {xmapsto 3}} as a solution. Substitutions may be ordered into a partial order, thus, unification is the act of finding a join on a lattice.In this sense, the word problem on a lattice has a solution, namely, the set of all equivalent words is the free lattice.