Irreducible elementary cellular automata found

Many multi-scale systems can be greatly simplified by using successive coarse-graining (CG) for approximation of microscopic degrees of freedom. As shown by Israeli and Goldenfeld in seminal papers [1], [2], the local CG procedure can be developed also for elementary cellular automata (ECA) which represent a simplistic modeling metaphor. This allows for extracting the large-scale behavior of the original systems without accounting for small-scale detail and studying predictability of emergent phenomena in complex systems. However, due to the high computational complexity of the brute-force CG algorithm used in [1], [2], the results obtained are very fragmentary. They do not allow to draw viable conclusions about reducibility of ECA for larger grain sizes than N = 4 (i.e. for coarser resolution of coarse-graining). In this paper we present a novel CG algorithm of substantially lower computational load. Thereby, much more cellular automata can be decided in terms of their reducibility and mutual transitions. We find out that the number of “hard” - irreducible - ECA, which have coarse-grained representations, decreases with increasing the “grain” size of the approximation procedure and for N = 7 converges to a stable set of 4 irreducible inequivalent ECA: {30, 45, 106, 154}. According to Wuensche's taxonomy of ECA this is the complete set of strong chain-rules representing maximally chaotic automata. Simultaneously, it is also the complete set of strong surjective automata, i.e. highly irreversible automata. We show that our algorithm can be used both as a valuable tool for theoretical investigations on cellular automata taxonomy and as a useful metaphor of coarse-graining procedures employed to more realistic modeling paradigms such as the particle method.