# an example of a semigroup with solvable word problem but unsolvable power problem

We say that a semigroup $S$ has solvable power problem if there is an algorithm that takes as input an element $s \in S$ and decides whether or not there exist $m,n \in \mathbb{N}$ with $m \neq n$ and $s^m=s^n$.

Does anybody know an "easy" (like finitely presented with relatively few relations) example of a semigroup with solvable word problem but unsolvable power problem?

I would also be interested in an example of a group with solvable word problem but unsolvable power problem, if anybody has such an example.

• The power problem asks for every $a,b$ whether $b=a^n$ for some $n$. It is not the same as what you wrote. In the case of groups your problem is known as the order problem (find out if an element is of finite order). – user6976 Apr 11 '11 at 18:23

The only known way to construct this example (say, in the case of groups, the case of semigroups is similar) is the following. First consider the free Abelian group $F$ with free generators $a_1,a_2,...$. Pick a recursively enumerable non-recursive set $I$ and impose relations $a_n^{m!}=1$ if $n$ is the $m$th number from $I$ (we assume that there exists a computer that lists numbers in $I$ in some order one by one). That group, call it $A$, has solvable word problem. Indeed, consider any word $w=a_{i_1}^{k_1}\ldots a_{i_s}^{k_s}.$ That word is equal to 1 in $A$ iff each $k_i$ is divisible by $m!$ such that $a_i$ is the $m$-th number in $I$. That gives restriction to $m$. So given $w$ we start the computer that lists $I$ and wait till we have the first (not in the natural order!) $k_1+...+k_s$ numbers from $I$ listed. The power problem in $A$ is not decidable of course. Since $A$ has solvable word problem, by Higman's theorem, it embeds into a finitely presented group $G$. By Clapham's theorem, we can assume that $G$ has decidable word problem. But the power (order) problem in $G$ is not decidable.