This question pops up constantly when I visit the site, and I'm not sure the answers are very natural groups since halting properties of Turing machines are mentioned when the group is constructed, so I'll give this somewhat belated answer.

If we take "natural" to just mean that the group arises from a natural action on some natural objects, and was not defined just for the purpose of a decidability problem, then there are plenty of examples. First off, I would not be surprised if this problem is undecidable even in something as natural as right-angled Artin groups or linear groups, e.g. for $F_2 \times F_2$ it reminds one of PCP (I'm not sure it's quite the same as what one calls PCP in groups though). It would be interesting if experts could comment, I don't know an official name for this problem (I suggest one below) so it's hard to search for it.

In the meantime, I'll present a cellular automaton solution, mostly based on my own research since it's what I know best.

Pick $A$ to be an alphabet of any composite cardinality except $|A| \neq 4$, and pick a Cartesian product decomposition $A = B \times C$. On $A^{\mathbb{Z}}$, we define the following finite set of homeomorphisms:

• For all $\pi \in \mathrm{Sym}(A)$, let $f_{\pi} : A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ apply $\pi$ cellwise, meaning $f_{\pi}(x)_i = \pi(x_i)$. Let $F \cong \mathrm{Sym}(A)$ be the group of such $f_{\pi}$.

• $\sigma_1 : A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ is defined by identifying $x \in A^{\mathbb{Z}}$ with $(y, z) \in B^{\mathbb{Z}} \times C^{\mathbb{Z}}$ in the obvious way, and defining $\sigma_1(y, z) = (\sigma(y), z)$ where $\sigma(y)_i = y_{i+1}$ is the left shift.

Definition. Let $G = \langle F, \sigma_1 \rangle$ be the group the above maps generate.

In other words, $G$ is the group of homeomorphisms on infinite sequences of symbols from $B \times C$, which are generated by shifting the first track, and permuting the individual symbols (by any permutation of the set $B \times C$). The group $G$ is a subgroup of the reversible cellular automata, i.e. the shift-commuting self-homeomorphisms of $\mathrm{Aut}(A^{\mathbb{Z}})$, and thus is a computable group. The bit string can be taken to be the minimal local rule of the CA.

I think the terminology "is a universal Turing machine" is not very descriptive, I think this property can be stated in standard terms, if we take the "free group problem" for a group to be the problem of, given two elements, deciding whether they generate a nonabelian free group (equivalently, freely generate one).

Theorem. The group $G$ has $\Pi^0_1$-complete free group problem under many-one reductions. Thus, it is a universal Turing machine in the sense of the question.

Proof. The following things are known:

• Given a Turing machine, you can construct a reversible cellular automaton in $\mathrm{Aut}(D^{\mathbb{Z}})$ for some $D$, such that the latter is periodic if and only if the Turing machine halts. This is proved in [1].

• There is an effective embedding $\phi : \mathrm{Aut}(D^{\mathbb{Z}}) * \mathrm{Aut}(D^{\mathbb{Z}}) \to \mathrm{Aut}(D^{\mathbb{Z}})$. This is proved in [2].

• Let $f_1, ..., f_k \in \mathrm{Aut}(D^{\mathbb{Z}})$, for any finite alphabet $D$. Then you can (effectively) construct an embedding $\psi : \langle f_1,...,f_k \rangle \to G$. This is proved in the preprint [3].

Combining these, given Turing machine $T$, using the first point above construct a reversible cellular automaton $f_T$ which is periodic iff $T$ halts. Then, using the second point above construct $\phi(f_T, \mathrm{id})$ and $\phi(\mathrm{id}, f_T)$. Then the group $H = \langle \psi(\phi(f_T, \mathrm{id})), \psi(\phi(\mathrm{id}, f_T)) \rangle \leq G$ is free if $T$ never halts, while if $T$ halts, $H$ is not even torsion-free. End of proof.

In general if $G * G \to H$ by an effective construction and $G$ has undecidable torsion problem, then the free group problem is undecidable for $H$.

About some other groups:

• For any uncountable sofic shift $X \subset A^{\mathbb{Z}}$, the automorphism group has undecidable free group problem. This follows easily from the above and [2]. (For countable sofics, this problem is decidable.)

• For the topological full group of the full shift $A^{\mathbb{Z}}$, I have thought about this problem quite a bit, and I don't know if it's decidable. It should not be hard to show (using the results of [4]) that at least for the topological full group of $A^{\mathbb{Z}^d}$ with $d \geq 3$, this problem is undecidable. I am not sure about dimension $2$.

• For automata groups (and the bigger group of all reversible transducers [5]), this problem is undecidable. Namely, there is an automata group $G$ where the torsion problem is undecidable [6, 7], and $G * G \to H$ for some other automata group $H$ [8], so this problem will be undecidable for $H$.

• For the group of reversible Turing machines in the sense of [4], I don't know if the group's free product with itself embeds in it, but I think it shouldn't be hard to show this is undecidable using undecidability of the torsion problem. I didn't try it though.

This idea will not work in groups where the order problem is decidable, which limits how natural an example one can find this way.

References

[1] Kari, Jarkko; Ollinger, Nicolas, Periodicity and immortality in reversible computing, Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 419-430 (2008). ZBL1173.68521.

[2] Salo, Ville, A note on subgroups of automorphism groups of full shifts, Ergodic Theory Dyn. Syst. 38, No. 4, 1588-1600 (2018). ZBL1390.37021.

[3] Salo, Ville, Universal groups of cellular automata, https://arxiv.org/abs/1808.08697

[4] Barbieri, Sebastián; Kari, Jarkko; Salo, Ville, The group of reversible Turing machines, Cook, Matthew (ed.) et al., Cellular automata and discrete complex systems. 22nd IFIP WG 1.5 international workshop, AUTOMATA 2016, Zurich, Switzerland, June 15–17, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39299-8/pbk; 978-3-319-39300-1/ebook). Lecture Notes in Computer Science 9664, 49-62 (2016). ZBL1350.68101.

[5] Grigorchuk, R. I.; Nekrashevich, V. V.; Sushchanskii, V. I., Automata, dynamical systems, and groups, Grigorchuk, R.I. (ed.), Dynamical systems, automata, and infinite groups. Transl. from the Russian. Moscow: MAIK Nauka/Interperiodica Publishing. Proc. Steklov Inst. Math. 231, 128-203 (2000); translation from Tr. Mat. Inst. Steklova 231, 134-214 (2000). ZBL1155.37311.

[6] Gillibert, Pierre, An automaton group with undecidable order and Engel problems, ZBL06824269.

[7] Bartholdi, Laurent; Mitrofanov, Ivan, https://arxiv.org/abs/1710.10109

[8] Fedorova, Mariia; Oliynyk, Andriy, Finite automaton actions of free products of groups, Algebra Discrete Math. 23, No. 2, 230-236 (2017). ZBL1375.20028.