Research paperShift-equivalence of k-ary, one-dimensional cellular automata rules
Introduction
Since the first works on cellular automata [1], they have been studied both from the viewpoint of mathematical/computational theory [2], [3], [4] as well as models for simulating a broad class of phenomena in various fields, such as physics [5], [6], [7], biology [8], [9], [10] and social sciences [11], [12], [13].
From the abstract viewpoint, a cellular automaton (CA) is a fully discrete dynamical system, since its space, time and state variables are all discrete. Moreover, the time evolution induced by a CA is locally-defined, with parallel and synchronous update from one iteration to the next [14].
With simple, locally-defined rules, some CAs are capable of showing complex global behaviour, including the ability to simulate a universal Turing machine [4], [15], [16], [17].
Cellular automata rule spaces have exponential growth both as a function of the neighbourhood size and of the number of possible states. As such, when analysing full rule spaces, it is often useful to group rules that display the same qualitative behaviour and take one in every class as its representative, thus reducing the effective rule set to be analysed. Generally speaking, the idea of same qualitative behaviour may refer to any property that is shared by a set of rules or by the time-evolution induced by them. In the case of dynamical equivalence in particular, this is carried out by joining in the same class rules that have the same time-evolution except possibly for a symmetry, that is, except possibly for changing the name of the states and/or reversing the order of the states in a configuration, that is, state conjugacies and reflections, respectively [4], [18]. These operations can be regarded as symmetries in the state set and in the configuration space, so that the resulting rules in a class are effectively dynamically equivalent.
The idea of partitioning CA rule spaces in classes according to some particular property is a widely studied topic. One of the first studies in dynamical equivalence regarding symmetries, as discussed above, was made in [18], and later deepened in [19] and [20]. The empirical notion of time-evolution complexity of elementary cellular automata (ECAs) rules was made in [21], [22], and formalised in terms of nonlinear dynamics concepts in [19]. A classification of the ECA rule space in terms of topological dynamics properties of the rules was given in [23] in terms of the parameters of sensitivity and chaoticity. On different perspectives, Ninagawa [24] and Ruivo and de Oliveira [25] classified the ECA rule space according, respectively, to the power spectrum and the Fourier spectrum generated by the rules. A review on the topic of classifications of CAs providing examples from many points of view can be found in [26].
When CAs are studied with respect to cyclic configurations, either finite – as in the context of computational tasks such as the determination of the density [27] or parity [28] of the configuration – or infinite – as in the case of computing the limit-set of a rule [29] – two rules that generate configurations that are translations of one another are essentially the same. Hence, as is the case for the previous symmetries, it does make sense to define the notion of rules that are equivalent relatively to translations in the configurations. This is exactly what we do here, by defining the notion of shift-equivalence between rules. It is worth noticing that such a notion is not the same as the one in the shift equivalence problem as addressed in [30], [31], which refers to the notion of conjugate shift spaces.
Although the notion of shifted configurations has been a recurring one in the CA literature, apparently the present work is the first characterisation of the notion of shift-equivalence among rules, based purely upon their local function, an approach that provides an additional algorithmic tool to sieve one-dimensional CA spaces towards equivalent rules of a specific nature.
We start, in the next section, by giving the basic definitions and introducing the notation. Then, in Section 3, we define the notion of shift-equivalence, showing that it is indeed an equivalence relation, and using it to extend the notion of dynamical equivalence. In Section 4 we then apply the extended dynamical equivalence to partition four cellular automata rule spaces, showing the Boolean expressions defining some rules that are in non-unitary classes of shift-equivalence and using them to give a characterisation of the rules in the same shift-equivalence class for a more general case. We conclude in Section 5.
Section snippets
Basic definitions
A cellular automaton (CA) A is a 4-tuple [14] where:
- •
for some is the state set;
- •
with is the neighbourhood vector;
- •
is the local transition function or local rule;
- •
is the dimension.
Given a CA, its local rule f acts locally in configurations. A d-dimensional k-ary configuration c is a mapping . Each index is a cell of the configuration and c(i) is the state of cell i in configuration c, which will be written ci from
Shifts and translations
Since configurations are bi-infinite k-ary sequences, the ones entailed by a given CA rule may be analysed in terms of the finite subsequences they contain, and can be regarded as words in a formal language. In fact, applying a one-dimensional CA rule finitely many times over each possible initial configuration yields a set that can be described by a regular language [3], [33].
In the study of the subsequences that may appear in a configuration generated by a given one-dimensional rule, the
Partitions of some rule spaces
Applying the procedures described in the previous section, we partitioned the rule spaces and in shift-equivalence classes, dynamical equivalence classes and extended dynamical equivalence classes, as shown in Table 1.
Notice that for and the DEC classes and the DECx classes are exactly the same. This is because for radius- reflection equivalence and shift-equivalence coincide.
The reduction rate from the number of dynamical classes to the
Concluding remarks
We extended the notion of dynamical equivalence of one-dimensional CA rules by defining a new relation between rules, namely, shift-equivalence. We have shown that such a relation is indeed an equivalence relation in the rule spaces .
We then used the shift-equivalence to define an extended dynamical equivalence class, which includes rules that are the same except for reflections, permutations on the set of states and shifts. Following, we partitioned the rule spaces R(2, 1),
Acknowledgements
All authors are thankful for a research grant from MackPesquisa – Fundo Mackenzie de Pesquisa. Additionally, P.P.B.O. thanks CNPq, and E.G. and F.L. thank CONICYT.
References (34)
Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics
Physica D
(1984)Simulating physics with cellular automata
Physica D
(1984)- et al.
Quantum field as a quantum cellular automaton: the dirac free evolution in one dimension
Ann Phys
(2015) - et al.
A cellular automaton model for the effects of population movement and vaccination on epidemic propagation
Ecol Modell
(2000) Theory of cellular automata: a survey
Theor Comput Sci
(2005)Universality and complexity in cellular automata
Physica D
(1984)- et al.
The best currently known class of dynamically equivalent cellular automata rules for density classification
Neurocomputing
(2006) Theory of self–reproducing automata
IEEE Trans Neural Networks
(1966)Computation in cellular automata : a selected review lattice
NonStand Comput
(1998)Computation theory of cellular automata
Commun Math Phys
(1984)
A new kind of science
A cellular automaton model for hypoxia effects on tumour growth dynamics
Software, knowledge, information management and applications (SKIMA), 2014 8th international conference on
A fuzzy delay approach for HIV dynamics using a cellular automaton
J Appl Math
Pedestrian group behavior in a cellular automaton
Pedestrian and evacuation dynamics 2012
Simulating urban growth by integrating landscape expansion index (LEI) and cellular automata
Int J Geograph Inf Sci
Self-organized societies: on the sakoda model of social interactions
Complexity
Mathematical games: the fantastic combinations of John Conway’s new solitaire game “Life”
Sci Am
Cited by (4)
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids
2023, Theoretical Computer ScienceCharacterisation of the elementary cellular automata with neighbourhood priority based deterministic updates
2022, Communications in Nonlinear Science and Numerical Simulation