Can a group be a universal Turing machine?

Question

This question was inspired by this blog post of Jordan Ellenberg.

Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the properties that

• There is an algorithm (by which I mean "Turing machine") which, when given a binary string, can determine whether that string lives in the group $G$ in finite time (i.e. $G$ is a computable set);
• There is an algorithm which, when given binary strings $x,y$ in $G$, can compute $x^{-1}$ and $xy$ in finite time (i.e. the group laws on $G$ are computable functions).

In the blog post mentioned above, the group $SL_3({\bf Z})$ was discussed, which is certainly an example of a computable group, but one can of course devise many other examples of computable groups. But note that this condition is stronger than being recursively presented, since I am requiring the word problem to be decidable.

Observe that if $G$ is a computable group, then there is an obvious algorithm which, when given any two elements $x,y$ of $G$ as input, which will halt in finite time if and only if $x,y$ fail to generate a free group, simply by evaluating all the nontrivial words of $x,y$ in turn and checking if any of them are the identity.

My first question is if there is any computable group $G$ which is "Turing complete" in the sense that the halting problem for any Turing machine can be converted into a question of the above form. In other words, there would be an algorithm which, when given a Turing machine $T$, would return (in finite time) a pair $x_T, y_T$ of elements of $G$ with the property that $x_T, y_T$ generate a free group in $G$ if and only if $T$ does not halt in finite time. Or more informally: can a group be a universal Turing machine?

I suspect the answer to this question is "yes", by doing something like taking G to be something like the group of reversibly computable operations on an infinite string of bits, though I wasn't able to quite push through the details. One might also modify the question by taking G to be a computable semigroup rather than a computable group, though I think this should not make too substantial of a difference.

My second (and more vague) question is whether one can take $G$ to be a "non-artificial" group, which can be defined without reference to computability or Turing machines. (For instance, a group which is somehow constructed using Diophantine equations would qualify.)

Answer 1

Update. Here is a more direct construction. (See edit history for previous version.)

There is such a universal computable group as you request. Let $F$ be the free group on infinitely many generators $\langle a_p\rangle_p$, indexed by the Turing machine programs $p$. Let $G$ be the quotient of this group by all the $k^{th}$ powers $a_p^k$, whenever the program $p$ halts (on trivial input) in exactly $k$ steps.

Let us represent the group $G$ by reduced words in the generators $a_p$ and their inverses, but in the case that we took the quotient by $a_p^k$, then in these words we use exponents on $a_p$ in the interval $(-k/2,k/2]$. (The reason for using this exponent format is that if we were to use only the positive powers of the finite-order generators, then we wouldn't be able to compute inverses in $G$, since we cannot compute whether $a_p$ has finite order or not.) First of all, we can computably recognize whether a word in the generators fits this description, simply by checking whether it is reduced and whether any of the exponents is too large. The point of this last issue is that we can tell if the exponent $a_p^r$ is too large by checking if program $p$ halts in $2r$ steps or not. Similarly, we can easily compute the inverse of a word from the word, and we can computably multiply words. Again, whenever we have a word with some new exponents on the generators, we need to check whether they reduce because of our quotient, and this is possible by running the relevant computation for sufficient number to steps to determine it.

Thus, we have a computable representation of the group $G$.

Finally, I claim that it is universal in the sense you requested. Given any Turing machine program $p$, let $x_p=a_p$ and let $y_p=a_q$ for some other program $q$ known not to halt. Thus, by design, the group generated by $x_p,y_p$ will be the free group on these generators if and only if $p$ does not halt.

An essentially equivalent presentation of the group can be made without reference to Turing machines or computations, but only to Diophantine equations, simply by using the Diophantine representation of the universal Turing machine. That is, since every c.e. set is the solution set of a Diophantine equation, there is a fixed Diophantine equation $d(y,\vec x)=0$, such that Turing machine program $p$ halts on trivial input if and only if $d(p,\vec x)=0$ has a solution in the integers, viewing the program as its Gödel code. So we may define the group $G$ as above, with infinitely many generators $a_n$, but taking the quotient by $a_n^k$, if $k$ is the size of the smallest integer solution of $d(n,\vec x)=0$. I'm not sure this makes the group "natural," (and my opinion is that this word has no robust, coherent mathematical meaning), but it does omit any mention of Turing machines, using instead a fixed Diophantine equation.

Lastly, let me observe that my group is not finitely generated, and it may be interesting to have a finitely generated example, or even a finitely presented example. I suspect that one can apply one of the embedding theorems to place this example into a finitely generated or even finitely presented group.

Answer 2

If I've followed this thread correctly, then there is still a question of whether a finitely presented example can be constructed. This follows from standard facts.

Specifically, let $G=G_0$ be the group constructed by Joel or Jason. By the standard Higman--Neumann--Neumann argument, $G_0$ embeds into a finitely generated group $G_1$ because $G_0$ is countable. It's a fact that $G_1$ is recursively presentable if $G_0$ was. By Higman's Embedding Theorem, $G_1$ can be embedded into a finitely presentable group $G_2$ because $G_1$ is recursively presentable.

The embedding of $G_0$ into $G_1$ is computable, and the embedding of $G_1$ into $G_2$ is obviously computable (since both groups are finitely generated).

Finally, one would like all this to be done so that $G_2$ has solvable word problem. That the Higman Embedding can be made to preserve solvability of the word problem follows from a result of Clapham.

(Strictly speaking, one also needs to check that $G_1$ can be taken to have solvable word problem, as I think Clapham starts with a finitely generated group. This must be well known, but Bridson and I wrote out the details in Section 7 of this paper.)

---

FURTHER

To explain why $G_0\to G_1$ is computable, I need to describe the construction. I'll give one version here, which I think makes the point fairly cleanly. If I recall correctly, it's very similar to the original argument given by Higman, Neuman and Neumann, though they do a little better and get an embedding into a two-generator group. I'll stick with three generators for simplicity.

I'll take $G_0$ to be given by a recursive presentation $\langle (a_m\mid m\in\mathbb{N})\mid (r_n\mid n\in\mathbb{N})\rangle$.

First, note that by replacing $G_0$ with $G_0*\langle x\rangle$ and by replacing each $a_m$ by $a_mx^{m+1}$, I may assume that the $a_m$ are all of infinite order and distinct.

Let

$G_{\frac{1}{2}}=G_0*\langle s\rangle$

and consider the subgroups

$H_M=\langle b_m=s^ma_{m-1}s^{-m}\mid m\geq M\rangle$

for $M\geq 1$. An easy argument with normal forms in free products proves:

Lemma: $H_M$ is free on the given generating set.

Therefore, the assignment $b_m\mapsto b_{m+1}$ defines an isomorphism $\phi:H_1\to H_2$. We can therefore define $G_1$ to be the HNN extension

$G_1=G_{\frac{1}{2}}*_\phi$

which has presentation $\langle G_{\frac{1}{2}},t\mid tht^{-1}=\phi(h)~\forall h\in H_1 \rangle$ (relative to $G_{\frac{1}{2}}$). We now appeal to Britton's Lemma to prove that $G_1$ contains a copy of $G_0$.

Britton's Lemma: The natural map $G_{\frac{1}{2}}\to G_{\frac{1}{2}}*_\phi$ is injective.

But $G_1$ is finitely generated; indeed it's generated by $a_0,s,t$.

The map $G_0\to G_1$ is given recursively by the equations

$a_m=s^{-m}b_ms^m$ and $b_m=tb_{m-1}t^{-1}$.

(Of course, $a_0\mapsto a_0$.) In particular, it's certainly computable.

To prove that the word problem is solvable in $G_1$, you need to argue that you can solve the membership problems for $H_0$ and $H_1$ in $G_\frac{1}{2}$.

Answer 3

I think the answer is yes, there is such a universal group. Let $G$ be the direct sum group $\bigoplus_{n \in \mathbb{N}} G_n$, where $G_n$ is $\mathbb{Z}$ if the $n$th Turing machine does not halt, and $G_n$ is cyclic otherwise. Just construct each $G_n$ by adding $0$, $1$, $-1$, ... until the $n$th Turing machine halts. Then make $G_n$ the smallest cyclic group it could possibly be. The key is that you can run everything in parallel and don't have to define addition (since I am thinking of an Abelian group) when you define the element (for example, $5$ may not be created yet when $2$ and $3$ are). You just have to eventually get around to it.

It is easy to see that you can enumerate the elements of this group, and enumerate the multiplication table. This enumeration can then be turned into the code for each element of the group.

Update: In my construction above, there is only one generator associated with each Turning machine, namely the group element with 1 in the $n$th coordinate, where $n$ is the index of the Turing machine. To have two generators (as was requested), the easiest modification would be to have $G_n$ look like the free group on two elements $a$ and $b$. If the associated Turing machine halts, then make $a$ and $b$ have finite order, leaving the rest free. Again, I think this is similar to Joel's new construction.

(I specialize more in computable analysis than algebra, but I imagine there are a number of standard groups representing the halting problem.)

I am not sure if there is a "natural" such group.

Update: I should also add that usually, when you have a property like that---i.e. you know when it holds, but don't always know when it doesn't hold---then you can make it code a universal Turing machine. Such sentences are called $\Sigma^0_1$ sentences.*

Answer 4

This question pops up constantly when I visit the site, and I'm not sure the second question has been answered, it seems the existing answers do not give 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. (edit: I just noticed Is it decidable whether or not a collection of integer matrices generates a free group? in the comments. So I suppose this is open.)

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.