Word problem for groups: Difference between revisions

Revision as of 04:42, 6 September 2021

Revision as of 07:41, 24 September 2021

Line 6:

== History ==

Throughout the history of the subject, computations in groups have been carried out using various [[Normal form (abstract rewriting)|normal forms]]. These usually implicitly solve the word problem for the groups in question. In 1911 [[Max Dehn]] proposed that the word problem was an important area of study in its own right,{{sfn|Dehn|1911}} together with the [[conjugacy problem]] and the [[group isomorphism problem]]. In 1912 he gave an algorithm that solves both the word and conjugacy problem for the [[fundamental group]]s of closed orientable two-dimensional manifolds of genus greater than or equal to 2.{{sfn|Dehn|1912}} Subsequent authors have greatly extended [[Small cancellation theory#Dehn's algorithm|Dehn's algorithm]] and applied it to a wide range of group theoretic [[decision problem]]s.<ref>{{Citation|last=Greendlinger|first=Martin|date=June 1959|title=Dehn's algorithm for the word problem|journal=Communications on Pure and Applied Mathematics|volume=13|issue=1|pages=67–83|doi=10.1002/cpa.3160130108|postscript=.}}</ref><ref>{{Citation|last=Lyndon|first=Roger C.|author-link=Roger Lyndon|date=September 1966|title=On Dehn's algorithm|journal=Mathematische Annalen|volume=166|issue=3|pages=208–228|doi=10.1007/BF01361168|hdl=2027.42/46211|s2cid=36469569|postscript=.|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002296799&L=1|hdl-access=free}}</ref><ref>{{Citation|author-link1=Paul Schupp|last1=Schupp|first1=Paul E.|date=June 1968|title=On Dehn's algorithm and the conjugacy problem|journal=Mathematische Annalen|volume=178|issue=2|pages=119–130|doi=10.1007/BF01350654|s2cid=120429853|postscript=.|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002300036&L=1}}</ref>

It was shown by [[Pyotr Novikov]] in 1955 that there exists a finitely presented group ''G'' such that the word problem for ''G'' is [[Undecidable problem|undecidable]].<ref>{{Citation|last=Novikov|first=P. S.|author-link=Pyotr Novikov|year=1955|title=On the algorithmic unsolvability of the word problem in group theory|language=ru| zbl=0068.01301 | journal=[[Proceedings of the Steklov Institute of Mathematics]]|volume=44|pages=1–143}}</ref> It follows immediately that the uniform word problem is also undecidable. A different proof was obtained by [[William Boone (mathematician)|William Boone]] in 1958.<ref>{{Citation|last=Boone|first=William W.| author-link=William Boone (mathematician) | year=1958|title=The word problem|journal=Proceedings of the National Academy of Sciences|volume=44|issue=10|pages=1061–1065|url=http://www.pnas.org/cgi/reprint/44/10/1061.pdf|doi=10.1073/pnas.44.10.1061|zbl=0086.24701 |pmc=528693|pmid=16590307|bibcode=1958PNAS...44.1061B|doi-access=free}}</ref>

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.

Line 266:

* {{Citation | last1=Collins | first1=Donald J. | title=A simple presentation of a group with unsolvable word problem | mr=840121 | year=1986 | journal=Illinois Journal of Mathematics | issn=0019-2082 | volume=30 | issue=2 | pages=230–234 | doi=10.1215/ijm/1256044631| doi-access=free }}

* {{Citation | last1=Collins | first1=Donald J. | last2=Zieschang | first2=H. | title=Combinatorial group theory and fundamental groups | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | mr=1099152 | year=1990 | pages=166}}

*{{Citation | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Über unendliche diskontinuierliche Gruppen | doi=10.1007/BF01456932 | mr=1511645 | year=1911 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=71 | issue=1 | pages=116–144| s2cid=123478582 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0071&DMDID=DMDLOG_0013&L=1}}

*{{Citation | last1=Dehn | first1=Max | author1-link=Max Dehn | title=Transformation der Kurven auf zweiseitigen Flächen | doi=10.1007/BF01456725 | mr=1511705 | year=1912 | journal=[[Mathematische Annalen]] | issn=0025-5831 | volume=72 | issue=3 | pages=413–421| s2cid=122988176 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0072&DMDID=DMDLOG_0039&L=1}}

* A. V. Kuznetsov, "Algorithms as operations in algebraic systems", ''Izvestia Akad. Nauk SSSR Ser Mat'' (1958)

* C. F. Miller. "Decision problems for groups -- survey and reflections." In ''Algorithms and Classification in Combinatorial Group Theory'', pages 1–60. Springer, 1991.

*{{Citation | last1=Rotman | first1=Joseph | title=An introduction to the theory of groups | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | isbn=978-0-387-94285-8 | year=1994}}

* {{cite journal | last1 = Stillwell | first1 = J. | year = 1982 | title = The word problem and the isomorphism problem for groups | journal = Bulletin of the AMS | volume = 6 | pages = 33–56 | doi=10.1090/s0273-0979-1982-14963-1| doi-access = free }}

* {{Citation | last1=Nyberg-Brodda | first1=Carl-Fredrik | title=The word problem for one-relation monoids: a survey | year=2021 | journal=[[Semigroup Forum]] | volume=103 | issue=2 | pages=297–355 | doi=10.1007/s00233-021-10216-8 |url arxiv=2105.02853 https://link.springer.com/article/10.1007/s00233-021-10216-8| doi-access=free }}

{{DEFAULTSORT:Word Problem For Groups}}