Word problem for groups: Difference between revisions

Revision as of 13:15, 21 October 2020

Revision as of 15:27, 7 December 2020

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.|authorlinkauthor-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|postscript=.|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002296799&L=1|hdl-access=free}}</ref><ref>{{Citation|authorlink1author-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|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.|authorlinkauthor-link=Pyotr Novikov|year=1955|title=On the algorithmic unsolvability of the word problem in group theory|language=Russianru| 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.| authorlinkauthor-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}}</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 260:

*{{planetmath reference|id=8301|title=Word problem}}

* W. W. Boone, F. B. Cannonito, and [[Roger Lyndon|R. C. Lyndon]]. ''Word Problems: Decision Problem in Group Theory.'' Netherlands: North-Holland. 1973.

* {{cite journal | last1 = Boone | first1 = W. W. | last2 = Higman | first2 = G. | year = 1974 | title = An algebraic characterization of the solvability of the word problem | url = | journal = J. Austral. Math. Soc. | volume = 18 | issue = | pages = 41–53 | doi=10.1017/s1446788700019108| doi-access = free }}

* {{cite journal | last1 = Boone | first1 = W. W. | last2 = Rogers Jr | first2 = H. | year = 1966 | title = On a problem of J. H. C. Whitehead and a problem of Alonzo Church | url = | journal = Math. Scand. | volume = 19 | issue = | pages = 185–192 | doi=10.7146/math.scand.a-10808| doi-access = free }}

*{{Citation | last1=Borisov | first1=V. V. | title=Simple examples of groups with unsolvable word problem | mr=0260851 | year=1969 | journal=Akademiya Nauk SSSR. Matematicheskie Zametki | issn=0025-567X | volume=6 | pages=521–532}}

* {{Citation | last1=Collins | first1=Donald J. | title=Word and conjugacy problems in groups with only a few defining relations | mr=0263903 | year=1969 | journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | volume=15 | issue=20–22 | pages=305–324 | doi=10.1002/malq.19690152001}}

Line 272:

* 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 | url = | journal = Bulletin of the AMS | volume = 6 | issue = | pages = 33–56 | doi=10.1090/s0273-0979-1982-14963-1| doi-access = free }}

{{DEFAULTSORT:Word Problem For Groups}}