A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Nilpotency and periodic points in non-uniform cellular automata
Tekijät: Kamilya Supreeti, Kari Jarkko
Kustantaja: SPRINGER
Julkaisuvuosi: 2021
Journal: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 58
Numero: 4
Aloitussivu: 319
Lopetussivu: 333
Sivujen määrä: 15
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-020-00390-7
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/66523304
Tiivistelmä
Nilpotent cellular automata have the simplest possible dynamics: all initial configurations lead in bounded time into the unique fixed point of the system. We investigate nilpotency in the setup of one-dimensional non-uniform cellular automata (NUCA) where different cells may use different local rules. There are infinitely many cells in NUCA but only a finite number of different local rules. Changing the distribution of the local rules in the system may drastically change the dynamics. We prove that if the available local rules are such that every periodic distribution of the rules leads to nilpotent behavior then so do also all eventually periodic distributions. However, in some cases there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. We demonstrate such a possibility using aperiodic Wang tile sets. We also investigate temporally periodic points in NUCA. In contrast to classical uniform cellular automata, there are NUCA-even reversible equicontinuous ones-that do not have any temporally periodic points. We prove the undecidability of this property: there is no algorithm to determine if a NUCA with a given finite distribution of local rules has a periodic point.
Nilpotent cellular automata have the simplest possible dynamics: all initial configurations lead in bounded time into the unique fixed point of the system. We investigate nilpotency in the setup of one-dimensional non-uniform cellular automata (NUCA) where different cells may use different local rules. There are infinitely many cells in NUCA but only a finite number of different local rules. Changing the distribution of the local rules in the system may drastically change the dynamics. We prove that if the available local rules are such that every periodic distribution of the rules leads to nilpotent behavior then so do also all eventually periodic distributions. However, in some cases there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. We demonstrate such a possibility using aperiodic Wang tile sets. We also investigate temporally periodic points in NUCA. In contrast to classical uniform cellular automata, there are NUCA-even reversible equicontinuous ones-that do not have any temporally periodic points. We prove the undecidability of this property: there is no algorithm to determine if a NUCA with a given finite distribution of local rules has a periodic point.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali