Shift-equivalence of k-ary, one-dimensional cellular automata rules

Highlights

• An equivalence relation between cellular automata relative to translations is defined.

• A characterisation of the shift-equivalent rules is given in terms of their local rules.

• An algorithm to compute the shift-equivalence classes is provided.

Abstract

Cellular automata are locally-defined, synchronous, homogeneous, fully discrete dynamical systems. In spite of their typically simple local behaviour, many are capable of showing complex emergent behaviour. When looking at their time-evolution, one may be interested in studying their qualitative dynamical behaviour. One way to group rules that display the same qualitative behaviour is by defining symmetries that map rules to others, the simplest way being by means of permutations in the set of state variables and reflections in their neighbourhood definitions, therefore defining equivalence classes. Here, we introduce the notion of shift-equivalence as another kind of symmetry, now relative to the concept of translation. After defining the notion and showing it indeed defines an equivalence relation, we extend the usual characterisation of dynamical equivalence and use it to partition some specific binary cellular automata rule spaces. Finally, we give a characterisation of the class of shift-equivalent rules in terms of the local transition functions of the cellular automata in the class, by providing an algorithm to compute the members of the class, for any k-ary, one-dimensional rule.

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.