The Word Problem for Groups

Imagine a tiny alphabet of symbols — say a, b and their inverses $a^{-1}$, $b^{-1}$ — and a handful of rules that say which strings mean the same thing. For example, a rule might say ab = ba, or aa = 1 (the empty string). A group is exactly this: a set of symbols (the generators) plus a list of equations (the relations).

A word is just a string of those symbols, like $a b a^{-1} b^{-1}$. Two words are equal in the group if you can turn one into the other by applying the rules — inserting or deleting pieces that the relations declare to be trivial.

The word problem asks the most natural question imaginable: given two words, do they name the same group element? Equivalently, can a given word be reduced to the empty word 1 (the identity)?

It sounds like bookkeeping. Apply rules until the strings match. Surely a computer can grind through that? The astonishing answer is no — and not just "slowly," but never, in a precise and permanent sense.

Below is a small group given by a few relations (each says some pattern equals another). Start from a word and click rules to rewrite it. Your goal: reach the identity 1, proving the word equals the identity in this group.

<p class="hint">{{hint}}</p>
<div class="row">
  <button id="easy" type="button" class="ghost">{{btn_easy}}</button>
  <button id="hard" type="button" class="ghost">{{btn_hard}}</button>
  <button id="auto" type="button" class="ghost">{{btn_auto}}</button>
</div>
<div class="word" id="word"></div>
<div class="status" id="status">{{status_init}}</div>
<p class="sub">{{sub_relations}}</p>
<div class="rules" id="rules"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.sub { font-size: .82rem; color: #555; margin: .9rem 0 .35rem; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
.word { font: 700 26px ui-monospace, monospace; letter-spacing: 3px; color: #1d3557;
        background: #eef3f8; border: 1px solid #cdd9e3; border-radius: 10px;
        padding: .7rem .9rem; min-height: 2.4em; display: flex; align-items: center;
        flex-wrap: wrap; gap: 2px; }
.tok { padding: 0 1px; }
.tok.hit { background: #ffe08a; border-radius: 4px; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.rules { display: grid; grid-template-columns: repeat(auto-fill, minmax(160px,1fr)); gap: .45rem; }
.rule { font: 600 14px ui-monospace, monospace; padding: .5rem .6rem; border: 1px solid #1d3557;
        background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; text-align: center;
        transition: all .1s; }
.rule:hover { background: #1d3557; color: #fff; }
.rule:disabled { opacity: .35; cursor: not-allowed; }
button.ghost { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid #1d3557;
        background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
button.ghost:hover { background: #1d3557; color: #fff; }

// Code not found

Try the friendly word first — a short chain of rewrites collapses it to 1. Then try the hard word: the rules still apply, but the search balloons. In this example a solution exists, yet notice how quickly the choices branch. Now picture a group where the rules are tangled enough that no recipe tells you when to stop searching — that is exactly the situation Novikov and Boone built.

Here is the precise status, and it is one of the great surprises of 20th-century mathematics.

• One direction is easy. If two words are equal, there is always a finite chain of rule-applications connecting them — so you can, in principle, find it by searching longer and longer chains.
• The other direction is the trap. If two words are not equal, that blind search never halts. You keep rewriting forever, never sure whether the next step would have worked.
• It is undecidable — proven, not merely open. In 1955 Pyotr Novikov, and independently in 1958 William Boone, constructed an explicit finitely presented group whose word problem no algorithm can solve. There is no program that, given any two words, always halts with a correct yes/no.
• Why it's impossible. The proofs encode a Turing machine (or equivalently a semigroup whose word problem was already known undecidable) into the group's relations. Deciding the word problem would let you decide whether the machine halts — and that is famously impossible.

So this is not the NP-style "hard but solvable in principle." It sits one rung higher, alongside the halting problem and Hilbert's tenth problem: a question that is provably beyond any algorithm, no matter how much time or memory you grant it. Many specific groups (finite groups, free groups, abelian groups, hyperbolic groups) have perfectly good algorithms — the impossibility is about a single method that works for every group.

A question that cannot be answered in general still teaches us exactly where the safe ground ends:

• Computer algebra systems: software like GAP works with groups every day, but it cannot promise to decide equality in an arbitrary presentation — it relies on classes of groups where the problem is decidable.
• Topology: deciding whether two spaces are the "same" (homeomorphic) is undecidable in high dimensions, and the word problem is the engine behind that result — fundamental groups carry the difficulty.
• Automated reasoning and term rewriting: the same "apply rules until things match" pattern underlies theorem provers; the word problem marks the line where completion procedures can loop forever.
• Knowing when to stop: practical tools detect special structure (confluent rewriting systems, automatic groups) precisely because the general case is hopeless.

The lesson echoes across the limits of computation, the same boundary you meet in the halting problem: identify the well-behaved cases, and never expect one universal algorithm to tame them all.

The word problem is a humbling masterpiece. Its statement fits in a sentence — do these two strings mean the same thing? — yet Novikov (1955) and Boone (1958) proved that no algorithm can answer it for every group. The "yes" cases reveal themselves to patient search; the "no" cases can hide forever.

It is a reminder that some walls in mathematics are not waiting for a cleverer programmer. Like the halting problem, the word problem is undecidable for good, and learning to recognize such walls — and the friendly territory just inside them — is one of the quietest superpowers in all of computation.