Skip to main content
2 of 6
Fixed missing negation
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Here is such a universal computable group, and it is isomorphic to an infinite direct sum of $\mathbb{Z}/k\mathbb{Z}$'s and $\mathbb{Z}$'s, with infinitely many copies of each type. In particular, it is abelian.

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, 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.

I realize that you asked about two words $x_p$ and $y_p$, whereas I needed only one. If you really want two, then just let $y_p=1_p$ in my group above, and let $x_p$ be $1_q$ for a different program $q$, known not to halt.

This group is not finitely generated, and you may want to change your question to seek a finitely generated group.

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