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