Nilpotency and periodic points in non-uniform cellular automata

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.

Automated summary

This study investigates nilpotency in one-dimensional non-uniform cellular automata (NUCA) and finds that changing the distribution of local rules can drastically impact the dynamics of the system. It is proven that in some cases, there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. Additionally, the undecidability of determining if a NUCA with a given finite distribution of local rules has a periodic point is established.