11
$\begingroup$

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

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

Question 1. 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?

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

Of course I'm interested in algorithms which output YES on a possibly big set of Turing machines.

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

$\endgroup$
1
  • 2
    $\begingroup$ In your conditions (1)–(3), don’t you also need (4) closed under inverse (defined in the natural way) and (5) L is nonempty? For example, I do not think that your conditions (1)–(3) rule out the language L which corresponds to the semigroup generated by the elements conjugate to g_1. $\endgroup$ Jul 20, 2011 at 20:09

5 Answers 5

16
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

There are the so-called Miller machines (see my paper ). 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$.

$\endgroup$
3
$\begingroup$

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.

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

So this gives a partial positive answer to Question 1.

$\endgroup$
3
$\begingroup$

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

D. W. Parkes and R. M. Thomas, Groups with context-free reduced word problem, Communications in Algebra 30 (2002), 3143–3156.

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:

(1) For any $\alpha \in \Sigma^*$ there exists $\beta \in \Sigma^*$ with $\alpha\beta \in W$.

(2) If $\alpha,\beta,\gamma \in \Sigma^*$ with $\alpha\beta\gamma \in W$ and $\beta \in W$, then $\alpha\gamma \in W$.

Even if you add closure under inversion to your conditions, then it is not clear that they imply (1) and (2).

I would guess that Andreas Blass' negative answer still applies to the conditions (1) and (2).

$\endgroup$
2
$\begingroup$

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:

Stephen R. Laken and Richard M. Thomas, Space Complexity and Word Problems of Groups, Groups-Complexity-Cryptology Volume 1 (2009), No. 2, 261-273

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^{*}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.