What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ and $x$ in $S$ as input and decides if $x$ is in the submonoid generated by $s_1,...,s_n$.

Let FG2 denote the free group of rank 2 and FM2 denote the free monoid of rank 2. I know that FG2 x FG2 has undecidable membership problem. Does FM2 x FM2 also have undecidable membership problem? Thanks.

  • 3
    $\begingroup$ The submonoid membership problem for FM2×FM2 is decidable because multiplying two elements in this monoid cannot decrease the length of the word. If the length of x is n and it belongs to the given submonoid, it has to be a product of at most n generators of the submonoid. $\endgroup$ – Tsuyoshi Ito Aug 29 '10 at 22:35
  • $\begingroup$ I should clarify: I'm talking about a monoid presentation, and a monoid that is not a group would be appreciated. $\endgroup$ – user8877 Aug 30 '10 at 1:12
  • $\begingroup$ You should use only one account. Otherwise you lose many features: modifying your own question, posting a comment to an answer to your question, and accepting an answer. See tea.mathoverflow.net/discussion/169/… for how to merge two accounts. (You need to register to do so.) $\endgroup$ – Tsuyoshi Ito Aug 30 '10 at 1:20
  • $\begingroup$ Dan, if you want a monoid that is not a group, then take a group whose subgroup membership problem is not decidable, and add an extra generater having no inverse. Now, you've got a non-group monoid with undecidable membership problem, for the same reason I gave in my answer. $\endgroup$ – Joel David Hamkins Aug 30 '10 at 1:27

A rather nice example is the monoid of $3\times 3$ integer matrices. Its membership problem is unsolvable, indeed so is the problem when $x$ is restricted to be the zero matrix. This is another way to state the unsolvability of the mortality problem for $3\times 3$ integer matrices, previously mentioned in this MO answer.


Every group is a monoid, and if a group has an undecidable subgroup membership problem, then the corresponding submonoid problem will also be undecidable (provided that we can computably produce $s^{-1}$ from $s$, which would be true if the group operation were computable), since if $G$ is a group, then $x$ is in the subgroup generated by $s_1$, ..., $s_n$ if and only if it is in the submonoid generated by $s_1,...,s_n,s_1^{-1},...s_n^{-1}$. Thus, the subgroup membership problem for $G$ reduces to the submonoid membership problem for $G$. If the former is undecidable, then so is the latter.

But I notice that you state your question (in your first paragraph) not in terms of a presentation of the monoid, using words in a presentation, but in terms of the monoid itself, as a raw operation. That is, a literal reading of your question would seem to have us work with a binary operation on a set of natural numbers that makes it a monoid, and we want to decide questions about the nature of that monoid. Thus, your question would seem to belong more to the subject of computable model theory, which is focused entirely on questions of this sort, than to combinatorial group (or monoid) theory. For example, there is a copy of the infinite cyclic group, obtained simply by using a highly non-computable permutation of the integers, where the induced group operation itself is not computable. One can arrange by diagonalization, since there will be only countably many possible queries about submonoid membership, that the submonoid (or subgroup) membership problem for this copy of the monoid is not computable. Since this monoid is just the infinite cyclic group, it is extremely simply as a monoid, but satisfies your undecidability property the way you have stated it. But probably that is not what you mean. If so, you should be more specific about what the input to your decision algorithm is supposed to be.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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