Introduction

Imagine a tiny alphabet of symbols — say a, b and their inverses a−1a^{-1}, b−1b^{-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 aba−1b−1a 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.

Rewrite the Word

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">This group has generators <b>a, b</b> (and inverses <b>A = a⁻¹, B = b⁻¹</b>). The relations below let you replace one pattern by another. Pick a word, then click a rule to rewrite the highlighted match. Reach <b>1</b> (the empty word) to prove the word equals the identity.</p>
<div class="row">
  <button id="easy" type="button" class="ghost">Load easy word</button>
  <button id="hard" type="button" class="ghost">Load hard word</button>
  <button id="auto" type="button" class="ghost">Auto-solve (search)</button>
</div>
<div class="word" id="word"></div>
<div class="status" id="status">Pick a word to begin.</div>
<p class="sub">Relations (each pattern can be swapped for the other, either direction):</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Word problem demo for the group  < a, b | a^3 = 1, b^2 = 1, ba = a^2 b > (this is S3).
// We work with letters a, A(=a^-1), b, B(=b^-1). A word equals the identity iff it
// can be rewritten to the empty word "1" using the relations (applied both ways).
// CHECKING a given rewrite chain is trivial; FINDING one in general is the hard part —
// and for groups in general it is UNDECIDABLE (Novikov 1955, Boone 1958).

// Each relation is a pair [L, R]: any occurrence of L may be replaced by R, or R by L.
const RELS = [
  ['aA', ''],   // a a^-1 = 1
  ['Aa', ''],   // a^-1 a = 1
  ['bB', ''],   // b b^-1 = 1
  ['Bb', ''],   // b^-1 b = 1
  ['aaa', ''],  // a^3 = 1
  ['bb', ''],   // b^2 = 1
  ['ba', 'aab'] // b a = a^2 b   (the non-commuting relation)
];
// Build the clickable directed rules (both directions of each relation, skip trivial).
const RULES = [];
for (const [L, R] of RELS) {
  RULES.push({ from: L, to: R });
  if (R !== '') RULES.push({ from: R, to: L });
}

const EASY = 'aaa';                 // a^3 -> 1  (collapses in one step)
const HARD_ID = 'baaaB';            // b a^3 b^-1 = b 1 b^-1 = b b^-1 = 1  (identity, but the
                                    // path is not obvious — the search branches quickly)

let word = '';
const $ = id => document.getElementById(id);
const pretty = ch => ch === 'A' ? 'a⁻¹' : ch === 'B' ? 'b⁻¹' : ch;

function renderWord(hitStart, hitLen) {
  const w = $('word'); w.innerHTML = '';
  if (word === '') { const s = document.createElement('span'); s.className='tok'; s.textContent='1'; w.appendChild(s); return; }
  for (let i = 0; i < word.length; i++) {
    const s = document.createElement('span');
    s.className = 'tok' + (hitStart!=null && i>=hitStart && i<hitStart+hitLen ? ' hit' : '');
    s.textContent = pretty(word[i]);
    w.appendChild(s);
  }
}
function setStatus(t, cls){ const s=$('status'); s.textContent=t; s.className='status '+(cls||''); }

function applyRule(rule){
  // apply at the first matching position
  let idx;
  if (rule.from === '') { // insertion not offered as a button here
    return false;
  }
  idx = word.indexOf(rule.from);
  if (idx < 0) return false;
  word = word.slice(0, idx) + rule.to + word.slice(idx + rule.from.length);
  renderWord(idx, rule.to.length);
  if (word === '') setStatus('Reached the identity 1 — the word equals the identity!','ok');
  else setStatus(fmt('Applied  %v% → %v2%.', { v: rule.from||'1', v2: rule.to||'1' }),'');
  renderRules();
  return true;
}

function renderRules(){
  const box = $('rules'); box.innerHTML='';
  for (const r of RULES) {
    if (r.from === '') continue; // skip pure-insertion rules in the UI
    const b = document.createElement('button');
    b.className = 'rule';
    b.textContent = fmt('%from% → %v%', { from: r.from, v: r.to || '1' });
    b.disabled = word.indexOf(r.from) < 0;
    b.addEventListener('click', () => applyRule(r));
    box.appendChild(b);
  }
}

// Breadth-first search: does `start` reduce to the empty word? (bounded — to keep the
// demo finite. In a general group NO such bound is guaranteed to exist.)
function search(start){
  const seen = new Set([start]);
  let frontier = [start];
  let steps = 0;
  const MAX = 4000;
  while (frontier.length && steps < MAX) {
    const next = [];
    for (const w of frontier) {
      steps++;
      if (w === '') return { ok:true, steps };
      for (const r of RULES) {
        if (r.from === '') continue;
        let idx = w.indexOf(r.from);
        while (idx >= 0) {
          const nw = w.slice(0, idx) + r.to + w.slice(idx + r.from.length);
          if (nw.length <= 8 && !seen.has(nw)) { seen.add(nw); next.push(nw); }
          idx = w.indexOf(r.from, idx + 1);
        }
      }
    }
    frontier = next;
  }
  return { ok:false, steps };
}

function load(w, label){ word = w; renderWord(); renderRules(); setStatus(fmt('Loaded the %label% word. Click rules to rewrite toward 1.', { label: label }),''); }

$('easy').addEventListener('click', () => load(EASY, 'easy'));
$('hard').addEventListener('click', () => load(HARD_ID, 'hard'));
$('auto').addEventListener('click', () => {
  if (word === '') { setStatus('Load a word first.','bad'); return; }
  const r = search(word);
  if (r.ok) setStatus(fmt('Search found a path to 1 after exploring %steps% words.', { steps: r.steps }),'ok');
  else setStatus(fmt('No path to 1 found within the bound after %steps% words — this word is NOT the identity.', { steps: r.steps }),'bad');
});

load(EASY, 'easy');
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/word-problem-groups/Content licensed under CC BY-NC 4.0.