MathOverflow

Return to Question

deleted 2 characters in body; added 188 characters in body
Source Link
Terry Tao
Terry Tao
  • 106k
  • 28
  • 421
  • 505

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
  • 106k
  • 28
  • 421
  • 505

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

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.