A4 Refereed article in a conference publication
Group-Walking Automata
Authors: Ville Salo, Ilkka Törmä
Editors: Jarkko Kari
Conference name: International Workshop on Cellular Automata and Discrete Complex Systems
Publishing place: Berlin
Publication year: 2015
Journal: Lecture Notes in Computer Science
Book title : Cellular Automata and Discrete Complex Systems
Series title: Lecture Notes in Computer Science
Volume: 9099
First page : 224
Last page: 237
Number of pages: 14
ISBN: 978-3-662-47220-0
eISBN: 978-3-662-47221-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-47221-7_17
Web address : http://link.springer.com/chapter/10.1007%2F978-3-662-47221-7_17
In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of multi-headed finite automata that walk on Cayley graphs, 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.
Downloadable publication This is an electronic reprint of the original article. |  |
