Skip to main content
3 of 6
added 1209 characters in body; added 81 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

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.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k