Skip to main content
MathOverflow

Return to Question

deleted 2 characters in body; added 188 characters in body
Source Link
Terry Tao
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

This question was inspired by this blog post of Jordan Ellenberg.

Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the properties that

  • There is an algorithm (by which I mean "Turing machine") which, when given a binary string, can determine whether that string lives in the group $G$ in finite time (i.e. $G$ is a computable set);
  • There is an algorithm which, when given binary strings $x,y$ in $G$, can compute $x^{-1}$ and $xy$ in finite time (i.e. the group laws on $G$ are computable functions).

In the blog post mentioned above, the group $SL_3({\bf Z})$ was discussed, which is certainly an example of a computable group, but one can of course devise many other examples of computable groups. But note that this condition is stronger than being recursively presented, since I am requiring the word problem to be decidable.

Observe that if $G$ is a computable group, then there is an obvious algorithm which, when given any two elements $x,y$ of a $G$ as input, which will halt in finite time if and only if $x,y$ fail to generate a free group, simply by evaluating all the nontrivial words of $x,y$ in turn and checking if any of them are the identity.

My first question is if there is any computable group $G$ which is "Turing complete" in the sense that the halting problem for any Turing machine can be converted into a question of the above form. In other words, there would be an algorithm which, when given a Turing machine $T$, would return (in finite time) a pair $x_T, y_T$ of elements of $G$ with the property that $x_T, y_T$ generate a free group in $G$ if and only if $T$ does not halt in finite time. Or more informally: can a group be a universal Turing machine?

I suspect the answer to this question is "yes", by doing something like taking G to be something like the group of reversibly computable operations on an infinite string of bits, though I wasn't able to quite push through the details. One might also modify the question by taking G to be a computable semigroup rather than a computable group, though I think this should not make too substantial of a difference.

My second (and more vague) question is whether one can take $G$ to be a "non-artificial" group, which can be defined without reference to computability or Turing machines. (For instance, a group which is somehow constructed using Diophantine equations would qualify.)

This question was inspired by this blog post of Jordan Ellenberg.

Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the properties that

  • There is an algorithm (by which I mean "Turing machine") which, when given a binary string, can determine whether that string lives in the group $G$ in finite time (i.e. $G$ is a computable set);
  • There is an algorithm which, when given binary strings $x,y$ in $G$, can compute $x^{-1}$ and $xy$ in finite time (i.e. the group laws on $G$ are computable functions).

In the blog post mentioned above, the group $SL_3({\bf Z})$ was discussed, which is certainly an example of a computable group, but one can of course devise many other examples of computable groups. But note that this condition is stronger than being recursively presented, since I am requiring the word problem to be decidable.

Observe that if $G$ is a computable group, then there is an obvious algorithm which, when given any two elements $x,y$ of a $G$ as input, which will halt in finite time if and only if $x,y$ fail to generate a free group, simply by evaluating all the nontrivial words of $x,y$ in turn and checking if any of them are the identity.

My first question is if there is any computable group $G$ which is "Turing complete" in the sense that the halting problem for any Turing machine can be converted into a question of the above form. In other words, there would be an algorithm which, when given a Turing machine $T$, would return (in finite time) a pair $x_T, y_T$ of elements of $G$ with the property that $x_T, y_T$ generate a free group in $G$ if and only if $T$ does not halt in finite time. Or more informally: can a group be a universal Turing machine?

I suspect the answer to this question is "yes", by doing something like taking G to be something like the group of computable operations on an infinite string of bits, though I wasn't able to quite push through the details.

My second (and more vague) question is whether one can take $G$ to be a "non-artificial" group, which can be defined without reference to computability or Turing machines. (For instance, a group which is somehow constructed using Diophantine equations would qualify.)

This question was inspired by this blog post of Jordan Ellenberg.

Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the properties that

  • There is an algorithm (by which I mean "Turing machine") which, when given a binary string, can determine whether that string lives in the group $G$ in finite time (i.e. $G$ is a computable set);
  • There is an algorithm which, when given binary strings $x,y$ in $G$, can compute $x^{-1}$ and $xy$ in finite time (i.e. the group laws on $G$ are computable functions).

In the blog post mentioned above, the group $SL_3({\bf Z})$ was discussed, which is certainly an example of a computable group, but one can of course devise many other examples of computable groups. But note that this condition is stronger than being recursively presented, since I am requiring the word problem to be decidable.

Observe that if $G$ is a computable group, then there is an obvious algorithm which, when given any two elements $x,y$ of $G$ as input, which will halt in finite time if and only if $x,y$ fail to generate a free group, simply by evaluating all the nontrivial words of $x,y$ in turn and checking if any of them are the identity.

My first question is if there is any computable group $G$ which is "Turing complete" in the sense that the halting problem for any Turing machine can be converted into a question of the above form. In other words, there would be an algorithm which, when given a Turing machine $T$, would return (in finite time) a pair $x_T, y_T$ of elements of $G$ with the property that $x_T, y_T$ generate a free group in $G$ if and only if $T$ does not halt in finite time. Or more informally: can a group be a universal Turing machine?

I suspect the answer to this question is "yes", by doing something like taking G to be something like the group of reversibly computable operations on an infinite string of bits, though I wasn't able to quite push through the details. One might also modify the question by taking G to be a computable semigroup rather than a computable group, though I think this should not make too substantial of a difference.

My second (and more vague) question is whether one can take $G$ to be a "non-artificial" group, which can be defined without reference to computability or Turing machines. (For instance, a group which is somehow constructed using Diophantine equations would qualify.)

Source Link
Terry Tao
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

Can a group be a universal Turing machine?

This question was inspired by this blog post of Jordan Ellenberg.

Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the properties that

  • There is an algorithm (by which I mean "Turing machine") which, when given a binary string, can determine whether that string lives in the group $G$ in finite time (i.e. $G$ is a computable set);
  • There is an algorithm which, when given binary strings $x,y$ in $G$, can compute $x^{-1}$ and $xy$ in finite time (i.e. the group laws on $G$ are computable functions).

In the blog post mentioned above, the group $SL_3({\bf Z})$ was discussed, which is certainly an example of a computable group, but one can of course devise many other examples of computable groups. But note that this condition is stronger than being recursively presented, since I am requiring the word problem to be decidable.

Observe that if $G$ is a computable group, then there is an obvious algorithm which, when given any two elements $x,y$ of a $G$ as input, which will halt in finite time if and only if $x,y$ fail to generate a free group, simply by evaluating all the nontrivial words of $x,y$ in turn and checking if any of them are the identity.

My first question is if there is any computable group $G$ which is "Turing complete" in the sense that the halting problem for any Turing machine can be converted into a question of the above form. In other words, there would be an algorithm which, when given a Turing machine $T$, would return (in finite time) a pair $x_T, y_T$ of elements of $G$ with the property that $x_T, y_T$ generate a free group in $G$ if and only if $T$ does not halt in finite time. Or more informally: can a group be a universal Turing machine?

I suspect the answer to this question is "yes", by doing something like taking G to be something like the group of computable operations on an infinite string of bits, though I wasn't able to quite push through the details.

My second (and more vague) question is whether one can take $G$ to be a "non-artificial" group, which can be defined without reference to computability or Turing machines. (For instance, a group which is somehow constructed using Diophantine equations would qualify.)