Which Turing machines accept the language of trivial words in a finitely presented group? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:55:43Z http://mathoverflow.net/feeds/question/66176 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente Which Turing machines accept the language of trivial words in a finitely presented group? Łukasz Grabowski 2011-05-27T12:23:35Z 2011-07-28T11:52:56Z <p>Let $G$ be a finitely presented group with generators $g_1, g_1^{-1},\ldots, g_n, g_n^{-1}$. Let $L(G)$ be the language of all those words in $g_1, \ldots, g_n$ which represent the trivial element of $G$. It's well known that there exists a Turing machine $T$ which accepts $L(G)$ (it doesn't necessary always stop).</p> <p>Conversely, given an alphabet $A$ consisting of symbols $g_1, g_1^{-1}, \ldots, g_n, g_n^{-1}$, and a language $L$ on $A$ accepted by a Turing machine $T$ it's easy to give neccesary and sufficient conditions on $L$ so that for some group $G$ we have $L=L(G)$. Namely $L$ should be closed under (1) concatanation (2) reductions and additions of the terms $g_ig_i^{-1}$ and $g_i^{-1}g_i$, (3) "conjugation" i.e. given $w\in L$ the words $gwg^{-1}$ and $g^{-1}wg$ are also in $L$.</p> <blockquote> <p><strong>Question 1.</strong> Is there a set of conditions on a Turing machine $T$ which assures that the language $L(T)$ accepted by $T$ fulfills the conditions (1)-(3) above?</p> </blockquote> <p>For the purpose of this question "a set of conditions" means an algorithm which always stops, which takes as the input a Turing machine $T$, and if $L(T)$ fulfills (1)-(3) then the algorithm returns YES (if it returns NO then it can be either way).</p> <p>Of course I'm interested in algorithms which output YES on a possibly big set of Turing machines.</p> <blockquote> <p><strong>Question 2.</strong> Is there an algorithm as above which returns YES exactly on the set of those machines $T$ such that $L(T)$ fulfills conditions (1)-(3).</p> </blockquote> http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente/66180#66180 Answer by Andreas Blass for Which Turing machines accept the language of trivial words in a finitely presented group? Andreas Blass 2011-05-27T12:35:56Z 2011-05-27T12:35:56Z <p>The answer to Question 2 is no, by Rice's theorem. The intuitive content of that theorem is that any non-trivial property of the (partial) function computed by a Turing machine will be undecidable as a property of the machine's program.</p> http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente/66192#66192 Answer by David Harris for Which Turing machines accept the language of trivial words in a finitely presented group? David Harris 2011-05-27T14:06:36Z 2011-05-27T14:06:36Z <p>Given a Turing machine $T$, one can close it under the conditions (1), (2), (3) as follows. Given the word $w$, run machine $T$ on $w$ as well as all the words $w'$ obtained by concatenating, reducing, and conjugating. The set of such words $w'$ is recursively enumerable. Then, simply dovetail the computations which correspond to each word $w'$. If any $w'$ acecpts, output YES. Otherwise, the machine runs indefinitely.</p> <p>This process produces a Turing machine $T'$ which is closed under the conditions (1) -- (3). Furthermore, it is easy to check if a given machine $T'$ is produced in this way. (i.e. $T'$ is formed by closing some other machine $T$).</p> <p>So this gives a partial positive answer to Question 1.</p> http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente/69565#69565 Answer by Mark Sapir for Which Turing machines accept the language of trivial words in a finitely presented group? Mark Sapir 2011-07-05T19:17:34Z 2011-07-20T19:28:31Z <p>There are the so-called Miller machines (see <a href="http://front.math.ucdavis.edu/0602.5215" rel="nofollow"> my paper </a>). These are not quite Turing machines, but can be easily converted into Turing machines. It is defined by a collection of words $r_1,...,r_n$. The commands are $q\to r_i^{\pm 1} q$, $q\to aqa^{-1}$ where $a$ is any letter of the alphabet, $q$ is the (only one!) state letter. Unlike a Turing machine, a Miller machine works with words which may contain inverses of the letters, and reduces a word after every step (this is a particular case of the so-called S-machines). The word $w$ is accepted if the machine takes $wq$ to $q$. Clearly the set of words accepted by the Miller machine is exactly the set of words equal to 1 modulo relations $r_i=1$, $i=1,...,n$. </p> http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente/70885#70885 Answer by Derek Holt for Which Turing machines accept the language of trivial words in a finitely presented group? Derek Holt 2011-07-21T08:48:10Z 2011-07-21T08:48:10Z <p>As mentioned in an earlier comment, your conditions for a language to be the word problem of some group do not seem to be complete. In Proposition 3.3 of </p> <p>D. W. Parkes and R. M. Thomas, Groups with context-free reduced word problem, Communications in Algebra 30 (2002), 3143–3156.</p> <p>necessary and sufficient conditions for an arbitrary subset $W$ of the set of words $\Sigma^*$ over a nonempty alphabet $\Sigma$ to be the word problem of a group having $\Sigma$ as monoid generating set are established. These are:</p> <p>(1) For any <code>$\alpha \in \Sigma^*$</code> there exists $\beta \in \Sigma^*$ with $\alpha\beta \in W$.</p> <p>(2) If $\alpha,\beta,\gamma \in \Sigma^*$ with $\alpha\beta\gamma \in W$ and $\beta \in W$, then $\alpha\gamma \in W$.</p> <p>Even if you add closure under inversion to your conditions, then it is not clear that they imply (1) and (2).</p> <p>I would guess that Andreas Blass' negative answer still applies to the conditions (1) and (2).</p> http://mathoverflow.net/questions/66176/which-turing-machines-accept-the-language-of-trivial-words-in-a-finitely-presente/71482#71482 Answer by Sam Jones for Which Turing machines accept the language of trivial words in a finitely presented group? Sam Jones 2011-07-28T11:52:56Z 2011-07-28T11:52:56Z <p>Further to Derek Holt's answer, the negative answer would appear to still apply to the conditions stated in his answer. In fact, you can't even decide if a PDA (let alone a TM) accepts the word problem of a group, as stated in the introduction to:</p> <p>Stephen R. Laken and Richard M. Thomas, Space Complexity and Word Problems of Groups, Groups-Complexity-Cryptology Volume 1 (2009), No. 2, 261-273</p> <p>The proof is simple and relies on the well known fact that one can't decide whether the language a PDA accepts over an alphabet $\Sigma$ is equal to $\Sigma^{*}$</p>