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.)
Best Answer
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.