Return to 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.

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.

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.

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 the $k^{th}$ power $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]$. 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.

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.

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.

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.

There is such a universal computable group.

First, consider a one-dimensional version of the problem. In this case, we may produce an abelian group, isomorphic to an infinite direct sum of $\mathbb{Z}/k\mathbb{Z}$'s and $\mathbb{Z}$'s, with infinitely many copies of each type, and exhibiting the completeness property you request in the one-generator case.

For each Turing machine program $p$, let $G_p=\mathbb{Z}/k\mathbb{Z}$, if $p$ halts (on trivial input) in $k$ steps, and otherwise $G_p=\mathbb{Z}$. We may think of $G_p$ as generated by an element that comes to have finite order exactly at the same stage, if any, that the computation halts. Thus, the group $G_p$ is cyclic, either finite or infinite, depending on whether $p$ halts.

The intended final group $G$ will be isomorphic to the direct sum $\oplus_p G_p$, but we must take care to choose a representation for which the group is computable.

We shall represent elements of $G$ with finite sequences of integers, with the $p^{th}$ coordinate providing an element of $G_p$, and using coordinate-wise group operations. This will make the group operation computable. To make the inverse $x\mapsto -x$ a computable operation, however, it will not work in the case $G_p$ is finite to represent $G_p=\mathbb{Z}/k\mathbb{Z}$ using $\{0,1,\ldots,k\}$, since we cannot compute $k$ from $p$. Instead, we simply straddle the elements at $0$, so that if $G_p=\mathbb{Z}/k\mathbb{Z}$ and $k$ is odd $2r+1$, then we represent it using $\{-r,\ldots,-1,0,1,2,\ldots,r\}$, and if $k=2r$, then use $\{-r+1,\ldots,-1,0,1,2,\ldots,r\}$. The point now is that we can compute the inverse $x\mapsto -x$ without knowing the size of the group. The group operation itself is computable in this representation, since we can add elements in this group and simultaneously check whether the program halts in that same size scale, in order to know whether we've overspilled the boundary and need to simplify the representation modulo $k$.

Thus, $G$ is represented by finite sequences of integers, where on coordinate $p$ we have either the full integers $\mathbb{Z}$ or the group consisting of the $k$ integers centered at $0$, with addition modulo $k$. This is a computable group in the sense you requested.

Finally, it is complete in the sense you requested, for the one-dimensional version of the question, since for any Turing machine program $p$, we may produce the element $1_p$ of $G$, namely, the element with $1$ on coordinate $p$ and $0$ on other coordinates. The point is that $p$ fails to halt on trivial input if and only if $1_p$ generates the infinite cyclic group.

This group can be used for the abelian two-dimensional version of the question, since if you let $y_p=1_p$ in my group above and let $x_p=1_q$ for some different program $q$ known not to halt, then $p$ fails to halt if and only if $x_p,y_p$ generate a free abelian group in $G$.

But consider now the full two-dimensional version of the question, which you actually asked. We shall simply modify the construction, and let $G_p$ be the free group on two generators, if $p$ fails to halt, but if $p$ halts in $k$ steps, then we use the quotient of this free group by the $k^{th}$ power of one of the generators. Both of these groups are (uniformly) computably representable, using a reduced word representation, combined with the trick above of centering at $0$, in order that we need not know whether we have taken the quotient or not in order to compute the inverse of a word. Now, the point is that for any program $p$, we may map it to the generators of $G_p$, and this is free just in case $p$ does not halt.

Perhaps the best way to view the answer is that we may produce a 2-generated computable group $G_p$, uniformly in $p$, such that $G_p$ is a free group on two generators if and only if $p$ fails to halt.

I take this answer to be not really what you wanted. It would be much better, for example, to have a finitely generated or even a finitely presented computable group with the completeness properties you desired.

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 the $k^{th}$ power $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]$. 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.

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.