# Membership problem in monoids

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.

• 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. – Tsuyoshi Ito Aug 29 '10 at 22:35
• I should clarify: I'm talking about a monoid presentation, and a monoid that is not a group would be appreciated. – user8877 Aug 30 '10 at 1:12
• 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.) – Tsuyoshi Ito Aug 30 '10 at 1:20
• 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. – 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.