an example of a semigroup with solvable word problem but unsolvable power problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:20:11Z http://mathoverflow.net/feeds/question/61314 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61314/an-example-of-a-semigroup-with-solvable-word-problem-but-unsolvable-power-problem an example of a semigroup with solvable word problem but unsolvable power problem dan 2011-04-11T18:12:22Z 2011-04-12T02:42:07Z <p>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!</p> http://mathoverflow.net/questions/61314/an-example-of-a-semigroup-with-solvable-word-problem-but-unsolvable-power-problem/61321#61321 Answer by Mark Sapir for an example of a semigroup with solvable word problem but unsolvable power problem Mark Sapir 2011-04-11T18:42:08Z 2011-04-12T02:42:07Z <p>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 <b> some</b> 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. </p> <p>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. </p>