Algebra Seminar talk
2017-11-17
Pierre Gillibert
The order problem in automaton groups is undecidable
Abstract:
A self-similar group is a subgroup of the automorphism group of a tree of all
words (over a finite alphabet), such that the induced actions on sub-trees are
also in the group. An automaton group is a self-similar group satisfying a
stronger condition: There is a finite set of generators, such that the action
of generators on sub-trees are also in the set of generators. Equivalently the
group is generated by the actions induced by a Mealy automaton (the set of
states correspond to the set of generators).
Using automaton groups Alešin constructed a simple example of a Burnside group. Later Grigorchuk gave an example of an automaton groups which is Burnside, just-infinite, amenable, non-elementary amenable and of intermediate growth, solving Milnor's problem and Day's problem.
The word problem is solvable in automaton groups (Eilenberg’s reduction algorithm). However there is an automaton group with undecidable conjugacy problem.
We prove that the order problem is undecidable (answering a question by Grigorchuk). From any Turing Machine, with a one-direction infinite tape, we constructs an automaton group. It simulates the Turing Machine in the following sense: Given any entry word there is an (explicitly constructed) element of the group such that the Turing Machine stops on this entry if and only if the order of the element is finite.
In particular, considering an automaton group constructed from a universal Turing Machine, there is no algorithm which decides whether or not an element is of finite order.