A split-and-perturb decomposition of number-conserving cellular automata

[摘要] This paper concerns d-dimensional cellular automata with the von Neumann neighborhood that conserve the sum of the states of all their cells. These automata, called number-conserving or density-conserving cellular automata, are of particular interest to mathematicians, computer scientists and physicists, as they can serve as models of physical phenomena obeying some conservation law. We propose a new approach to study such cellular automata that works in any dimension d and for any set of states Q. Essentially, the local rule of a cellular automaton is decomposed into two parts: a split function and a perturbation. This decomposition is unique and, moreover, the set of all possible split functions has a very simple structure, while the set of all perturbations forms a linear space and is therefore very easy to describe in terms of a basis. We show how this approach allows to find all number-conserving cellular automata in many cases of d and Q. In particular, we find all three-dimensional number-conserving CAs with three states, which until now was beyond the capabilities of computers. (C) 2020 Elsevier B.V. All rights reserved.

[发布日期] 2020-12-01

[关键词] Multi-dimensional cellular automata;Number-conservation;Multi-state;Von Neumann neighborhood