= Solution
The allowed algebraic characterization is the <Boone-Higman theorem>:
$$
\boxed{G\text{ finitely generated has soluble word problem}
\ \Longleftrightarrow\ G\hookrightarrow S\hookrightarrow P,
\quad S\text{ simple},\quad P\text{ finitely presented}.}
$$
The <simple group> $S$ need not itself be finitely presented. The primary statement is Theorem I of https://www.cambridge.org/core/journals/journal-of-the-australian-mathematical-society/article/an-algebraic-characterization-of-groups-with-soluble-word-problem1/748FFD937CEA3727E812C8CDB9CC59B9[An algebraic characterization of groups with soluble word problem]. In particular, a finitely generated <group> with insoluble <word problem for a group> cannot embed in any finitely presented simple group: otherwise take that group as both $S$ and $P$ in the characterization.
Use the following effective form of the permitted <Messuage lemma for groups>. Given a <finite group presentation> of $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ implies $K_w=1$, while $w\ne1$ implies that $K$ embeds in $K_w$. The construction is performed without first deciding whether $w$ is trivial. A collapse-and-embedding lemma with these properties is also stated as Lemma 5.13 in https://www.macs.hw.ac.uk/~lc45/Teaching/kggt/miller.pdf[Combinatorial Group Theory]. No proof of that allowed lemma is needed here.
Fix a finitely presented <group> $U$ with insoluble <word problem for a group>, whose existence is allowed. For each input word $w$ in its generators, construct $U_w$ by the lemma and then form the finite presentation of
$$
P_w=U_w*C_2.
$$
If $w=1$, then $P_w\cong C_2$, which is a nontrivial <simple group>. If $w\ne1$, the lemma embeds $U$ in $U_w$, and the <normal form theorem for a free product> embeds $U_w$ in $P_w$. If $P_w$ were simple, it would be a finitely presented simple group containing $U$, contradicting the characterization. Hence
$$
\boxed{P_w\text{ is simple}\ \Longleftrightarrow\ w=1\text{ in }U.}
$$
An algorithm deciding simplicity from arbitrary finite presentations would therefore solve the insoluble <word problem for a group> in $U$. This proves \b[simplicity of finitely presented groups is algorithmically undecidable]. Using $C_2$ avoids any convention about whether the trivial group is called simple.
Back to article page
