Abstract : The decidability of the finiteness problem for automaton groups is a well-studied open question on Mealy automata. We connect this question of algebraic nature to the periodicity problem of one-way cellular automata, a dynamical question known to be undecidable in the general case. We provide a first undecidability result on the dynamics of one-way permutive cellular automata, arguing in favor of the undecidability of the finiteness problem for reset Mealy automata.
https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributor : Martin Delacourt
<>
Submitted on : Tuesday, March 14, 2017 - 12:52:39 PM
Last modification on : Tuesday, November 19, 2019 - 4:48:10 PM
Long-term archiving on: Thursday, June 15, 2017 - 1:55:39 PM
Martin Delacourt, Nicolas Ollinger. Permutive one-way cellular automata and the finiteness problem for automaton groups. Computability in Europe, Jun 2017, Turku, Finland. ⟨hal-01436460v2⟩
