# Partial Reversibility of One-Dimensional Cellular Automata

Ronaldo De Castro Corrêa, Pedro De Oliveira

► To cite this version:

Ronaldo De Castro Corrêa, Pedro De Oliveira. Partial Reversibility of One-Dimensional Cellular Automata. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.120-134, 10.1007/978-3-319-39300-1_10. hal-01435024

HAL Id: hal-01435024

https://inria.hal.science/hal-01435024

Submitted on 13 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Partial reversibility of one-dimensional cellular automata

Ronaldo de Castro Corrêa², Pedro P.B. de Oliveira¹,²

Universidade Presbiteriana Mackenzie

Faculdade de Computação e Informática¹

Pós-Graduação em Engenharia Elétrica e Computação²

Rua da Consolação, 930 - Consolação, São Paulo - SP, 01302-907, Brazil

ronaldo.c.correa@gmail.com, pedrob@mackenzie.br

**Abstract.** Reversibility is the property of very special cellular automata rules by which any path traversed in the configuration space can be traversed back by its inverse rule. Expanding this context, the notion of partial reversibility has been previously proposed in the literature, as an attempt to refer to rules as being more or less reversible than others, since some of the paths of non-reversible rules could be traversed back. The approach was couched in terms of a characterisation of the rule's pre-image pattern, that is, the number of pre-images of a rule for all configurations up to a given size, and their relative lexicographical ordering used to classify the rules in terms of their relative partial reversibility. Here, we reassess the original definition and define a measure that represents the reversibility degree of the rules, also based on their pre-image patterns, but now relying on the probability of correctly converting each possible cyclic, finite length configuration, up to a maximum size. As a consequence, it becomes possible to look at partial reversibility in absolute terms, and not relatively to other rules, as well to infer the reversibility degrees for arbitrary lattice sizes, even in its limit to infinity. All the discussions are restricted to the elementary space, but are also applicable to any one-dimensional rule space.

**Keywords:** One-dimensional cellular automata; reversible rule; partial reversibility; reversibility degree, elementary space, pre-image pattern.

## 1 Introduction

The rules of some cellular automata (CAs) permit that any temporal evolution be reversed, regardless of the initial configuration, by means of its corresponding inverse rule. This property of reversibility is appealing due to the various potential applications it may entail, such as in encryption, reversible computing processes, quantum computation, etc ([10]).

Several studies on the reversibility of cellular automata have been carried out, both aiming at understanding the properties of these rules, and at creating algorithms to detect or enumerate reversible cellular automata. For example, [6] and [1] propose algorithms to build reversible rules, the former using a method
based on graphs and the latter based on an elaborate algebraic approach. Algorithms also do exist to establish whether a one-dimensional rule is reversible or not, such as in [5], since this problem is undecidable for larger dimensions ([4]). Also, there are simple and effective techniques to build reversible CAs using variants of the CAs. One of them are the block CAs, where groups of cells have their states changed together ([9]); another are the partitioned cellular automata (PCAs), introduced in [8], which can be regarded as a CA with multiple tracks; and finally, the second order CAs introduced in [11], exemplified in the space of elementary rules. The facility to build and handle reversible CAs with these techniques has been important both in expanding the phenomenology of reversible CAs, and in proving important theoretical results about (conventional) reversible CAs. As such, [7] used PCAs to show that one-dimensional reversible CAs can be computation universal, and [3] proved that any reversible CA can be represented by a reversible block CA.

Broadening the original reversibility concept, [2] introduced the notion of *relative partial reversibility*, which consists in classifying one-dimensional rules that are more or less reversible, clustering them if they have the same partial reversibility. Since reversible CAs can be very difficult to find in an arbitrary space, a practical motivation for defining ways to characterise partial reversibility is the possibility of iteratively searching that space, following the path of rules which are more and more reversible than others, until reaching the reversible ones, much like the successful approach discussed in [13]. However, exploring partial reversibility is tempting in itself, as a way to probe a rule space from the perspective of the reversibility property.

Under the scheme presented in [2], the set of reversible rules are placed at the top of the rank, and the less reversible ones at the bottom. Such a classification is obtained by means of the relative lexicographical ordering of the *pre-image patterns* of the rules, which is a multiset of the pre-image quantities of all possible cyclic initial configurations, up to a maximum given lattice size $L_{max}$.

Here, after verifying that the lexicographical ordering of pre-image patterns is not fully adequate as a basis for addressing partial reversibility, we go on defining a quantity that stands for the reversibility degree of a rule and then use it to individually analyse all rules of the elementary space. In spite of this restriction, any other one-dimensional space is also amenable to analogous analyses, provided sufficient computational resources are available. Whether our study can be used to address spaces with higher dimensionality is an open question that we do not venture to address; however, given the impossibility of an algorithm existing to verify the reversibility of rules with dimensions larger than 1 ([4]), we suspect that our approach may not be readily applicable. Finally, the fact that we only address cyclic configurations has no theoretical consequences, since the global function of any one-dimensional cellular automaton is bijective, if and only if, its restriction on periodic configurations is also bijective (see, for instance, [4]).

After presenting the required background for the paper in Section 2, the subsequent section revisits partial reversibility, the reversibility degree of a rule is proposed, and the reversibility degrees of the rules of the elementary space
are individually analysed for finite lattice sizes and as well as when size tends to
infinity. The last section wraps up the work with some concluding remarks.

2 Background

**2.1 Basics**

Cellular automata (CAs) are discrete dynamical systems defined by the triplet (S, N, f), in which S is the finite set of states $S = \{s_0, s_1, \dots, s_{k-1}\}$, $N \in S^m$ defines the neighbourhood of a cell c, with m being the number of cells in the neighbourhood, and $f: S^m \to S$ is the local state transition function applied to each cell. The CA lattice is a d-dimensional array of cells, with $d > 0$, each one taking on the states in S. We denote the global lattice configuration by $C \in \mathbb{Z}^d$. The rule is applied to all cells of the lattice, synchronously, at each time step t, after which the configuration C is updated.

Here we rely upon one-dimensional CAs, with $S = \{0,1\}$ and $m=3$, that is,
the elementary space. The state transition function $f$ receives as parameter the
states of a cell $c$ and those of its two next-neighbour cells at time $t$ and returns
the state of $c$ at time $t+1$. When $f$ is defined for all $S^m$ possible neighbourhoods
the CA rule is well-defined; in the elementary space a rule might be the following
set of state transitions, in reverse lexicographical order of the neighbourhoods:
$\{111 \to 0, 110 \to 1, 101 \to 1, 100 \to 0, 011 \to 0, 010 \to 1, 001 \to 1, 000 \to 0\}$.
Following such an ordering, each rule can be represented by an integer $R$, after
the resulting decimal number generated from the outputs of each neighbourhood;
for the previous example, the sequence of out bits corresponds to rule number
102, out of the 256 possible rules that define the space ([11]).

From the standpoint of their dynamical behaviours, rules may be equivalent
to others, defining equivalence classes, obtained from the operations of conju-
gation and reflection, and by composing the latter two ([11]). For binary CAs,
conjugation consists of flipping all bits in the neighbourhoods and their outputs
and reordering the state transitions, as mentioned above; on its part, reflection
consists of reversing the neighbourhoods, while keeping the same output bit, and
then performing the reordering. The equivalence class is completed by composing
conjugation and reflection in any order, and reordering the resulting state tran-
sitions. Once a class of dynamical equivalence is obtained, we can simply refer
to it by a representative, usually the rule with the lowest number; for instance,
elementary rule 45 is the representative of the class {45, 75, 101, 89}.

The pre-images of a configuration at time step *t* are formed by all the possible previous configurations at *t* − 1. For a rule to be reversible, all possible configurations can only have a single pre-image. Configurations that do not have pre-image are known as *Garden of Eden (GoE)*. If a rule has at least one *GoE* configuration, consequently, the rule also has some configuration with more than one pre-image; therefore, the rule is not reversible ([4]). Reversible cellular automata are exceptions, because the majority of the rules of any space have some *GoE* configuration. In the elementary space, only the rules 15, 85, 51, 170, 240 and 204 are reversible.
## 2.2 Partial Reversibility Classes

The notion of partial reversibility of CA rules was originally proposed in [2], based on the pre-image pattern of a rule, which is a multiset containing all pre-image quantities of all possible configurations with finite lengths varying from 1 to $L_{max}$. More precisely, the pre-image pattern of a rule with number $R$, with respect to configuration sizes up to $L_{max}$, is represented by $\mathcal{P}_R$ and defined as:

**Definition 1 (Pre-image pattern).**

$$ \mathcal{P}_R = \{l_1, l_2, \dots, l_{|\mathcal{P}_R|}\} \begin{cases} |\mathcal{P}_R| \le |S|^{C_{L_{max}}} \\ l_i \in \mathbb{Z}^+ \text{ is the number of pre-images of configuration } i \end{cases} $$

where $C_{L_{max}}$ is the total number of possible configurations of sizes from 1 to $L_{max}$, given by:

$$ C_{L_{max}} = \sum_{q=1}^{L_{max}} |S|^q = -2 + 2^{L_{max}+1} \quad (1) $$

In words, each $l_i \in \mathcal{P}_R$ represents the number of pre-images of every (non-GoE) configuration, with sizes in the range $[1, L_{max}]$.

**Remarks:**

1) Notice that $\sum_{i=1}^{|\mathcal{P}_R|} l_i = C_{L_{max}}$.

2) Pre-image pattern was first introduced in [2], therein named reversibility pattern, with the necessity that the multiset should be ordered from the lowest to the highest value. Although this is not a necessity for present purposes, we preserve the same scheme just for the sake of clarity of presentation.

The pre-image patterns of elementary rules 1 and 68 are illustrated below, with $L_{max} = 4$:

**Example 1 (Pre-image patterns of elementary rules 1 and 68).**

$$ \mathcal{P}_1 = \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\} $$

$$ \mathcal{P}_{68} = \{1, 1, 1, 1, 1, 1, 1, 2^*, 2, 2, 2, 2, 2, 2, 2, 2, 3\} $$

Rules that share the same pre-image patterns can be grouped into classes, referred to in [2] as *Partial Reversibility Classes*, PRCs for short. In face of these classes, [2] asked how they could be classified from the least to the most reversible, and proposed this would be based on their pre-image patterns, lexicographically ordered in relation to each other. From this standpoint, for the pre-image patterns $\mathcal{P}_1$ and $\mathcal{P}_{68}$ above, rule 1 turns out to be more reversible than rule 68, since at the position highlighted with “*” for both rules – which is the first position where they differ – the number of pre-images of rule 1 is smaller than that for rule 68.

In [2], such a *relative* classification of the rules was performed in the elementary space up to $L_{max} = 23$, resulting in 45 PRCs, as shown in Table 1; later
on, the same authors managed to extend the classification up to $L_{max} = 31$, with no change in the classes. With all previous data available to us, here we extended them further to $L_{max} = 32$ and once again the same classes and their order remained. Quite coherently, the first PRC $\{15, 51, 170, 204\}$ is formed by the reversible rules of the elementary space, while the last PRC $\{0\}$ is the least reversible, since for any lattice size, a single configuration has all the others as pre-images.

<table><caption>Table 1: Partial reversibility classes of the elementary space.</caption><tr><td>{15, 51, 170, 204}</td><td>{45, 154}</td><td>{30, 106}</td><td>{105, 150}</td><td>{37, 164}</td><td>{22, 104}</td><td>{62, 110}</td></tr><tr><td></td><td>{25, 152}</td><td>{41, 134}</td><td>{73, 146}</td><td>{26, 74}</td><td>{57, 156}</td><td>{94, 122}</td><td>{7, 168}</td><td>{58, 78}</td><td>{54, 108}</td></tr><tr><td></td><td></td><td>{14, 42}</td><td>{38, 44}</td><td>{35, 140}</td><td>{28, 50, 56, 76}</td><td>{33, 132}</td><td>{77, 178}</td><td>{23, 232}</td><td>{6, 40}</td></tr><tr><td></td><td></td><td>{9, 130}</td><td>{5, 160}</td><td>{27, 172}</td><td>{3, 19, 136, 200}</td><td>{13, 162}</td><td>{18, 72}</td><td>{43, 142}</td><td>{29, 184}</td></tr><tr><td></td><td></td><td>{1, 128}</td><td>{4, 32}</td><td>{11, 138}</td><td>{12, 34}</td><td>{2, 8}</td><td>{10}</td><td>{60}</td><td>{90}</td><td>{126}</td><td>{36}</td><td>{24}</td><td>{46}</td><td>{0}</td></tr></table>

Notice in the table that each PRC is defined only by the set of every representative rule of each dynamical equivalence class involved; for instance, while PRC $\{45, 154\}$ refers to only two rules, more rules are effectively therein, since rule 45 has the same pre-image pattern of its dynamically equivalent rules 75, 101 and 89, and rule 154 has the same pre-image pattern of its dynamical class 210, 166 and 154. The fact that we are referring only to $\{45, 154\}$ is a mere simplification of the notation.

Furthermore, in order to simplify any reference to specific PRCs, throughout the paper we sometimes simply refer to the first rule of the class – its representative, with the smallest number – but meaning its entire class.

# 3 Reversibility degree

## 3.1 Reappraisal of relative partial reversibility in [2]

Although the notion of relative partial reversibility in [2] was interesting for its own sake and led to insightful considerations about the pre-image patterns of the rules with increasing lattice sizes, it is insufficient if an absolute characterisation of partial reversibility is the target. The point is that relative lexicographical ordering of the pre-image patterns ends up not using them fully, which represents the ineffective use of all lattice sizes implicit in the patterns. This can be realised with the pre-image patterns $P_1$ and $P_{68}$ from Example 1. The lexicographical ordering thus goes on only up to $l_8$ (highlighted with “*”), while the remaining pre-image quantities are simply discarded, as there is no need for them.

So, there cannot be a situation in which all pre-image patterns are compared and only the last pre-image quantity is different, because the sum of all pre-image quantities must be maintained. As a consequence, to come up with a quantity that could be used to formalise such a scheme of partial reversibility seems a fruitless effort, as it would not be related to an intrinsic property of a rule. This is why unsuccessful attempts were reported in [2] exactly with that aim. What we really need is a way to account for the pre-image pattern of a rule in its entirety and regardless of any other rule involved, that is, in absolute terms.
## 3.2 Absolute partial reversibility

The notion of an absolute partial reversibility should be just a corollary of a notion of reversibility degree of a rule that would account for all the information available in the pre-image pattern of a rule.

In order to go about that, let us first have it clear that since $l_i \in \mathcal{P}_R$ contains the pre-image quantity of a possible configuration at any time step, $1/l_i$ can be interpreted as the probability of reversing the time evolution one step, at the configuration concerned. So, computing the reversion probability of all pre-image quantities $l_i$ yields the individual probabilities of correctly reversing all possible configurations of lattices up to $L_{max}$ of a rule. By adding all reversion probabilities, dividing the result by the number of possible configurations up to $L_{max}$, and normalising the result in the interval [0, 100], 0 means that a rule is the least reversible in the rule space at issue, and 100 corresponds to the reversible rules. More precisely, the reversibility degree of a rule $R$ is defined as:

**Definition 2 (Reversibility degree of a rule).**

$$ \delta_R(\mathcal{P}_R, L_{max}) = \left( \frac{\sum_{i=1}^{|\mathcal{P}_R|} \frac{1}{l_i}}{-2 + 2^{L_{max}+1}} \right) \times 100 $$

To exemplify the calculation of $\delta_R$, consider the pre-image patterns $\mathcal{P}_0$ and $\mathcal{P}_{15}$, up to $L_{max} = 4$:

**Example 2 (δ_R for two elementary rules with extreme values).**

$$ \begin{aligned} \mathcal{P}_0 &= \{2, 4, 8, 16\} \\ \delta_0 &= \left( \frac{1/2+1/4+1/8+1/16}{30} \right) \times 100 = 3.125 \end{aligned} $$

$$ \begin{aligned} \mathcal{P}_{15} &= \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\} \\ \delta_{15} &= \left( \frac{30 \times 1}{30} \right) \times 100 = 100 \end{aligned} $$

Because for rule 0, a single configuration is the image of all configurations, regardless of the lattice size, its reversibility degree has to be the lowest, non zero, in the elementary space, which indeed is the case; as a consequence it is no longer possible to refer to a *non-reversible* rule in any space, in absolute terms. At the other extreme, the reversible elementary rule 15 has maximal reversibility degree of 100.

Since the sum of each $1/l_i$ impairs a direct interpretation of the resulting value in terms of probability, we verified what would happen when using multiplication. But it would turn out that neither PRC {15, 51, 170, 204} of the reversible rules nor PRC {0}, the least reversible one, would be placed in the extreme ends of the classification. Thus, the approach based on the multiplication of each $1/l_i$ does not lead to a coherent result, although it would preserve a clear interpretation of the quantity in terms of probabilities.

The reversibility degree $\delta_R$ allows us to group the rules with the same degree, and classify them in a relative way, analogously to [2]; this was carried out for
the elementary rules up to $L_{max} = 32$, and the results are plotted as the series of graphics shown in Figure 1. At the vertical axis, the PRCs are classified from the least reversible ({{0}}) at the bottom, to the reversible one ({{15, 51, 170, 204}}), with the horizontal axis displaying the maximum lattice size $L_{max}$ at each computation. It becomes clear that, as $L_{max}$ increases, the relative positions of the PRCs tend to settle, even though with some local oscillations.

The position of the majority of the PRCs plotted in the graphic clearly stabilises as $L_{max}$ gets progressively larger. However, this does not occur with all PRCs; for example, while PRCs {60} and {90} – the 5th and 8th rows from top to bottom, respectively, at $L_{max} = 32$ – move away from the least reversible ones, quite interestingly, the exact opposite trend obtained out of the lexicographical ordering scheme employed in [2].

### 3.3 Partial reversibility degree of individual elementary rules

With the definition of the reversibility degree of a rule, it becomes possible to visualise the individual reversibility degree of the rules in the elementary space, as shown in Figure 2. The initial lattice size used was 6, after eliminating a transient; the computations were performed up to $L_{max} = 32$. In the figure, the vertical axis displays the reversibility degree of the rules, normalised from 0 to 100, and the horizontal axis shows the lattice sizes up to $L_{max}$. Overall, it becomes clear that, as $L_{max}$ increases, the reversibility degree of several PRCs either decrease or increase smoothly, almost monotonically, while three others do not follow this trend, keeping either an oscillation or a steady value. Relevant details of the figure are discussed below.

As expected, the graphics shows that the PRC of the reversible elementary rules ({{15, 51, 170, 204}}) have maximal reversibility degree of 100, and that PRC {0} contains the least reversible rules. It also becomes evident the reason why PRCs {60} and {90} moved away from the least reversible ones on the relative partial reversibility graphs of Figure 1. The explanation is that PRC {60} (at the 5th row from top to bottom, at $L_{max} = 32$), has a stable reversibility degree of 25; consequently, as the degrees of several PRCs decrease, while $L_{max}$ increases, they get closer to the least reversible rules. So, it is not PRC {60} that moves away from the least reversible ones, but an effect of the behaviour of the others. A similar situation occurs with PRC {90} (at the 8th row from top to bottom, at $L_{max} = 32$), with the difference that PRC {90} has an apparently periodical variation in its reversibility degree.

Figure 2 is limited to $L_{max} = 32$ due to the high processing time to generate the pre-image patterns for superior lattice sizes; for this reason, it was not possible to empirically verify in which reversibility levels the PRCs would get stable. Alternatively, we went about analytically inferring the limit of the reversibility degree with $L_{max}$ tending to infinity. For such, three groups of PRCs have been identified, shown in Table 2, as suggested by the plot, namely: $\overrightarrow{PRC}$, whose respective reversibility degrees are stable or have periodic variation; $\uparrow PRC$, whose degrees tend to 100; and $\downarrow PRC$, with reversibility degrees tending to 0.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Relative partial reversibility in the elementary space, as defined by the partial reversibility degrees of the rules, up to $L_{max} = 32$.</figcaption></figure>

<table><caption>Table 2: Groups of PRCs sharing a pattern in their reversibility degrees.</caption><tr><td><span style="text-decoration: overline;">PRC</span></td><td>{105, 150}, {90}, {60}</td></tr><tr><td>↑PRC</td><td>{15, 51, 170, 204}, {45, 154}, {30, 106}</td></tr><tr><td>↓PRC</td><td>{0}, {2, 8}, {46}, {24}, {12, 34}, {10}, {4, 32}, {1, 128}, {11, 138}, {36}, {126}, {18, 72}, {5, 160}, {3, 19, 136, 200}, {13, 162}, {9, 130}, {6, 40}, {33, 132}, {77, 178}, {23, 232}, {43, 142}, {29, 184}, {27, 172}, {28, 50, 56, 76}, {38, 44}, {14, 42}, {35, 140}, {54, 108}, {58, 78}, {7, 168}, {94, 122}, {73, 146}, {26, 74}, {57, 156}, {41, 134}, {25, 152}, {62, 110}, {37, 164}, {22, 104}</td></tr></table>

For each group, their respective expressions for $\delta_R$ were rewritten as a function of $L_{max}$ instead of $P_R$, assuming the pre-image pattern of PRCs has a non-mutable pattern of formation, as suggested from the graphs in Figure 2. In doing so, we managed to work out analytically the limits of the reversibility degrees, with the help of software *Mathematica*, specifically, *FindSequenceFunction*[$a_n$], that tries to find a simple function that yields the sequence $a_n$ when given successive integer arguments ([12]). For all PRCs only the rule with the smallest number was used in the calculations, as a representative. Even though all PRCs have been analysed, we only discuss below significant PRCs of each group.

### 3.3.1 Analysis of the $\overline{PRC}$ group

Firstly, let us look at $\overline{PRC}$, composed by {105, 150}, {90} and {60}. It can be observed for PRC {105, 150} that the quantities of pre-image do not change while
<figure><img src="image_3.png" /><figcaption>Fig. 2: Reversibility degrees of the elementary rules, with $L_{max}$ from 6 to 32.</figcaption></figure>

$L_{max}$ increases, while the frequency of pre-image quantities do (see Table 3); the pre-image pattern of rule 105 is a multiset formed by the pre-image quantities 1 and 4. As such, the frequencies of these quantities were listed as a function of $L_{max}$, and the series analysed with the software *Mathematica*, resulting in the following equations $q1_{105}$ and $q4_{105}$, where $x = L_{max}$:

$$q1_{105}(x) = (2/21)(-9 - 2^x(-14 + 5 \cos(2\pi x/3) + \sqrt{3} \sin(2\pi x/3)))$$

$$q4_{105}(x) = (1/42)(-12 + 2^x(7 + 5 \cos(2\pi x/3) + \sqrt{3} \sin(2\pi x/3)))$$

<table><caption>Table 3: Frequencies of the pre-image quantities for rule 105.</caption><thead><tr><th>x = L<sub>max</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>q1<sub>105</sub>(x)</th><td>2</td><td>6</td><td>6</td><td>22</td><td>54</td><td>54</td><td>182</td><td>438</td><td>438</td><td>1462</td><td>3510</td><td>3510</td><td>11702</td><td>28086</td><td>28086</td></tr><tr><th>q4<sub>105</sub>(x)</th><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>18</td><td>18</td><td>18</td><td>146</td><td>146</td><td>146</td><td>1170</td><td>1170</td><td>1170</td><td>9362</td></tr></tbody></table>

With equations $q1_{105}$ and $q4_{105}$, it becomes possible to rewrite equation $\delta_{105}$ as a function of $L_{max}$ only, without the pre-image pattern $P_{105}$. The reversibility degree of rule 105 as a function of $L_{max}$ is defined by equation $\delta'_{105}(x)$ below, where the normalisation factor 100 was dropped off, as it does not influence the limit to be worked out; in fact, the notation $\delta'_R(x)$ is employed for all other analyses that will follow. In order to validate the correctness of equation $\delta'_{105}$, it was used to generate the values of reversibility degree from $L_{max} = 16$ up to $L_{max} = 32$, and compared to those empirically obtained with $\delta_{105}$ (used in Figure 2), and they matched exactly. This same kind of verification was employed for all other results described in the paper, and they all matched.
$$ \delta'_{105}(x) = (q1_{105}(x) + (1/4)q4_{105}(x))/( -2 + 2^{x+1} ) \quad (2) $$

Given the hypothesis that the pattern of formation of pre-image quantities would remain the same for $L_{max} > 32$, the limit of $\delta'_{105}(x)$ as $x$ tending to infinity can then be calculated, so as to verify at which reversibility degree the PRC {105, 150} would stabilise:

$$ \lim_{x \to +\infty} \delta'_{105}(x) = \left( 231 - 15 \left( 5 \cos(2\pi x/3) + \sqrt{3} \sin(2\pi x/3) \right) \right) / 336 $$

In doing so, it can be verified that the outcomes of $\cos(\frac{2\pi x}{3})$ and $\sin(\frac{2\pi x}{3})$ follow a pattern: for $x \mod 3 = 0$, their resulting values are 1 and 0, respectively; for $x \mod 3 \neq 0$, the cosine is always $-1/2$, while the sine yields $\sqrt{3}/2$ when $x \mod 3 = 1$ or $-\sqrt{3}/2$ when $x \mod 3 = 2$. Since the graph corresponding to PRC {105, 150} in Figure 2 varies periodically with three values, in the limit $\delta'_{105}(x)$ also leads to three values:

$$ \lim_{x \to +\infty} \delta'_{105}(x) = \begin{cases} \text{if } x \mod 3 = 0 : 46.4286 \\ \text{if } x \mod 3 = 1 : 73.2142 \\ \text{if } x \mod 3 = 2 : 86.6071 \end{cases} $$

The same general procedure has been applied to PRC {90}, after realising that its pre-image pattern is a multiset composed by pre-image quantities 2 and 4. By listing the frequencies of these pre-image quantities as a function of $L_{max}$ (following Table 4) and inferring the series with *Mathematica*, two equations are obtained:

$$ \begin{aligned} q2_{90}(x) &= (1/6)(-2 + 3 \times 2^x + (-1)^{1+x} 2^x) \\ q4_{90}(x) &= (1/12)(-4 + (-2)^x + 3 \times 2^x) \end{aligned} $$

<table><caption>Table 4: Frequencies of the pre-image quantities for rule 90.</caption><thead><tr><th>x = L<sub>max</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>q2<sub>90</sub>(x)</th><td>1</td><td>1</td><td>5</td><td>5</td><td>21</td><td>21</td><td>85</td><td>85</td><td>341</td><td>341</td><td>1365</td><td>1365</td><td>5461</td><td>5461</td><td>21845</td></tr><tr><th>q4<sub>90</sub>(x)</th><td>0</td><td>1</td><td>1</td><td>5</td><td>5</td><td>21</td><td>21</td><td>85</td><td>85</td><td>341</td><td>341</td><td>1365</td><td>1365</td><td>5461</td><td>5461</td></tr></tbody></table>

After rewriting equation $\delta_{90}$ as a function of $L_{max}$, by means of functions $q2_{90}$ and $q4_{90}$ (as below), the validation procedure described earlier was performed, with renewed success, thus yielding:

$$ \delta'_{90}(x) = ((1/2)q2_{90}(x) + (1/4)q4_{90}(x)) / (-2 + 2^{x+1}) \quad (3) $$

Once again, the limit of $\delta'_{90}(x)$ with $x$ tending to infinity was calculated to determine the reversibility degree to which PRC {90} stabilises:

$$ \lim_{x \to +\infty} \delta'_{90}(x) = \begin{cases} \text{if } x \mod 2 = 0 : 12.50 \\ \text{if } x \mod 2 = 1 : 18.75 \end{cases} $$
Repeating the previous procedures for PRC {60}, whose reversibility degree has no variations, one can realise that its pre-image pattern is made up of only frequency 2. The frequencies of the pre-image quantities were analysed as a function of $L_{max}$ and $\delta'_{60} = ((1/2)q2_{60}(x))/( -2 + 2^{x+1})$ was obtained. The limit with $x$ tending to infinity was calculated and the reversibility degree stabilises in 25.

### 3.3.2 Analysis of the ↑PRC group

The next group of PRCs analysed is ↑PRC, composed by those that approach reversibility degree 100, namely, PRCs {45, 154} and {30, 106} (excluding the trivial case of the reversible rules). The analyses followed the very same procedures as those before. As such, the pre-image patterns of rule 45 are multisets composed by the pre-image quantities 1, 2 and 3, whose frequencies have been listed (Figure 5), extended by inference, eventually leading to the following three equations:

$$ q1_{45}(x) = \frac{3(\sqrt{2}-2)2^{x+3}+6((\sqrt{2}-2)x-(-1)^x)-28(-1)^{2x}}{12(\sqrt{2}-2)} + \frac{3(-2\frac{x}{2}+3)((2\sqrt{2}-3)(-1)^{x-1})+\sqrt{2}(-1)^x+20\sqrt{2}(-1)^{2x}+\sqrt{2}-14}{12(\sqrt{2}-2)} $$

$$ q2_{45}(x) = \frac{2\frac{x}{2}+1((2\sqrt{2}-3)(-1)^{x-1})+2(-1)^x+4(-1)^{2x}}{2(\sqrt{2}-2)} + \frac{2((2\sqrt{2}-3)(-1)^{2x+1}+\sqrt{2}-1)x-3\sqrt{2}(-1)^{2x}+\sqrt{2}(-1)^{x+1}+2}{2(\sqrt{2}-2)} $$

$$ q3_{45}(x) = (1/4)(-1)^x ((-1)^x(2x-1)+1) $$

<table><caption>Table 5: Frequencies of the pre-image quantities for rule 45.</caption><thead><tr><th>x = L<sub>max</sub></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>q1<sub>45</sub>(x)</th><td>2</td><td>3</td><td>11</td><td>20</td><td>52</td><td>101</td><td>229</td><td>454</td><td>966</td><td>1927</td><td>3975</td><td>7944</td><td>16136</td><td>32265</td><td>65033</td></tr><tr><th>q2<sub>45</sub>(x)</th><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>8</td><td>8</td><td>22</td><td>22</td><td>52</td><td>52</td><td>114</td><td>114</td><td>240</td><td>240</td></tr><tr><th>q3<sub>45</sub>(x)</th><td>0</td><td>1</td><td>1</td><td>2</td><td>2</td><td>3</td><td>3</td><td>4</td><td>4</td><td>5</td><td>5</td><td>6</td><td>6</td><td>7</td><td>7</td></tr></tbody></table>

With functions $q1_{45}$, $q2_{45}$ and $q3_{45}$, the expression for $\delta_{45}$ can be rewritten as a function of $L_{max}$, yielding

$$ \delta'_{45}(x) = (q1_{45}(x) + (1/2)q2_{45}(x) + (1/3)q3_{45}(x))/( -2 + 2^{x+1}) \quad (4) $$

with the limit $\lim_{x \to +\infty} \delta'_{45}(x) = 1$. So, PRC {45, 154} tends to reversibility in the limit of the lattice size.

Finally, PRC {30, 106} was also analysed following the same procedure, and three equations – this time recurrence equations – were obtained for $q1_{30}$, $q2_{30}$ and $q3_{30}$ (shown on the page), resulting in

$$ \delta'_{30}(x) = (q1_{30}(x) + (1/2)q2_{30}(x) + (1/3)q3_{30}(x))/( -2 + 2^{x+1}) \quad (5) $$

thus leading to $\lim_{x \to +\infty} \delta'_{30}(x) = 1$, which means that also these rules tend to reversibility.
$$q1_{30}(x) = -4q1_{30}(x-6) - 2q1_{30}(x-5) - 4q1_{30}(x-4) + 3q1_{30}(x-3) + 2q1_{30}(x-1),$$

$$\text{with} \quad \begin{cases} q1_{30}(1) = 0, q1_{30}(2) = 2, q1_{30}(3) = 5, \\ q1_{30}(4) = 11, q1_{30}(5) = 31, q1_{30}(6) = 72 \end{cases}$$

$$q2_{30}(x) = +3 - 2q2_{30}(x-6) - q2_{30}(x-4) + 3q2_{30}(x-3) + q2_{30}(x-1),$$

$$\text{with} \quad \begin{cases} q2_{30}(1) = 1, q2_{30}(2) = 2, q2_{30}(3) = 3, \\ q2_{30}(4) = 8, q2_{30}(5) = 14, q2_{30}(6) = 24 \end{cases}$$

$$q3_{30}(x) = \frac{1}{9} \left( 3x + \sqrt{3} \sin\left(\frac{2\pi x}{3}\right) + 3 \cos\left(\frac{2\pi x}{3}\right) - 3 \right)$$

### 3.3.3 Analysis of the ↓PRC group

With all PRCs analysed so far their pre-image patterns are composed by constant values of pre-image quantities, only their frequencies varying. But it so happens that for ↓PRC new pre-image quantities appear in their pre-image patterns as $L_{max}$ increases, with progressively increasing values. This impaired the possibility of inferring the frequencies as a function of $L_{max}$. The pre-image pattern of PRC {22, 104} exemplifies this situation, with the exponent of each pre-image quantity representing its frequency:

Example 3 (Pre-image pattern of rule 22).

$$P_{22} = \{1^{19490}, 2^{6227}, 3^{3023}, 4^{1144}, 5^{619}, 6^{347}, 7^{303}, 8^{58}, 9^{306}, 10^{41}, 11^{16}, 12^{15}, 13^{184}, 14^{44}, 16^{1}, 19^{53}, 20^{15}, 22^{1}, 27^{14}, 28^{43}, 32^{1}, 39^{15}, 41^{30}, 47^{1}, 68^{1}, 99^{1}, 145^{1}, 212^{1}, 310^{1}\}$$

Notwithstanding the difficulty just mentioned, the limit can still be calculated with direct analysis of $\delta_R$. The growing order of the numerator $\sum_{i=1}^{|P_R|} \frac{1}{l_i}$ of $\delta_R$ resembles a harmonic series $\sum_{x=1}^{\infty} \frac{1}{x}$, which gradually diverges as $x$ increases; on the other hand, its denominator $-2+2^{L_{max}+1}$, has exponential growth (Equation 1). The left and right hand figures in Figure 3 illustrate the difference in growth order of a harmonic series and Definition 2, respectively.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Growing order of the components of $\delta_R$ in Definition 2.</figcaption></figure>

As a consequence, the reversibility degree limit is clearly 0; further analytical validation with Mathematica also confirms this conclusion. All the pre-image
patterns of the group $\downarrow PRC$ were verified, and they are similar to that of rule 22 discussed above. Therefore, all of them will tend to 0 with $L_{max}$ tending to infinity.

# 4 Concluding remarks

The original relative lexicographical ordering of pre-image patterns employed in [2] is not adequate as a way to characterise the notion of reversibility degree of a rule as an intrinsic property. We made it explicit that it rejects pre-image quantities, unless the pre-image patterns compared are identical.

We then gave the definition of the reversibility degree of a rule ($\delta_R$) as a way to represent an absolute form of characterising the reversibility degree of a rule, within a scale from 0 to 100, from the least reversible to reversible ones. This quantity then provides a natural way to characterise the relative partial reversibility between arbitrary rules. Since $\delta_R$ relies upon the pre-image pattern of all pre-image quantities for all lattice sizes up to $L_{max}$, it can be regarded as a rule property up to this finite limit. In cases when $\delta_R$ can be fully written in terms of $L_{max}$ only, and its limit to infinity calculated, the property becomes truly robust. As we showed these limits can be worked out for the entire elementary space.

Property $\delta_R$ was applied to all rules of the elementary space and the relative ordering was plotted in Figure 1. The resulting relative ordering was similar to the one in [2], although not exactly. For example, here PRCs {60} and {90} moved away from the less reversible rules, instead of getting closer, as happened therein. It was also possible to analyse the reversibility degree of all PRCs individually as a function of $L_{max}$, which was not possible before.

The calculations were limited to $L_{max} = 32$ due to the high processing time and big storage space required; thus, it was not possible to empirically verify in which degree the PRCs would be stabilised. To verify the reversibility degree with $L_{max}$ tending to infinity, the pre-image patterns were analysed through their formation patterns. The PRCs were divided into three groups to facilitate the analysis: $\overrightarrow{PRC}$, in which their respective degree are stable or have periodic variation; $\uparrow PRC$, which tend reversibility; and $\downarrow PRC$, which tend to 0.

For the groups $\overrightarrow{PRC}$ and $\uparrow PRC$, it was possible to rewrite $\delta_R$ as a function of $L_{max}$ only (instead also of $P_R$), which has permitted the calculation of their limits with $L_{max}$ tending to infinity, thus identifying the reversible rules or those with a limit trend to reversibility. However, it was seen in the group $\downarrow PRC$ that the pre-image patterns of the PRCs do not display a formation pattern as a function of $L_{max}$, since new pre-image quantities appear while $L_{max}$ increases. Nevertheless, by direct analysis of the expression that defines $\delta_R$, it was possible to demonstrate that its reversibility levels tend to 0 while $L_{max}$ tend to infinity.

All discussions and analyses have been made in the context of the elementary space due to computational constraints only; any larger one-dimensional space is also amenable to the same kind of treatment. However, since we relied on numerical/computational methods, our results open various ways for formal
follow-ups. Along these lines we envisage, for instance, the characterisation of
the partial reversibility classes for finite lattice sizes and their limit with infinite
size configurations, including the questions of why there are 45 classes for finite
configurations and 5 for infinite; proofs that the series we inferred for the pre-
image patterns really hold; to investigate what would be the counterpart of an
inverse rule in the partial reversibility context, including the question of whether
a single of multiple inverse rules should be defined; and to look at how the notion
of partial reversibility in CAs extends to larger dimensions, since undecidability
of reversibility in these cases is an established fact.

**Acknowledgements:** We thank the financial support provided by Fornax Technology to R. Corrêa, and by MackPesquisa (Fundo Mackenzie de Pesquisa), FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo) and CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico) to P. de Oliveira.

References

[1] Boykett, T.: Efficient exhaustive listings of reversible one dimensional cellular automata. Theoretical Computer Science, 325:215-247, (2004)

[2] de Oliveira, P. P. B., Freitas, R.: Relative partial reversibility of elementary cellular automata. In J. Kari, N. Fatés, T. Worsh, eds, Proc. of Automata 2010: 16<sup>th</sup> Int. Workshop on Cellular Automata and Discrete Complex Systems, LORIA-INRIA, Nancy, France, 195-208 (2010)

[3] Durand-Lose, J.: Representing reversible cellular automata with reversible block cellular automata. In Robert Cori, Jacques Mazoyer, Michel Morvan, and Rémy Mosseri, editors, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG '01, volume AA of Discrete Mathematics and Theoretical Computer Science Proceedings, pages 145-154, (2001)

[4] Kari, J.: Theory of Cellular Automata: A Survey. Theoretical Computer Science, 334:3-33 (2005)

[5] Mora, J. C. S. T., Vergara, S. V. C., Martínez, G. J., McIntosh, H. V.: Procedures for calculating reversible one-dimensional cellular automata Physica D, 202:134-141 (2005).

[6] Moraal, H.: Graph-theoretical characterization of invertible cellular automata. Physica D, 141:1-18 (2000)

[7] Morita, K.: Computation universality of one-dimensional reversible cellular automata. Information Processing Letters, 42:325-329, (1992)

[8] Morita, K., Harao, M.: Computation universality of 1 dimensional reversible (in-jective) cellular automata. Transactions Institute of Electronics, Information and Communication Engineers, E, 72:758-762, (1989)

[9] Toffoli, T., Margolus, N.: Cellular Automata Machines: A New Environment for Modeling, MIT Press, (1987).

[10] Toffoli, T., Margolus, N.: Invertible Cellular Automata: A Review. Physica D, 45:229-253, (1994)

[11] Wolfram, S.: A New Kind of Science. Wolfram Media, (2002)

[12] Wolfram Research: Wolfram Mathematica. http://www.wolfram.com/mathematica, (2015)

[13] Wolz, D., de Oliveira, P. P. B.: Very effective evolutionary techniques for searching cellular automata rule spaces. Journal of Cellular Automata, 3(4):289-312, (2008)