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

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 nonrecursive 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. There are no examples which are given by very few defining relations. The reason is that the solvability of the order problem is not easy to achieve without Higman embedding (I do not know any such way without getting undecidable word problem also) which is very implicit. 

