MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

6 added 1085 characters in body

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.

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.

5 added 248 characters in body

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}$ power 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.

4 Updated with better, direct construction; added 75 characters in body

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

There is such a universal computable group as you request.

First, consider a one-dimensional version of Let $F$be the problem. In this case, we may produce an abelian free group , isomorphic toan infinite direct sum of $\mathbb{Z}/k\mathbb{Z}$'s and$\mathbb{Z}$'s, with on infinitely many copies of each typegenerators $\langlea_p\rangle_p$, and exhibiting the completeness property you request in indexed by the one-generator case.

For each Turing machine program programs $p$, letp$. Let$G_p=\mathbb{Z}/k\mathbb{Z}$, if 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, and otherwise $G_p=\mathbb{Z}$. We may think of $G_p$ asgenerated by an element that comes to have finite order exactly atthe same stage, if any, that the computation halts.Thus,

Let us represent the group$G_p$ is cyclic, either finite or infinite, depending on whether$p$ halts.

The intended final group $G$ will be isomorphic to by reduced words in the direct sum generators$\oplus_p G_p$a_p$and their inverses, but we must take care to choose a representation for which in the group is computable. We shall represent elements of$G$with finite sequences ofintegers, with case that we took the quotientby$p^{th}$coordinate providing an element ofa_p^k$, then in these words we use exponents on $G_p$, and using coordinate-wise group operations. This will makethe group operation computable. To make a_p$in the inverse interval$x\mapsto -x$acomputable operation, however(-k/2,k/2]$. First of all, it will not work we can computably recognize whether aword 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$.Insteadgenerators fits this description, we simply straddle by checkingwhether it is reduced and whether any of the elements at $0$, so exponents is toolarge. The point of this last issue is that we can tell if $G_p=\mathbb{Z}/k\mathbb{Z}$ and theexponent $k$ a_p^r$is odd$2r+1$, then werepresent it using$\{-r,\ldots,-1,0,1,2,\ldots,r\}$, and too large by checking if program$k=2r$, then use p$ halts in$\{-r+1,\ldots,-1,0,1,2,\ldots,r\}$. The pointnow is that 2r$steps or not. Similarly, we can easily compute the inverse$x\mapsto -x$withoutknowing the size ofa word from the group. The group operation itself iscomputable in this representationword, since and we can add elements in this group andsimultaneously check whether the program halts in that same sizescalecomputably multiply words. Again,in order to know whether we've overspilled whenever we have a word with some new exponents on the boundary andwe need to simplify the representation modulo$k$. Thuscheck whether they reduce because of our quotient,$G$andthis is represented possible by finite sequences of integersrunning the relevant computation for sufficientnumber to steps to determine it. Thus, where oncoordinate$p$we have either the full integers$\mathbb{Z}$or thegroup consisting of the$k$integers centered at$0$, with additionmodulo$k$. This is a computable group in representation of the sense you requested.group$G$. Finally, I claim that it is complete universal in the sense you requested, for the one-dimensional version of the question, since for .Given any Turing machine program$p$, we may produce the element$1_p$of$G$, namely, theelement 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 x_p=a_p$ and let$x_p=1_q$ y_p=a_q$for some different other program$q$known not to halt. Thus, 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 questionbydesign, which you actually asked. We shall simply modify the construction, and let group generated by$G_p$x_p,y_p$ will be the free group ontwo 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$, if and this is free just in case only if $p$ does not halt.

Perhaps the best way to view the answer is

Lastly, let me observe that we may produce a 2-generated computable my 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 examplefinitely generated, andit may be interesting to have a finitely generated example, or evena finitely presented computable group with the completeness properties you desiredexample.