Word problem (mathematics)
Encyclopedia
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.
) 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.
: when are two strings of combinators equivalent? Because combinators encode all possible Turing machine
s, 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 lambda calculus
: given two distinct lambda expressions, there is no algorithm which can discern whether they are equivalent or not; equivalence is undecidable.
, 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 of identities E (an equational theory), and two terms
x and y, is it possible to transform x into y using the identities in E as rewriting
rules in both directions?. The act of discovering such equivalences is known as unification. The process of unification requires discovering substitutions
to demonstrate equality. 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
.
One of the most deeply studied cases of the word problem is in the theory of semigroup
s and group
s. There are many groups for which the word problem
is not decidable
, in that there is no Turing machine that can determine the equivalence of any two words in a finite time.
The word problem on ground terms is not decidable.
The word problem on free Heyting algebra
s is difficult. 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).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
whether two given representatives represent the same element of the set. The problem is commonly encountered in abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, where given a presentation of an algebraic structure by generators
Generating set
In mathematics, the expressions generator, generate, generated by and generating set can have several closely related technical meanings:...
and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups
Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
. 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
Rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
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
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
.
Many, if not most all, undecidable problems in mathematics can be posed as word problems; see the list of undecidable problems for many examples.
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 machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
) 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 word problem in combinatorial calculus
The simplest example of an undecidable word problem occurs in combinatory logicCombinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
: when are two strings of combinators equivalent? Because combinators encode all possible Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s, 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 lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
: given two distinct lambda expressions, there is no algorithm which can discern whether they are equivalent or not; equivalence is undecidable.
The word problem in universal algebra
In algebraAlgebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
, one often studies infinite algebras which are generated (under the finitary
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
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 of identities E (an equational theory), and two terms
Term (logic)
In mathematical logic, universal algebra, and rewriting systems, terms are expressions which can be obtained from constant symbols, variables and function symbols...
x and y, is it possible to transform x into y using the identities in E as rewriting
Rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
rules in both directions?. The act of discovering such equivalences is known as unification. The process of unification requires discovering substitutions
Substitution (logic)
Substitution is a fundamental concept in logic. Substitution is a syntactic transformation on strings of symbols of a formal language.In propositional logic, a substitution instance of a propositional formula is a second formula obtained by replacing symbols of the original formula by other formulas...
to demonstrate equality. Substitutions may be ordered into a partial order, thus, unification is the act of finding a join
Join
Join may refer to:* Join , to include additional counts or additional defendants on an indictment* Join , a least upper bound of set orders in lattice theory* Join , a type of binary operator...
on a lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
. In this sense, the word problem on a lattice has a solution, namely, the set of all equivalent words is the free lattice
Free lattice
In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property. The word problem for free lattices is also challenging.-Formal definition:...
.
One of the most deeply studied cases of the word problem is in the theory of semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
s and group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
s. There are many groups for which the word problem
Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
is not decidable
Decidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
, in that there is no Turing machine that can determine the equivalence of any two words in a finite time.
The word problem on ground terms is not decidable.
The word problem on free Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
s is difficult. The only known results are that the free Heyting algebra on one generator is infinite, and that the free complete Heyting algebra
Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
on one generator exists (and has one more element than the free Heyting algebra).