Word problem (mathematics)

A word problem in math is a challenge where we try to see if two math expressions mean the same thing. We use rules to change one expression into another to figure this out.

This idea is important in math and computer science. One famous example is the word problem for groups, where mathematicians study if two ways of combining numbers or symbols are the same.

Word problems help us understand what computers and math can and cannot solve. Some discoveries show that sometimes, there is no way to always know if two expressions are the same. This question is a big part of how we study computation and logic.

In school, word problems might be math questions told in a story. But in advanced math and computer science, the word problem is about understanding how expressions relate to each other with rules. This helps mathematicians and computer scientists see what can be solved with steps called algorithms. For more on how word problems are used in education, see Word problem (mathematics education). For other meanings of the term, see Word problem).

Background and motivation

In computer algebra, we sometimes want to know if two math expressions mean the same thing. For example, we might ask if (x ⋅ y) / z is the same as (x / z) ⋅ y. An algorithm that can tell us this is called a solution to the word problem.

One way to solve this is to pick a special form for each expression, called the normal form. Then, we just check if these special forms look exactly the same. For instance, we might decide that x ⋅ y ⋅ z⁻¹ is the special form for (x ⋅ y) / z, (x / z) ⋅ y, and (y / z) ⋅ x. If we can change any of these expressions into that special form, we can see if they are equal. But there are other ways to solve the word problem that don’t use this special form.

The word problem looks at expressions with constants to see if they are equal. A related problem, called the unification problem, looks at expressions with variables to see if they can ever be equal. For example, 2 + 3 = ? 8 + (−3) is a word problem, because it has no variables. But 2 + x = ? 8 + (−x) is a unification problem, because it has the variable x. In this case, the problem has a solution when x is 3.

History

The word problem has been studied a lot, especially in areas like semigroups and groups. Here are some important moments in its history:

In 1910, Axel Thue asked a question about changing expressions.
In 1911, Max Dehn introduced the word problem for some types of groups.
In 1912, Dehn shared a way to solve the problem for some groups.
In 1947, Emil Post and Andrey Markov Jr. showed that some problems with semigroups cannot be solved by computers.
In 1955, Pyotr Novikov proved that the word problem for groups cannot always be solved.
In 1977, Gennady Makanin solved another problem about equations in some structures.

The word problem for semi-Thue systems

The accessibility problem for string rewriting systems (semi-Thue systems or semigroups) asks if we can change one word into another using specific rules. These rules can only be used in one direction. The word problem asks if we can change one word into another when the rules can be used in both directions.

These problems are undecidable. This means there is no single way to solve them for every case. This stays true even when we use only a few symbols and rules. Even for some special types of words and rules, there is no way to always find the answer.

The word problem for groups

Main article: Word problem for groups

In math, a word problem helps us find out if two different ways of combining group elements give the same answer. This idea was first suggested in 1911. Later, in 1955, it was found that for some groups, there is no way to always tell if two expressions are the same.

The word problem in combinatorial calculus and lambda calculus

Main article: Combinatory logic § Undecidability of combinatorial calculus

One of the first big discoveries was that it is impossible to know for sure if two strings of combinators are the same. This is because combinators can act like machines, and we cannot always tell if two machines will do the same thing. Alonzo Church found this out in 1936.

We see a similar problem with lambda expressions. When we have two different lambda expressions, there is no way to know for sure if they mean the same thing. For some special kinds of lambda expressions, we can check if they are the same by simplifying them.

The word problem for abstract rewriting systems

In an abstract rewriting system, the word problem asks if two things are the same after using a set of rules. Usually, there is no way to always know the answer. But, if every object can be made simpler in a few steps, we can check if two things are the same by seeing if they both become that simpler form. The Knuth-Bendix completion algorithm helps change a set of rules into one that follows this simpler form.

The word problem in universal algebra

In universal algebra, we study special math systems made from a group of starting items, called a generating set, and certain math actions called operations. These actions follow some rules, called identities. The word problem asks us to decide if two different math expressions using these starting items and actions actually mean the same thing, following all the rules.

For some types of math systems, like free Heyting algebras, solving the word problem is very hard. We only know that the simplest version of a Heyting algebra has infinitely many elements, and that a slightly bigger version, called a free complete Heyting algebra, also exists.

The word problem for free lattices

In math, we sometimes want to know if two different ways of writing something actually mean the same thing. This is called the "word problem."

For special math structures called free bounded lattices, we can decide if two writings are the same.

Bounded lattices have special rules and two main operations: ∨ (or) and ∧ (and). We can build many expressions using these rules and starting points from a set of generators X.

The word problem asks which of these expressions mean the same thing in every bounded lattice. We can solve this problem by creating a special order ≤~ that helps us compare expressions. If two expressions fit this order in both directions, they mean the same thing. This method works well and can be used to check if two expressions are equal in all bounded lattices.

Example: A term rewriting system to decide the word problem in the free group

Bläsius and Bürckert show how the Knuth–Bendix algorithm can help decide if two math expressions are the same in groups. This algorithm creates special rules to change any math expression into a simplest form. If two expressions turn into the exact same simplest form, they are equal in every group.

For example, two different-looking expressions both simplify to "1", meaning they are equal. Another pair simplifies to different forms, showing they are not always equal.

Group axioms used in Knuth–Bendix completion
A1	1 ⋅ x {\displaystyle 1\cdot x}	= x {\displaystyle =x}
A2	x − 1 ⋅ x {\displaystyle x^{-1}\cdot x}	= 1 {\displaystyle =1}
A3	( x ⋅ y ) ⋅ z {\displaystyle (x\cdot y)\cdot z}	= x ⋅ ( y ⋅ z ) {\displaystyle =x\cdot (y\cdot z)}

Term rewrite system obtained from Knuth–Bendix completion
R1	1 ⋅ x {\displaystyle 1\cdot x}	⇝ x {\displaystyle \rightsquigarrow x}
R2	x − 1 ⋅ x {\displaystyle x^{-1}\cdot x}	⇝ 1 {\displaystyle \rightsquigarrow 1}
R3	( x ⋅ y ) ⋅ z {\displaystyle (x\cdot y)\cdot z}	⇝ x ⋅ ( y ⋅ z ) {\displaystyle \rightsquigarrow x\cdot (y\cdot z)}
R4	x − 1 ⋅ ( x ⋅ y ) {\displaystyle x^{-1}\cdot (x\cdot y)}	⇝ y {\displaystyle \rightsquigarrow y}
R8	1 − 1 {\displaystyle 1^{-1}}	⇝ 1 {\displaystyle \rightsquigarrow 1}
R11	x ⋅ 1 {\displaystyle x\cdot 1}	⇝ x {\displaystyle \rightsquigarrow x}
R12	( x − 1 ) − 1 {\displaystyle (x^{-1})^{-1}}	⇝ x {\displaystyle \rightsquigarrow x}
R13	x ⋅ x − 1 {\displaystyle x\cdot x^{-1}}	⇝ 1 {\displaystyle \rightsquigarrow 1}
R14	x ⋅ ( x − 1 ⋅ y ) {\displaystyle x\cdot (x^{-1}\cdot y)}	⇝ y {\displaystyle \rightsquigarrow y}
R17	( x ⋅ y ) − 1 {\displaystyle (x\cdot y)^{-1}}	⇝ y − 1 ⋅ x − 1 {\displaystyle \rightsquigarrow y^{-1}\cdot x^{-1}}