We introduce a novel method to study the reversibility of d-dimensional number-conserving multi-state cellular automata with the von Neumann neighborhood. We apply this method to ternary such ...cellular automata, for which, up to now, nothing was known about their reversibility. It turns out that they are all trivial: the only reversible such cellular automata are shifts that are intrinsically 1-dimensional.
This paper concerns two-dimensional cellular automata on a triangular grid that preserve the sum of the states of all the cells. To study such cellular automata, we adapt the idea of the ...split-and-perturb decomposition of a number-conserving local rule, developed first for square grids, to the setting of triangular grids. As a result, we obtain a new mathematical tool that allows, for example, to enumerate all so-called k-ary (i.e., binary, ternary, quaternary, quinary, etc.) number-conserving cellular automata on a triangular grid, regardless of the value of k.
In this paper, we study non-uniform elementary cellular automata on the infinite grid in the context of number conservation. These automata operate in a one-dimensional setting, where individual ...cells can employ distinct Wolfram rules for updating their states. The result is an exhaustive characterization of such number-conserving cellular automata. Until now, such a characterization was known only for finite grids, for which research hypotheses could be derived on the basis of computer experiments. It turns out that when considering number conservation for non-uniform cellular automata, the infinite grid cannot be treated as a limiting case of finite grids, i.e., there are number-conserving non-uniform cellular automata on the infinite grid that have no analogous counterpart on finite grids.
In this paper, we investigate non-uniform elementary cellular automata (i.e., one-dimensional cellular automata whose cells can use different Wolfram rules to update their states) in the context of ...number conservation. As a result, we obtain an exhaustive characterization of such number-conserving cellular automata on all finite grids both with periodic and null boundary conditions. The characterization obtained allows, inter alia, to enumerate all number-conserving non-uniform elementary cellular automata, in particular those that are reversible. Surprisingly, the numbers obtained are closely related to the Fibonacci sequence.
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.
•A novel approach to study number conservation of cellular automata is proposed.•We prove that any number-conserving local rule is a sum of two well-defined units.•This decomposition is unique and holds for any dimension and any state set.•The effectiveness of the decomposition theorem is illustrated via several examples.
This paper presents an investigation into the evolution and dynamics of the simplest generalization of binary cellular automata: Affine continuous cellular automata (ACCAs), with
0
,
1
as state set ...and local rules that are affine in each variable. The focus lies on legal outer-totalistic ACCAs, an interesting class of dynamical systems that exhibit some behavior that is not observed in the binary case. A unique combination of computer simulations (sometimes quite advanced) and a panoply of analytical methods allows to lay bare the dynamics of each and every one of these continuous cellular automata. The results also show that in the class of ACCAs considered, all types of sensitivity can be observed: sensitivity to a change of the number of cells in the grid, sensitivity to slight changes in the parameters of a local rule and sensitivity to the change of a single value in an initial configuration.
We present a novel method to study two-dimensional rotation-symmetric number-conserving multi-state cellular automata with the von Neumann neighborhood with radius one. This method enables a succinct ...and easy enumeration in all cases examined so far in literature, i.e., cellular automata with at most five states. Moreover, it allows to find all such cellular automata with six and seven states, while so far, even enumerating six-state rules was beyond the reach of computing machines. Such enumeration allows us to revisit some unresolved questions in the field. Furthermore, we give some rough estimates of the asymptotic growth of the number of such cellular automata with n states, as n tends to infinity. The results are obtained for finite square grids with periodic boundary conditions, but they are also valid in the case of the infinite square grid.
Discrete dynamical systems such as cellular automata are vastly used as models of complex physical phenomena. For this reason, the problem of reversibility of such systems is very important and ...recurrently taken up by researchers. Unfortunately, the study of reversibility is remarkably hard, even in the case of one-dimensional cellular automata. We propose a novel method that really supports the investigation of the reversibility of number-conserving cellular automata, i.e, cellular automata that preserve the sum of the states of all the cells upon every update. This method allows to enumerate all so-called k-ary (binary, ternary, quaternary, quinary, etc.) number-conserving cellular automata that are reversible and this for a fairly wide range of values of the parameter k.
•Algorithms for enumeration of 1D reversible number-conserving cellular automata.•Use cases for 1D reversible number-conserving CA with five, six, and seven states.•Comprehensive description of dynamics for such CA with five states is presented.
PDF
