= Solution
Take a <recursively enumerable set> $S\subseteq\mathbb N_{>0}$ that is not recursive, for example the diagonal halting set from Question 2 shifted by one. To obtain a <finitely generated group> with recursive presentation but undecidable <word problem for a group>, first define the countable <Right-angled Artin group>
$$
B_S=\langle a_i\ (i\in\mathbb Z)\mid[a_i,a_j]=1\text{ whenever }|i-j|\in S\rangle.
$$
Translation of the indices gives an <automorphism> $a_i\mapsto a_{i+1}$. The <semidirect product> with its infinite cyclic shift is generated by $a=a_0,t$ and has presentation
$$
G_S=\langle a,t\mid[a,t^nat^{-n}]=1\ (n\in S)\rangle.
$$
To verify this presentation, the semidirect product satisfies its relators, while the reverse map sends $a_i$ to $t^iat^{-i}$; all translated commutation relations follow by conjugation. These maps are inverse on their generators. Thus $B_S$ embeds in $G_S$.
For $n\in S$, the word $[a_0,a_n]$ is trivial. For $n\notin S$, map $a_0,a_n$ to the free generators $x,y$ of $F(x,y)$ and every other $a_i$ to one. Every defining commutator of $B_S$ maps to one, since the only possible relation involving both surviving generators would have separation $n$, which is absent. The resulting <group homomorphism> sends $[a_0,a_n]$ to the nontrivial reduced word $[x,y]$. Hence
$$
\boxed{[a,t^nat^{-n}]=1\text{ in }G_S\quad\Longleftrightarrow\quad n\in S.}
$$
This proves the <shift-invariant graph groups encode arbitrary sets> construction rather than supposing that a missing relator automatically means a nontrivial word. A word algorithm for $G_S$ would decide $S$, so none exists. Since $S$ is enumerable, the displayed two-generator presentation is a <recursive presentation of a group>. By the <Higman embedding theorem>, $G_S$ embeds in a finitely presented group $G_0$. A word algorithm for $G_0$, composed with substitution of the two fixed generator-image words, would solve the word problem for $G_S$. Therefore \b[$\boxed{G_0\text{ is finitely presented with insoluble word problem}}$.]
Back to article page
