<div class="csl-bib-body">
<div class="csl-entry">Gillibert, P. (2018). An automaton group with undecidable order and Engel problems. <i>Journal of Algebra</i>, <i>497</i>, 363–392. https://doi.org/10.1016/j.jalgebra.2017.11.049</div>
</div>
-
dc.identifier.issn
0021-8693
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/168399
-
dc.description.abstract
For every Turing machine, we construct an automaton group that simulates it. Precisely, starting from an initial configuration of the Turing machine, we explicitly construct an element of the group such that the Turing machine stops if, and only if, this element is of finite order. If the Turing machine is universal, the corresponding automaton group has an undecidable order problem. This solves a problem raised by Grigorchuk. The above group also has an undecidable Engel problem: there is no algorithm that, given g,h in the group, decides whether there exists an integer n such that the n-iterated commutator […[[g,h],h],…,h] is the identity or not. This solves a problem raised by Bartholdi.
en
dc.language.iso
en
-
dc.publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
-
dc.relation.ispartof
Journal of Algebra
-
dc.subject
Automaton group
en
dc.subject
Cellular automaton
en
dc.subject
Engel problem
en
dc.subject
Mealy automaton
en
dc.subject
Order problem
en
dc.title
An automaton group with undecidable order and Engel problems