Revisions - MathOverflow

Return to Answer

added 1085 characters in body

view source

edited Feb 14 2012 at 0:51

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.

added 248 characters in body

view source

edited Feb 13 2012 at 22:37

Joel David Hamkins
76.8k●8●192●355

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.

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

view source

edited Feb 13 2012 at 22:26

Joel David Hamkins
76.8k●8●192●355

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.

added 1209 characters in body; added 81 characters in body

view source

edited Feb 13 2012 at 21:35

Joel David Hamkins
76.8k●8●192●355

Here

There is such a universal computable group.

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

Finally, it is complete in the sense you requested, for the one-dimensional version of the question, since for any

I realize that you asked about two words $x_p$ and $y_p$, whereas Ineeded only one. If you really want two

This group can be used for the abelian two-dimensional version of the question, then just since if you let $y_p=1_p$ in my group above , and let $x_p$ be $1_q$ x_p=1_q$ for a some different program $q$,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.

This We shall simply modify the construction, and let $G_p$ be the free group is 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 finitely generatedknow 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 you this is free just in case $p$ does not halt.

Perhaps the best way to view the answer is that we may want 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 change your question halt.

I take this answer to seek 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.

Fixed missing negation

view source

edited Feb 13 2012 at 21:17

Joel David Hamkins
76.8k●8●192●355

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$ halts 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.

view source

answered Feb 13 2012 at 21:03

Joel David Hamkins
76.8k●8●192●355

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.

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$ halts on trivial input if and only if $1_p$ generates the infinite cyclic group.

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