Skip to main content
3 of 3
edited tags
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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.

dan
  • 41
  • 1