View source for Word problem for groups

The '''word problem for groups''' is the algorithmic question of deciding whether two words in the generators of a finitely presented group represent the same element. For [[Free group|free groups]], the answer is trivial: reduce both words and compare. For groups with relations, the problem can be undecidable — Max Dehn proved in 1911 that the word problem is solvable for fundamental groups of surfaces, but in 1955 Pyotr Novikov and independently William Boone showed that there exist finitely presented groups with unsolvable word problems. The boundary between decidability and undecidability in group theory is the boundary between geometry and chaos.

''The word problem is not a technical curiosity. It is the place where algebra meets the limits of computation, and the fact that some groups resist algorithmic understanding suggests that mathematical structure itself can outrun formal reasoning.''

[[Category:Mathematics]]
[[Category:Computability]]
[[Category:Systems]]