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

semigroupgenerated by the elements conjugate to g_1. – Tsuyoshi Ito Jul 20 '11 at 20:09