In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.
es_ES
Patrocinador
dc.description.sponsorship
Comision Nacional de Investigacion Cientifica y Tecnologica, FONDECYT
3150552