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.
No comments:
Post a Comment