Title: Decidability problems in automaton semigroups,
Abstract: We consider decidability problems in self-similar semigroups, and in
particular in semigroups of automatic transformations of $X^*$. We describe
algorithms answering the word problem, and bound its complexity under some
additional assumptions. We give a partial algorithm that decides in a group
generated by an automaton, given $x,y$, whether an Engel identity
($[\cdots[[x,y],y],\dots,y]=1$ for a long enough commutator sequence) is
satisfied. This algorithm succeeds, importantly, in proving that Grigorchuk's
$2$-group is not Engel. We consider next the problem of recognizing Engel
elements, namely elements $y$ such that the map $x\mapsto[x,y]$ attracts to
$\{1\}$. Although this problem seems intractable in general, we prove that it
is decidable for Grigorchuk's group: Engel elements are precisely those of
order at most $2$. We include, in the text, a large number of open problems.
Our computations were implemented using the package "Fr" within the computer
algebra system "Gap".