Math 2.0

Group theory and generalizations Infinite groups and combinatorial group theory Problem

Word problem for groups

Builds on Presentation of a groupFree groupComputable set

Problem

Let G=⟨S∣R⟩G = \langle S \mid R \rangle be a group given by a finite presentation, with a finite set SS of generators and a finite set RR of relators. A word is a finite sequence of elements of S∪S−1S \cup S^{-1}, that is, an element of the free group F(S)F(S). The word problem for GG asks for an algorithm that decides, for every word ww, whether ww represents the identity element of GG. Equivalently: is the set of words that represent the identity a computable set?

Remarks

The answer depends on the group. The word problem is solvable for free groups, by free reduction, and for finite groups. Magnus showed that it is solvable for every group with one defining relator. Dehn gave an algorithm for the fundamental groups of closed orientable surfaces of genus at least 22. Novikov (1955) and Boone (1958) independently constructed finitely presented groups whose word problem is unsolvable. The set of words that represent the identity is always computably enumerable, so the word problem asks only whether its complement is too. Whether the word problem is solvable does not depend on the chosen finite presentation of GG.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Computable set, concept, no evidence levelComputable setconceptFree group, concept, no evidence levelFree groupconceptPresentation of a group, concept, no evidence levelPresentation of a gro…conceptWord problem for groups, problem, no evidence levelWord problem for grou…problem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Computable set concept
  2. Free group concept
  3. Presentation of a group concept
  4. Word problem for groups problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Word_problem_for_groups
About this page
TagPBGTTAVMMT
URIm2://PBGTTAVMMT
Kindproblem
WritingW0 stub
MSC20F10, 03D40
StatusThis copy of the site has no build data. Run m2 status PBGTTAVMMT.
AboutPresentation of a group
UsesPresentation of a group, Free group, Computable set
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.