Groups And Graphs
Alessandra Carbone, Stephen Semmes · 2000
Abstract A fundamental class of examples of implicit descriptions of large objects in mathematics is provided by finitely-presented groups, A finite presentation is given by a finite set of generators and a finite set of relations, but then the resulting group can be an infinite object which may be quite complicated. In particular, the word problem — deciding whether a particular expression in the generators represents the identity element in the group is algorithmically undecidable for many finitely-presented groups. (See [Man77], for instance.)