word problem

《Lecture Notes on Bayesian Estimation and Classification》 · 第 54 页 · Section 2.2「Presentations of Groups」，小节「The Word Problem」

Suppose that $G$ is a finitely presented group with generators $x_1,\ldots,x_n$ and relators $r_1,\ldots,r_k$. Here the $r_i$ are assumed to be explicitly given words in the $x_i$. The word problem is said to be soluble for the presentation if there is an algorithm which, when a word $w$ in the $x_i$ is given, decides whether or not $w$ is a relator, i.e., whether $w=1$ in $G$.