Word problem (mathematics)

In computational mathematics, a word problem is a challenge where we try to figure out if two expressions mean the same thing based on a set of rules for changing one expression into another. This idea is important in both mathematics and computer science. One classic example is the word problem for groups, where mathematicians study how to tell if two ways of combining numbers or symbols are actually the same.

This type of problem helps us understand the limits of what computers and math can solve. Some big discoveries show that, in many cases, there is no way to always know if two expressions are the same. This question of whether something can be decided or not is a deep part of how we study computation and logic.

For everyday learning in school, word problems might mean something different, like 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 using strict rules. This helps both mathematicians and computer scientists see what can and cannot be solved with 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 often want to show 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 the areas of semigroups and groups. Here are some important moments in its history:

• In 1910, Axel Thue asked a general question about rewriting expressions.
• In 1911, Max Dehn introduced the word problem for certain types of groups.
• In 1912, Dehn shared a method 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 any computer.
• In 1955, Pyotr Novikov proved that the word problem for groups cannot always be solved.
• In 1977, Gennady Makanin solved another related problem about equations in certain structures.

The word problem for semi-Thue systems

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

These problems are undecidable, meaning there is no single method to solve them for all cases. This remains true even when we use a limited set of symbols and rules. Even for certain specific 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 figure out if two different ways of combining group elements actually give the same result. This idea was first suggested in 1911. Later, in 1955, it was discovered that for some groups, there is no way to always decide 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 any kind of machine, 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 following a set of rules. In general, there is no way to always know the answer. However, if every object can be simplified to one special form in a limited number of steps, we can check if two things are the same by seeing if they simplify to that special form. The Knuth-Bendix completion algorithm helps turn a set of rules into one that follows this special 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 — this usually happens in certain types of groups called non-abelian groups.

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}}