Group-Walking Automata
Ilkka Törmä; Ville Salo
Group-Walking Automata
Ilkka Törmä
Ville Salo
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042715099
https://urn.fi/URN:NBN:fi-fe2021042715099
Tiivistelmä
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.
Kokoelmat
- Rinnakkaistallenteet [19207]