Word problem for groups: Difference between revisions

Revision as of 20:51, 29 January 2023

Revision as of 02:10, 20 March 2023

Line 12:

The word problem was one of the first examples of an unsolvable problem to be found not in [[mathematical logic]] or the [[theory of algorithms]], but in one of the central branches of classical mathematics, [[abstract algebra|algebra]]. As a result of its unsolvability, several other problems in combinatorial group theory have been shown to be unsolvable as well.

It is important to realize that the word problem is in fact solvable for many groups ''G''. For example, [[polycyclic group]]s have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the [[Todd–Coxeter algorithm]]<ref>{{cite journal |last1=Todd |first1=J. |last2=Coxeter |first2=H.S.M. |title=A practical method for enumerating cosets of a finite abstract group |journal=Proceedings of the Edinburgh Mathematical Society |volume=5 |issue=1 |pages=26–34 |date=1936 |doi=10.1017/S0013091500008221 |url=|doi-access=free }}</ref> and the [[Knuth–Bendix completion algorithm]].<ref>{{cite book |first1=D. |last1=Knuth |first2=P. |last2=Bendix |chapter=Simple word problems in universal algebras |chapter-url=https://wwwbooks.google.com/books/edition/Computational_Problems_in_Abstract_Algeb/KIDiBQAAQBAJ?hlid=enKIDiBQAAQBAJ&pg=PA263 |editor-first=J. |editor-last=Leech |title=Computational Problems in Abstract Algebra: Proceedings of a Conference Held at Oxford Under the Auspices of the Science Research Council Atlas Computer Laboratory, 29th August to 2nd September 1967 |publisher=Springer |date=2014 |orig-year=1970 |isbn=9781483159423 |pages=263–297 |url=}}

</ref> On the other hand, the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has an unsolvable word problem. For instance Dehn's algorithm does not solve the word problem for the fundamental group of the [[torus]]. However this group is the direct product of two infinite cyclic groups and so has a solvable word problem.

Line 50:

**Finitely presented simple groups.

*Finitely presented [[residually finite]] groups

*One relator groups<ref>{{cite book |first1=Roger C. |last1=Lyndon |first2=Paul E |last2=Schupp |title=Combinatorial Group Theory |publisher=Springer |date=2001 |isbn=9783540411581 |pages=1–60 |url=https://wwwbooks.google.com/books/edition/Combinatorial_Group_Theory/aiPVBygHi_oC?hlid=enaiPVBygHi_oC&pg=PP1}}</ref> (this is a theorem of Magnus), including:

**Fundamental groups of closed orientable two-dimensional manifolds.

*Combable groups