A closed formula for the inverse of a reversible cellular automaton with (2R+1)-cyclic rule

摘要

Reversibility of cellular automata (CA) has been an extensively studied problem from both a theoretical and a practical point of view. It is known when a (2R+1)-cyclic cellular automaton with periodic boundary conditions (p.b.c.) is reversible (see Siap et al., 2013) but, as far as we know, no explicit expression is given for its inverse cellular automaton apart from the case R=1 (see Encinas and del Rey, 2007). In this paper we give a closed formula for the inverse rule of a reversible (2R+1)-cyclic cellular automaton with p.b.c. over the finite field F2 for any value of the neighbourhood radius R. It turns out that the inverse of a reversible (2R+1)-cyclic CA with p.b.c. is again a cyclic CA with p.b.c., but with a different neighbourhood radius, and this radius depends on certain numbers which need to be computed by a new algorithm we introduce. Finally, we apply our results to the case R=1 (which is the ECA with Wolfram rule number 150) to introduce an alternative and improved expression for the inverse transition dipolynomial formulated in Encinas and del Rey (2007). We also illustrate these results by giving explicit computations for the inverse transition dipolynomial of a reversible cellular automaton with penta-cyclic rule.