Nazim Fatès
email: nazim.fates@loria.fr

Irène Marcovici
email: irene.marcovici@univ-lorraine.fr

Coalescence in fully asynchronous elementary cellular automata Jordina Francès de Mas MSc in Dependable Software Systems (DESEM) 1st year

Cellular automata (CA) are discrete mathematical systems formed by a set of cells arranged in a regular fashion. Each of these cells is in a particular state and evolves according to a local rule depending on the state of the cells in its neighbourhood. In spite of their apparent simplicity, these dynamical systems are able to display a complex emerging behaviour, and the macroscopic structures they produce are not always predictable despite complete local knowledge.

While studying the robustness of CA to the introduction of asynchronism in their updating scheme, a phenomenon called coalescence was observed for the first time: for some asynchronous CA, the application of the same local rule on any two di↵erent initial conditions following the same sequence of updates quickly led to the same non-trivial configuration. Afterwards, it was experimentally found that some CA would always coalesce whilst others would never coalesce, and that some of them exhibit a phase transition between a coalescing and non-coalescing behaviour.

However, a formal explanation of non-trivial rapid coalescence has yet to be found, and this is the purpose of this project, where we try to characterise and explain this phenomenon both qualitatively and analytically. In particular, we analytically study trivial coalescence, find lower bounds for the coalescence time of ECA 154 and ECA 62, and give some first steps towards finding their upper bounds in order to prove that they have, respectively, quadratic and linear coalescence time.

Introduction 1.Main properties and history of CA

Cellular automata (CA) are discrete mathematical systems formed by a set of cells arranged in a regular fashion. Each of these cells is in a particular state and evolves according to a local rule depending on the state of the cells in its neighbourhood. Despite of their apparent simplicitythey are a set of cells updating their state in discrete time by following simple local rules-, these dynamical systems are able to display complex emerging behaviour. As Epstein wrote, "even perfect knowledge of individual decision rules does not always allow us to predict macroscopic structure.

We get macro-surprises despite complete micro-knowledge" [START_REF] Epstein | Agent-based computational models and generative social science[END_REF].

Example 1.1. The one-dimensional binary cellular automaton which simultaneously updates every cell with the sum modulo 2 of its right and left neighbours, known as ECA 90 (see page 6 for a formal definition of Elementary Cellular Automata), initialised with a single cell in state one generates the Sierpiński triangle, a very famous fractal structure (see Figure 1). At each time step, each cell is simultaneously updated with the sum modulo 2 of its right and left neighbours, and the resulting configuration is plot on top of its predecessor.

CA were introduced by von Neumann in the 1950s when he was studying the problem of selfreplicating systems [START_REF] Neumann | The general and logical theory of automata[END_REF] and, following a suggestion of his colleague Stanislaw Ulam, he focused on the study of a two-dimensional discrete model [START_REF] Neumann | Theory of self-reproducing automata[END_REF]. The particular CA he worked with was rather complicated, with 29 possible states for each cell, but prospective studies would show that even the simplest kind of CA are capable of modelling numerous complex systems, such as those with many interacting elements in biology [START_REF] Green | Cellular automata models in biology[END_REF] (e.g. biological cells [START_REF] Alber | On cellular automaton approaches to modeling biological cells[END_REF], swarming phenomenon [START_REF] Deutsch | Principles of biological pattern formation: swarming and aggregation viewed as selforganization phenomena[END_REF], pattern formation [START_REF] Deutsch | Cellular automaton modeling of biological pattern formation: characterization, applications, and analysis[END_REF][START_REF] Kusch | Mollusc shell pigmentation: cellular automaton simulations and evidence for undecidability[END_REF][START_REF] Manukyan | A living mesoscopic cellular automaton made of skin scales[END_REF]), physics (e.g. ideal gases and fluids [START_REF] Salem | Thermodynamics and hydrodynamics with cellular automata[END_REF]), chemistry (e.g. anodisation process [START_REF] Bartosik | Cellular automata model of anodization[END_REF]), economics (e.g. financial market [START_REF] Bartolozzi | Stochastic cellular automata model for stock market dynamics[END_REF]), sociology and ecology [START_REF] Engelen | Using cellular automata for integrated modelling of socio-environmental systems[END_REF][START_REF] Nowak | Modeling social change with cellular automata[END_REF][START_REF] White | Cellular automata and fractal urban form: a cellular modelling approach to the evolution of urban land-use patterns[END_REF], among others. These results show that CA are not merely abstract systems, but can directly correspond to natural processes.

Example 1.2. Kusch and Markus and Coombes showed that the pigmentation patterns on mollusc's shells could be generated by CA models [START_REF] Coombes | The geometry and pigmentation of seashells[END_REF][START_REF] Kusch | Mollusc shell pigmentation: cellular automaton simulations and evidence for undecidability[END_REF]. More recently, Manukyan et al. demonstrated that the colour pattern of the ocellated lizards' skin scales can be modeled by a cellular automaton [START_REF] Manukyan | A living mesoscopic cellular automaton made of skin scales[END_REF] (see Figure 2). Figure 2: Conus textile shell exhibiting a pattern that can be identified with ECA 30 (left, reprinted from [START_REF] Coombes | The geometry and pigmentation of seashells[END_REF]), and ocellated lizard scales skin exhibiting a pattern that can be identified with a quasihexagonal probabilistic CA (right, reprinted from [START_REF] Manukyan | A living mesoscopic cellular automaton made of skin scales[END_REF]).

In the 1960s, the computation capabilities of CA were noticed and started to be formally studied.

CA, like Turing machines, can be fully specified in mathematical terms and implemented in physical structures, but the main di↵erence is that they perform computations in a parallel, distributed fashion. It was proven that some CA can emulate a universal Turing machine, and therefore compute, according to Church-Turing thesis, anything computable.

Example 1.3. The most popular CA is probably Conway's Game of Life [START_REF] Gardner | Mathematical games: The fantastic combinations of john conways new solitaire game life[END_REF]. It is a twodimensional CA which exhibits a range of complex and interesting behaviour, and it is one of the simplest computational models ever proved to be Turing-complete [START_REF] Berlekamp | Winning ways for your mathematical plays academic[END_REF]. The simplest known model capable of universal computation is a one-dimensional binary CA known as ECA 110, the behaviour of which is on the boundary between stability and chaos [START_REF] Cook | Universality in elementary cellular automata[END_REF]. These findings suggest that, surprisingly enough, naturally occurring physical systems may also be capable of universality! However, note that other factors such as noise and asynchronism may be present in real systems, and these factors can alter the universality capabilities of the system (see Remark on page 15).

In the 1980s, Wolfram started to work on cellular automata and published several papers [START_REF] Martin | Algebraic properties of cellular automata[END_REF][START_REF] Salem | Thermodynamics and hydrodynamics with cellular automata[END_REF][START_REF] Wolfram | Computation theory of cellular automata[END_REF][START_REF] Wolfram | Cellular automata and complexity: collected papers[END_REF] that led to a rapid increase of scientific interest in the field. He extensively explored onedimensional CA, and in 2002 he published a 1280-page book summarising his work, findings and ideas, arguing that CA have significance for all disciplines of science, and providing the groundwork for further research [START_REF] Wolfram | A new kind of science[END_REF].

Asynchronism and coalescence

In their original definition, CA cells are all updated in parallel at each time step, that is, synchronously. However, it could be argued that other updating methods better model real systems where asynchronism, noise and errors may be present. It was observed that even a small change in this CA feature could strongly modify their behaviour and properties (see e.g. [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF]). Surprisingly, some CA behave the same if their cells are updated in a synchronous or an asynchronous manner (we call these to be "robust" to asynchronism), but the behaviour of some other CA drastically changes when di↵erent updating styles are used. The systematic study of these kind of perturbations showed that some previously observed behaviours and properties where, in fact, artifacts of a synchronous updating and the use of a regular disposition of the cells [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF]. This gave rise to the study of other classes of CA, namely asynchronous CA, probabilistic CA, and CA with alternative cell shapes and arrangements.

While studying the "robustness" of ECA to the introduction of asynchronism in their updating scheme, Fatès and Morvan observed one of these aforementioned "macro-surprises": for some asynchronous ECA, the application of the same local rule on any two di↵erent initial conditions following the same sequence of updates quickly led to the exact same configuration [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF] (see Figures 3 and 4). This surprising phenomenon is called coalescence and it was experimentally studied by Rouquier and Morvan, who showed that some ECA would always coalesce whilst others would never coalesce, and that some of them exhibit a phase transition between a coalescing and noncoalescing behaviour [START_REF] Rouquier | Robustesse et mergence dans les systmes complexes: le modle des automates cellulaires[END_REF][START_REF] Rouquier | An exhaustive experimental study of synchronization by forcing on elementary cellular automata[END_REF][START_REF] Rouquier | Coalescing cellular automata[END_REF][START_REF] Rouquier | Combined e↵ect of topology and synchronism perturbation on cellular automata: Preliminary results[END_REF][START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF]. However, a formal explanation of non-trivial rapid coalescence has yet to be found, and this is the purpose of this project, where we try to characterise and explain this phenomenon both qualitatively and analytically. It is quite obvious that a CA which, given any initial configuration and following any sequence of updates, always reaches the same configuration (typically, a fixed point) after some time will be coalescent. For example, ECA 0 (where any input configuration becomes zero) and ECA 255 (where any input configuration becomes one). This phenomenon can thus be called trivial coalescence (see Figure 3). On the other hand, non-trivial coalescence has also been observed [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF] (see Figure 4), and so this suggests that the asymptotic behaviour of some CA could be completely independent of the initial configuration but strongly dependent on the sequence of updates.

Remember that CA are deterministic in the sense that starting from the same initial configuration and updating the same cells in the same order will lead to the exact same result. However, their global behaviour may be very complex, even chaotic, and di cult to predict, so we would not expect them to synchronise. Therefore, it is puzzling to see that an apparent non-trivial configuration (like the evolution of ECA 46 that we can see in Figure 4) is always reached from any initial condition if the same updating sequence is followed, especially when this happens very quickly! Thinking of CA as complex systems, many questions about this unexpected synchronisation phenomenon arise: will two complex systems be able to synchronise? If so, how long will it take? Will this synchronisation be independent or dependent on the initial configuration? Will the order in which the cells are updated matter? In how many di↵erent states is a complex system able to coalesce? How robust is this property? The study of these kind of questions can help us understand and build complex systems robust to some perturbations or with a specific global behaviour independent of its initial state. showing their di↵erences in green and orange and their agreement in white and grey (right). This surprising phenomenon is not only interesting by its own, but also for its deeper meaning when related to real systems, for it may conceptually correspond to the so-called dichotomy "nature versus nurture", that is, the updating dynamics can be thought of as the environment, whilst the local rule would represent the intrinsic properties of a system evolving from a particular initial condition.

The behaviour of a system could strongly depend on the initial condition, or not at all. On the other hand, the same system may behave di↵erently when interacting with di↵erent environments, that is, a system can be strongly dependent on the environment or, on the contrary, it can be robust to environment changes if its evolution is una↵ected by them. Thus, this parallelism may lead to the discovery of environment-dependent versus environment-independent universal properties, and a deeper study of coalescence may help us to understand other phenomena, such as synchronisation and confluence.

As we can see, many properties of CA still need to be explored, studied, and understood, even for the most elementary cases. Moreover, some state-of-the-art characterisations are purely qualitative, so a rigorous mathematical analytical study should be done.

Definitions and notation

CA and ECA

Let us start with a general formalisation of the model that we are going to study: Definition 2.1. A cellular automaton (CA) is given by a tuple (d, n, Q, V, f, ↵) where

• d 2 N is the dimension;

• n = (n 1 , . . . , n d ) 2 N d is the (possibly infinite) size; • Q is the set of possible states that a cell may assume (the alphabet);

• V = {v 1 , . . . , v |V | },
the neighbourhood, is a finite set of vectors in Z d specifying which cells a↵ect one another, that is, which cells takes into account the local transition rule f when updating the value of a cell. For d = 1 it is usually specified by its symmetric radius r, and then V = { r, (r 1), . . . , 1, 0, 1, . . . , r 1, r};

• f : Q |V | ! Q is the local transition function or rule.
It defines how the state of a cell is updated according to the states of the cells located in its neighbourhood;

• ↵ 2 [0, 1] is the synchrony rate which will determine the global transition function (see Section 2.2). That is, each cell has probability ↵ to be updated (note that ↵ = 0 is an abuse of notation which corresponds to the extreme case where a single cell is updated at each time step).

However, we will most of the time focus on the simplest class of CA, namely elementary cellular automata: Definition 2.2. An elementary cellular automaton (ECA) is a one-dimensional CA having two possible values for each cell and radius one (i.e. rules depend only on the cell being updated and its two nearest neighbours). Thus, it corresponds to the tuple (1, n, {0, 1}, { 1, 0, 1}, f, ↵) with n 2 N,

f : {0, 1} 3 ! {0, 1} and ↵ 2 [0, 1].
There are 2 2 3 = 256 such automata, each of which can be indexed according to its local transition rule. We use the classical notation (see Table 1) introduced by Wolfram [START_REF] Wolfram | A new kind of science[END_REF] together with the alternative encoding (see Table 2) introduced by Fatès [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF] which provides an immediate inference of the local behaviour of the CA just by looking at its letter code 1 .

• In Wolfram's notation, a rule f is denoted by the number

2 7 f (1, 1, 1)+2 6 f (1, 1, 0)+2 5 f (1, 0, 1)+ 2 4 f (1, 0, 0) + 2 3 f (0, 1, 1) + 2 2 f (0, 1, 0) + 2 1 f (0, 0, 1) + 2 0 f (0, 0, 0). 2 7 2 6 2 5 2 4 2 3 2 2 2 1 2 0
x y z 111 110 101 100 011 010 001 000 [START_REF] Macauley | Order independence in asynchronous cellular automata[END_REF] and used in their further works [START_REF] Macauley | Coxeter groups and asynchronous cellular automata[END_REF][START_REF] Macauley | Dynamics groups of asynchronous cellular automata[END_REF].

f (x, y, z) 1 1 0 1 0 0 1 0
• In Fatès' notation, a rule f is denoted by its di↵erence to the identity automaton, using a concatenation of letters which specify the active transitions (the ones that change the state of the cell being updated; i.e. if f (x, 0, y) = 1 or f (x, 1, y) = 0) according to the following letter code: A corresponds to the neighbourhood 000, B to 001, C to 100, D to 101, E to 010, F to 011, G to 110, and H to 111.

A B C D E F G H
x y z 000 001 100 101 010 011 110 111 In the context of asynchronism, the advantage of this second naming is that we can deduce from it whether the local behaviour can increase the number of ones (transitions A, B, C, D)

f (x, y, z) 0 1 1 0 0 0 1 1
or decrease it (transitions E, F, G, H), whether it is possible that isolated zeros (resp. ones) disappear (transition D, resp. E) or appear (transition H, resp. A) and the displacement of 01 and 10 frontiers (transition B moves 01 to the left whilst transition F moves it to the right, and transition C moves 10 to the right whilst transition G moves it to the left) (see Table 3). At each (discrete) time step, the CA configuration evolves according to its transition function (based on the states of neighbouring cells) and the updating scheme (see Section 2.2). The space-time diagram is the usual way to visualise the dynamics of a CA. For the one-dimensional case, it is obtained by stacking these successive configurations (see Figure 5).

Most analytical studies aim to find theoretical results for infinite-size CA. However, it is not always possible to experimentally handle that kind of CA. In order to get an insight into infinite-size CA, we can use periodic boundary conditions, so that for a dimension which has size n, each cell can be indexed by Z/nZ. In that case, taking the same size n in every dimension we can denote the cell space by U = (Z/nZ) d . Then the configuration space may be defined as Q U . That is, each configuration x 2 Q U is a word indexed by U with letters in Q. A zone is a subset of consecutive cells being in the same state. These are the basic tools to study the behaviour of CA. However, recall that, informally speaking, we say that a CA is coalescent if, starting from two di↵erent initial configurations and updating the same cells at each time step, we obtain exactly the same configuration after letting it evolve for some time. As we could see on page 5 Figure 4 (left and centre), it is often di cult to visually detect coalescence just by comparing two space-time diagrams side by side, even when n is small. Thus, in order to study coalescence, we are going to use all the tools and notations introduced above together with what we call the agreement space-time diagram, which is the superimposition of two space-time diagrams showing the di↵erences between both configurations (see page 5 Figure 4, right).

Remark. The agreement space-time diagram of two ECA is the space-time diagram of a 4-state one-dimensional CA: let i 2 Z/nZ and x, y 2 {0, 1} Z/nZ be two configurations. Then a cell in its superimposition z can be in the following states:

z i = 8 > > > > > > < > > > > > > : a 0 i↵ x i = y i = 0 a 1 i↵ x i = y i = 1 d 0 i↵ x i = 0 and y i = 1 d 1 i↵ x i = 1 and y i = 0 that is, z 2 ( a 0 = 0 0 ! , a 1 = 1 1 ! , d 0 = 0 1 ! , d 1 = 1 0 !) Z/nZ
and its local transition function f is fully determined by the local transition function of the ECA

f ECA : f x 0 x ! , y 0 y ! , z 0 z !! = f ECA (x 0 , y 0 , z 0 ) f ECA (x,

Updating schemes and fixed points

There are di↵erent types of updating schemes, that is, di↵erent ways to choose which cells will be updated at each time step. These updating styles may radically change the global behaviour of the dynamics of a CA (see Figure 6) and, thus, its properties, like coalescence. The main updating schemes are:

• Synchronous dynamics: all cells are updated in parallel; that is, the transition function is simultaneously applied on each cell at each time step with probability ↵ = 1.

Historically, this is the most used and studied updating scheme because it was the one associated to the seminal definition of CA. However, there has been much interest in asynchronous regimes over the last decade [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF].

• Partially asynchronous dynamics: each cell is independently updated with probability ↵ 2 (0, 1) at each time step. It is also known as ↵-asynchronous dynamics.

Partially asynchronous CA are a subclass of probabilistic CA, which have stochastic updating local rules [START_REF] Bušic | Density classification on infinite lattices and trees[END_REF][START_REF] Bušić | Probabilistic cellular automata, invariant measures, and perfect sampling[END_REF][START_REF] Mairesse | Around probabilistic cellular automata[END_REF].

• Fully asynchronous dynamics: at each time step, only one cell is randomly and uniformly chosen to be updated. Notice that this updating scheme can only be applied to finite-size CA; otherwise, we would need to consider continuous time. With a small abuse of notation we refer to it as ↵ = 0.

Fully asynchronous CA are a subclass of interacting particles systems (IPS), which are continuoustime Markov processes [START_REF] Bušic | Density classification on infinite lattices and trees[END_REF][START_REF] Fatès | Two-dimensional tra c rules and the density classification problem[END_REF][START_REF] Liggett | Interacting particle systems. classics in mathematics[END_REF].

Note. Even though this last dynamics intuitively corresponds to the limit ↵ ! 0, note that it may not always coincide. For example, ECA 146 (BCEFG) starting from a configuration ...11111111100111111... and under fully asynchronism could never reach a configuration with all ones; however, under a partially asynchronous update with very small ↵, there is always a tiny possibility that the size two zero-zone disappears if the two consecutive cells having state 0 are updated simultaneously. Each updating scheme gives rise to a global transition function, F ↵ : Q U ! Q U , which associates to each configuration x 2 Q U a configuration y 2 Q U according to the following definitions:

↵ = 1 ↵ = 0.5 ↵ = 0
• For a synchronous updating scheme (↵ = 1),

y i = f (x i 1 , x i , x i+1 ) for all i 2 U . • For a partially asynchronous updating scheme (↵ 2 (0, 1)), for every i 2 U , y i = f (x i 1 , x i , x i+1
) with probability ↵ and y i = x i with probability (1 ↵). • For a fully asynchronous updating scheme (↵ = 0),

y i = f (x i 1 , x i , x i+1
) for a randomly uniformly chosen i 2 U and for each j 6 = i, y j = x j . We denote by x t the configuration obtained after t applications of the given updating scheme; i.e.,

x t = F t ↵ (x). Note that for asynchronous updating schemes (↵ 2 [0, 1)) x t is a random variable. It is important to notice that a reachable configuration under a given updating scheme may not be reachable under another one.

Remark. The complete set of configurations of a deterministic CA produced after any finite number of time steps can be described in terms of regular formal language [START_REF] Wolfram | Computation theory of cellular automata[END_REF].

Along its evolution, a CA may have more probability to reach some configurations than others, and there are some configurations from where any further application of the global transition function will result in the same configuration; i.e., it will remain constant. It will be important to identify these global behaviours in order to study and understand coalescence. In particular: Definition 2.3. The set of fixed points of ECA f with a given n and synchrony rate ↵ is {x 2 Q U :

P (F ↵ (x) = x) = 1}.
Remark. The set of fixed points of the asynchronous dynamics is clearly identical to the set of fixed points of the synchronous dynamics. However, its reachability may vary depending on the updating scheme used.

Example 2.2. The set of fixed points of ECA 130 (BEFG) with ring size n is {0 n , 1 n }. Under synchronous updating, none of them is reachable from a configuration di↵erent from the fixed point itself. However, under fully asynchronous dynamics, ECA 130 converges very quickly to 0 n for any configuration di↵erent from 1 n . We can easily determine the set of fixed points of an ECA by using an adaptation of de Bruijn diagrams (see Figure 7 and see e.g. [START_REF] Fatès | Remarks on the cellular automaton global synchronisation problem[END_REF]). It represents all the possible transitions in a graph form, allowing us to easily detect all possible cycles corresponding to fixed points configurations (we can find the set of fixed points of all ECA in Table 5 of Appendix A). Informally speaking, any cycle of inactive transition nodes will be a fixed point, because they correspond to static configurations. Using the same procedure we can see that the set of fixed points of ECA 44 (DGH) with ring size n is {0 n , 10 r1 10 r2 . . . 10 rq with r i 2 and P q i=1 r i = n q}, because the only possible cycles of inactive transitions (A, B, C, E, F) are the A loop and A m BEC, where m 2 N can be di↵erent each time we come back to node C. Note that 0 n cannot be reached from any configuration di↵erent from 0 n for both synchronous and fully asynchronous updating schemes.

Definition 2.4. The worst expected convergence time of a fully asynchronous ECA f (W ECT f ) can be defined as follows: let x 2 Q U , let S f be the set of fixed points of rule f , and let T f (x) = min{t :

x t 2 S
f } be the random variable representing the time needed to reach a fixed point starting from configuration x under fully asynchronous dynamics. Then [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF]).

W ECT f = max x2Q U E[T f (x)](see

ECA properties

Symmetries and equivalence classes

It is easy to see that there is a total of 88 fundamentally non-equivalent ECA rules after basic symmetry considerations (see Table 5 in Appendix A). These symmetries that have been classically of 0 and 1), and the combination of these two operations (see Figures 8 and9). Since their main properties (including coalescence) are una↵ected by these transformations, ECA form 88 equivalence classes, each of which is represented by the minimal ECA of the class; i.e., the lowest-numbered using Wolfram's notation (see Table 1 on page 6). This is important to know and very useful, because it notably reduces the study cases, for we can deal with these 88 representative ECA without loss of generality. That is, we know that any result that applies to an ECA can be extended to the other ECA in its equivalence class.

Using Fatès' notation we can observe that the classical symmetries considered correspond to the following changes in the letter code:

• Vertical reflection corresponds to the exchanges B $ C and F $ G.

• Conjugation corresponds to the exchanges

A $ H, B $ G, C $ F and D $ E.

• The composition of both transformations corresponds to the exchanges

A $ H, B $ F, C $ G and D $ E.
As we can see in Figure 8, ECA 2 (BEFGH) is equivalent to ECA 16 (CEFGH) under vertical reflection, ECA 191 (ABCDG) under conjugation, and ECA 247 (ABCDF) under the composition of both transformations. Another example with a less trivial behaviour is given in Figure 9.

Linearity, a nity, quiescence, homogeneity and universality

There are several special classes of ECA with interesting and useful properties. Definition 2.5. Linear ECA are those that can be described by a linear rule; that is, their rules can be expressed as f (x 1 , x 2 , x 3 ) = P i2I x i mod 2 where I ✓ {1, 2, 3}.

There are 8 such automata: 0, 60, 90, 102, 150, 170, 204, 240.

Remark. Local transition functions of linear ECA behave as XOR (exclusive disjunction); i.e., they perform sum modulo 2.

Definition 2.6. Additive or a ne ECA are those that can be described by an a ne rule; that is, its rule can be expressed as

f (x 1 , x 2 , x 3 ) = ✏ + P i2I x i mod 2, where I ✓ {1, 2, 3} and ✏ 2 {0, 1}.
There are 16 such automata: 0, [START_REF] Fatès | Remarks on the cellular automaton global synchronisation problem[END_REF][START_REF] Worsch | Towards intrinsically universal asynchronous CA[END_REF]60,85,90,102,105,150,153,165,170,195,204,240,255.

Remark. Additive ECA correspond to XOR and NXOR operations over the neighbourhood.

Notice that the set of linear ECA is a subset of the set of additive ECA. Thus, the quotient rule of an additive ECA is the linear ECA obtained from the same rule with ✏ = 0 (see Figure 10), and for both asynchronous dynamics, the agreement space-time diagram of linear rules is the space-time diagram of the rule itself, in other words, the quotient rule of a linear ECA is itself (see Figure 11).

Remark. This notion of additivity can be generalised as follows: let F ↵ be an ECA, x, y 2 Q U two configurations, and a binary operator on Q. Then F ↵ is an additive ECA with respect to if Definition 2.7. A state q 2 Q is quiescent if f (q, q, q) = q. An ECA is doubly quiescent (DQECA) if both states 0 and 1 are quiescent.

F ↵ (x y) = F ↵ (x) F ↵ (
Remark. The number of regions in a fully asynchronous DQECA configuration cannot increase.

Remark. Any DQECA of size n has at least two fixed points: 0 n and 1 n .

Definition 2.8. An ECA F ↵ is nilpotent if all configuration eventually reach the same quiescent state; that is, if for any ring size n and 8x 2 Q U , 9q 2 Q and 9T 2 N such that 8t T, F t ↵ (x) = q U (for more details, see [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF][START_REF] Mairesse | Around probabilistic cellular automata[END_REF]). However, the notion of nilpotency does not capture the behaviour of CA that can reach multiple quiescent states, here DQECA. This is an interesting behaviour where all initial information is removed, like in the nilpotent case, because any configuration will lead to one of the two possible homogenous states, and it will be of great importance when studying coalescence, so we defined it as follows: Definition 2.9. An ECA F ↵ is homogenising if for any ring size n and 8x 2 Q U ,

P 9q 2 Q, 9T 2 N : 8t T, F t ↵ (x) = q U = 1.
Remark. An ECA may be homogenising under a particular updating style, but this does not imply that it will be homogenising under another kind of updating scheme (see Figure 12). Definition 2.10. An ECA is universal if it is capable of arbitrarily complex behaviour and so able to perform computations of arbitrary sophistication. In particular, given appropriate initial conditions, it can be e↵ectively programmed to emulate any possible CA.

Remark. ECA 110 (124,137,193) are proven to be universal. Wolfram suggested that 27 out of 256 may be universal [START_REF] Wolfram | A new kind of science[END_REF].

Remark. It has been shown that asynchronous CA can simulate arbitrary synchronous CA (by extending the number of states, the dimension or the size of the neighbourhood, for example). From this result a universal asynchronous CA can be easily constructed (see e.g. [23, 25, 32-34, 36, 37] for further insight and [START_REF] Fatès | A guided tour of asynchronous cellular automata[END_REF][START_REF] Worsch | Towards intrinsically universal asynchronous CA[END_REF] for discussions on the issue).

Precedings

The starting point of this research project is Rouquier's PhD thesis [START_REF] Rouquier | Robustesse et mergence dans les systmes complexes: le modle des automates cellulaires[END_REF] and, in particular, one of its chapters rewritten as an article that focuses on coalescing CA [START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF]. In this paper, Rouquier and Morvan coin the term coalescence and first define it as follows: an asynchronous finite CA is coalescing if, for any two initial configurations, applying the same sequence of updates leads both configurations to become identical within polynomial expected time (with respect to n). Notice that for a CA to be coalescent it is required that it coalesces quickly enough. This definition aimed to formalise the first observations of this phenomenon that appeared in [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF]. They formally study the behaviour of six asynchronous ECA and give proofs to the following results:

• The identity rule 204 cannot coalesce.

• For both asynchronous dynamics, 60 is not coalescing.

• 6 and 7 are coalescing for the fully asynchronous dynamics when n is odd.

• 15 and 170, for both asynchronous dynamics, either coalesce or end in total disagreement, each case with probability 1 2 . They also show how to construct coalescing CA with arbitrarily many states. Next, their simulation study of all partially asynchronous ECA is presented and, using the asymptotic density, all rules are classified with respect to coalescence in the following categories: a) CA that never coalesce. b) CA that coalesce rapidly in a trivial way (they converge to a unique fixed point). c) CA that coalesce rapidly to non trivial orbits. d) CA that combine a), b) and c) depending on ↵. e) CA that end in either full agreement between configurations (coalescence) or full disagreement, depending on the sequence of updates and the initial configuration. f) CA that combine e) with either a) or c).

Finally, the authors study the transition between non coalescence and coalescence when ↵ varies for the ECA that combine a) and c), and show that they present a phase transition (abrupt change in macroscopic properties of a system with only a small change of a control parameter around a critical value) belonging to the universality class of directed percolation (see also [START_REF] Fatès | Directed percolation phenomena in asynchronous elementary cellular automata[END_REF]).

Other articles fundamental to our work are [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF], where Fatès et al. analytically study the convergence time of all DQECA which inspired our formal study, and [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF], where Fatès and Morvan use a statistical approach with macroscopic parameters in order to experimentally study the robustness to asynchronism of ECA and which inspired our qualitative study.

In order to explore CA's dynamics, we used FiatLux 2 , a Java based software developed by Fatès which allows one to simulate di↵erent kinds of 1D and 2D CA, using di↵erent updating dynamics and di↵erent topologies. The applet is available on http://fiatlux.loria.fr.

Visualisation and qualitative exploration

We considered that studying ECA instead of trying to find general results for any kind of CA was a good starting point. Moreover, we focused on fully asynchronous dynamics because phase transitions have been observed in partially asynchronous ECA [START_REF] Fatès | Directed percolation phenomena in asynchronous elementary cellular automata[END_REF][START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF], and so their complete analytical study would go beyond the scope of this project.

Before analytically study coalescence, we qualitatively explored the behaviour of all fully asynchronous ECA and their coalescence. This work allowed us to detect quick coalescence (in linear or even logarithmic time), coalescence to a fixed point, coalescence before reaching a fixed point, coalescence to a non trivial configuration, slow coalescence, and di↵erent kinds of non-coalescent behaviour (see Figure 13). The first exploration work was done by comparing two space-time diagrams of the same ECA under the same fully asynchronous dynamics (fixing a seed for the random sequence of updates, we can force both ECA to update the same cells at each time step) and starting from two di↵erent random configurations. We explored the behaviour of the system with di↵erent ring sizes and di↵erent initial conditions (random or particular ones). We repeated these experiments several times in order to evaluate their dependence on the updating sequence.

After that, we developed a new feature of FiatLux allowing us to display the agreement space-time diagram of two ECA, and we repeated the exploration by using this new tool. This visualisation provides further insight into the coalescence style because it displays the dynamics of the disagreement, which may not be straightforward from the side-by-side comparison of two or several space-time diagrams.

By using it, we could quickly verify our previous results and intuitions and, together with an exhaustive study of ECA fixed points, we were able to distinguish trivial from non-trivial coalescence. Furthermore, we could already find some particular configurations and sizes that altered the predominating coalescence behaviour (see Figure 14 and Figure 15). Finally, incrementing the size of the CA, we could also detect coalescent behaviour produced by the use of periodic boundary conditions (see Figure 16).

Thus, this qualitative study allowed us to roughly classify all ECA according to their predominating coalescence behaviour (see Table 5 of Appendix A).

Definitions of coalescence behaviours

In order to analytically study coalescence, first of all we need to define this concept formally.

Let (x t

, y t ) = F t 0 (x, y) denote the random evolution of two configurations updating the same cell at each time step and starting from the initial configurations x = x 0 , y = y 0 2 S ✓ Q U . Then we denote by T xy = inf{t 0 : x t = y t } the random variable representing the first time that the two configurations coincide, that is, the minimum number of time steps needed to observe coalescence. Definition 5.1. We say that a CA coalesces in time t(n) if, for any two initial configurations, applying the same sequence of updates leads both configurations to become identical within expected

time t(n). Formally, if 8x, y 2 Q U , E[T xy ]  t(n).
Notice that this definition includes the extreme case of a CA that only coalesces in "infinite" time, due to its stochastic nature. Informally speaking, these systems have the potential to coalesce but this outcome is highly unlickely. However, if given enough (infinite) time, they will eventually coalesce "by chance". This definition excludes CA that will never coalesce, not even after an infinite time; for example, the identity rule ECA 204. Figure 17 gives several examples of coalescence reached in di↵erent times that inspired this definition. Definition 5.2. We say that a CA is trivially coalescent in time t(n) if its asymptotic behaviour is independent of both the initial configuration and the sequences of updates. That is, if starting from any two initial configurations and applying di↵erent updating sequences still leads both configurations to become identical within expected time t(n).

Figure 18 shows several examples of trivial coalescence.

When we talk about asymptotic behaviour, we informally mean after the system evolved "long enough", meaning that its behaviour will not be substantially di↵erent from the one already observed.

The simplest examples to illustrate this concept are when a CA becomes independent of its initial condition (which can be seen as a perturbation or forced state) or reaches a fixed point (where it will remain forever in a static configuration). The asymptotic behaviour of a CA may appear intuitive from an experimental point of view, but it may easily lead to false or inaccurate statements. It is quite di cult to analytically work with this notion, but a starting point is to use macroscopic parameters (such as the density of one state averaged over 10 6 time steps) and take a statistical approach.

ECA 40 ECA 58 ECA 106 There are several CA that are coalescent in general but they do not coalesce for some specific configurations. For example, taking an unreachable fixed point as one of the initial configurations leads to non-coalescence. Thus we define the following behaviour:

Definition 5.3. We say that a CA coalesces for a proper subset S ( Q U of initial configurations in time t(n) if it is coalescent in time t(n) when restricted to this subset of initial configurations, and it is not coalescent for the complementary set S = Q U \ S. We saw that the ring size may drastically a↵ect the behaviour of a CA (recall Figure 14 and Figure 15) and, thus, its properties such as coalescence, so we can similarly define the following notion:

Definition 5.4. We say that a CA coalesces for a subset N ( N of ring sizes in time t(n) if it is coalescent in time t(n) when restricted to this subset of ring sizes, and it is not coalescent for the complementary set N = N \ N . Some CA, for example those with more than one reachable fixed point, may sometimes coalesce but sometimes not or even reach full disagreement. In order to capture this behaviour we define the following concept:

Definition 5.5. We say that a CA is coalescent with probability p if coalescence is reached with probability p and non coalescence with probability 1 p.

Figure 20 shows an example of an ECA that has two reachable fixed points {0 n , 1 n }. Thus, if both copies end up in the same fixed point, we will observe coalescence. On the other hand, if they converge to di↵erent fixed points we will observe full disagreement. The (non) coalescence of ECA presenting this kind of behaviour will most probably depend on the initial configuration. In particular, some ECA that coalesce with probability p may reach a non coalescent configuration where one of the copies is a translation of the other. Thus: Definition 5.6. We say that a CA is shift-coalescent in time t(n) if after letting it evolve t(n) time steps, there exists a j 2 U such that x t(n) i = {y t(n) } i j for all i 2 U . Figure 21 shows an example of an ECA that may reach a non coalescent state where one configuration is a shift of the other. Notice that this probability p of reaching (shift) coalescence will, in general, be very di cult to determine because of CA's global behaviour complexity and because it should be averaged over every possible initial condition and every possible updating sequence.

Finally, the behaviour of some CA suggests that they might be able to coalesce if they were not forced to update exactly the same cells, because they tend or are very close to reach a coalescent state but this is sometimes impossible because of some di↵erences that cannot be "broke" if both copies follow the same updating sequence (see Figure 22).

Thus, it would be interesting to study the notion of coalescence percentage, which could be an indicator to spot these cases and maybe some other properties related to coalescence. For example, the average coalescence percentage of a CA may be constant over time and for any initial condition, and this would be a clear indicator of non coalescence.

Definition 5.7. At each time step, the coalescence percentage is defined as the ratio a n , where n is the ring size and a is the number of agreeing cells.

If needed, this measure could be averaged for all runs or measured after letting CA evolve for some time.

Analytical tools

In order to formally prove some results we will need the following probabilistic notions and results.

Let ✏ > 0, m, m 0 2 N, and (X t ) t2N be a sequence of random variables taking values in { m, . . . , m 0 }. Let X t = X t X t 1 and (X t ) t2N be the sequence of past values taken by previous random variables up to t. The following lemma bounds the convergence time of a random variable that decreases on expectation.

Lemma 6.1 ([17]). Assume that if X t > 0, then E[ X t+1 |X t ]  ✏. Let T = min{t : X t  0} denote the random variable corresponding to the first time t that X t  0. Then, if X 0 = x 0 , E[T ]  m + x 0 ✏ . Let (X t )
t2N be now a sequence of random variables taking values in {0, . . . , m}.

Definition 6.1 ([17]

). We say that (X t ) t2N is a martingale of type I if for all t:

• E[X t+1 |X t ] = X t , and • if 0 < X t < m, then P ( X t+1 1|X t ) = P ( X t+1  1|X t ) ✏. Let T = min{t : X t 2 {0
, m}} denote the random variable corresponding to the convergence time of a type I sequence (X t ) to one of the two only possible fixed points. The following lemma bounds the convergence time of this random process.

Lemma 6.2 ([17]

). For any type I sequence (X t ), if X 0 = x 0 , the expectation of T satisfies

E[T ]  x 0 (m x 0 ) 2✏ .
Finally, we will also need the following concepts: Definition 6.2. Let f be a function with domain M and a partially ordered set (N, ) as codomain, and let g be a function defined on domain M and having the same codomain (N, ). Then g is an upper bound (resp. lower bound ) of f if g(x) f (x) (resp. g(x)  f (x)) for each x 2 M . An upper or lower bound is said to be sharp if equality holds for at least one value of x 2 M . An upper bound (resp. lower bound) is said to be tight, a least upper bound (resp. greatest lower bound ) or a supremum (resp. infimum) if no smaller value or function is an upper bound (resp. lower bound).

We call energy function a real-valued function giving values to the sequence of random variables (X t ) according to its constraints, allowing us to construct a suitable (X t ) in order to apply the previously stated lemmas.

Analytical study

In this section we will only refer to the minimal representatives of the 88 ECA equivalence classes, but remember that any result proven for one ECA can be easily extended to the other members of its class.

Fixed points and homogenising ECA

Using a de Bruijn diagram (see page 12) we were able to determine all possible fixed points of all ECA (see Table 5 First of all we perform a qualitative exploration in order to find any configuration that would provide a counterexample to the hypothesis that all ECA listed above are possible homogenising candidates.

For the synchronous case, it is easy to find counterexamples for ECA 2,[START_REF] Deutsch | Cellular automaton modeling of biological pattern formation: characterization, applications, and analysis[END_REF][START_REF] Liggett | Interacting particle systems. classics in mathematics[END_REF][START_REF] Macauley | Coxeter groups and asynchronous cellular automata[END_REF][START_REF] Nehaniv | Asynchronous automata networks can emulate any synchronous automata network[END_REF][START_REF] Rouquier | Robustesse et mergence dans les systmes complexes: le modle des automates cellulaires[END_REF][START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF][START_REF] Wang | Limit set problem of multi-agent systems with finite states: An eigenvalue-based approach[END_REF][START_REF] Wolfram | A new kind of science[END_REF]56,58,62,110,130,138,152,154,162,170,and 178 because in general they present a cyclic evolution. We find counterexamples for ECA 32, 40, 160, and 168 if initialised with a (01) n/2 pattern. ECA 18, 54, 60, 106, 122, 126, and 146 present a more complex behaviour, because they present some moving non-trivial structures or self-similarity. However, it is easy to obtain a cyclic evolution providing a counterexamples if initialised with a periodic pattern. In particular, some of the counterexamples we found are: ECA 18, 54, 146 initialised with (0011) n/4 with n = 4k, k 2 N, ECA 60 initialised with (010) n/3 with n = 3k, k 2 N, ECA 106 and 122 initialised with (01) n/2 , and ECA 126 initialised with (0111) n/4 with n = 4k, k 2 N. ECA 0 and 8 are proven to be the only two nilpotent ECA (see e.g. [START_REF] Wang | Limit set problem of multi-agent systems with finite states: An eigenvalue-based approach[END_REF]). Thus, they are homogenising. ECA 128 (EFG) is doubly quiescent and has fixed points {0 n , 1 n } (see page 14). If we start from a configuration di↵erent from the fixed point 1 n there must be at least one 0. Looking at its letter code we clearly see that the size of any present zero-zone can only increase, we also know that the number of zones cannot increase and that a one-zone can disappear once it has size 2 or 1. Thus, ECA 128 is homogenising. Finally, using a similar reasoning than for ECA 128, we can easily conclude that ECA 136 (EG) is also homogenising.

From this study we are able to deduce that the set of homogenising ECA under synchronous dynamics is {0, 8, 128, 136} together with their symmetric ECA.

For the fully asynchronous case, we start by determining the reachability of the set of fixed points of each ECA. With this information we can already detect some non-homogenising ECA.

In particular, it is impossible that ECA 38 (BDFGH), 46 (BDGH), 54 (BCDFGH), 60 (CDGH), 62 (BCDGH), 110 (BDH), and 126 (BCDH) are homogenising because their only fixed point is {0 n } but under fully asynchronous updating it is unreachable from any configuration di↵erent from the fixed point itself, because an isolated 1 (last configuration before reaching the fixed point) could never disappear (E is not active). It is clear that ECA 0 (EFGH) and ECA 8 (EGH) are homogenising.

Using the analytical study and results in [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF] we can easily deduce that fully asynchronous ECA 128,130,136,138,146,152,154,160,162,168,170,178, and 184 are homogenising. Finally, we conjecture that the remaining ECA (listed in Table 4) are homogenising because (a) their only fixed point, which is reachable, is {0 n }; (b) most of them have more active transitions that increase the number of zeros; and (c) all of them have both transitions E and H active. Thus, even if their coalescence to the fixed point could be in theory very slow, they will always eventually reach 0 n . This hypothesis is in accordance with what we observe when modelling these ECA because all except for ECA 122 converge very quickly to the fixed point. On the other hand, we think that ECA 122 could have exponential or even infinite convergence time. However, in order to formally prove this claim we would need to formally demonstrate that these rules will always converge to 0 n for any ring size n and any initial configuration. Thus, we conjecture that the set of homogenising ECA under fully asynchronous dynamics, is {0, 2, 8, [START_REF] Deutsch | Cellular automaton modeling of biological pattern formation: characterization, applications, and analysis[END_REF][START_REF] Fatès | Two-dimensional tra c rules and the density classification problem[END_REF][START_REF] Liggett | Interacting particle systems. classics in mathematics[END_REF][START_REF] Macauley | Coxeter groups and asynchronous cellular automata[END_REF][START_REF] Nakamura | Asynchronous cellular automata and their computational ability[END_REF][START_REF] Nehaniv | Asynchronous automata networks can emulate any synchronous automata network[END_REF][START_REF] Rouquier | Coalescing cellular automata[END_REF][START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF][START_REF] Wolfram | A new kind of science[END_REF]56,58,106,122,128,130,136,138,146,152,154,160,162,168,170,178, 184} together with their symmetric ECA.

Study of trivial coalescence

The first step towards a complete classification of all ECA according to their coalescence behaviour is to identify trivial coalescence.

During our experimental study, we found that there are three possible ways to coalesce (see Figure 23): to a fixed point, before reaching a fixed point or to a configuration which is not a fixed point. The first one is not surprising, the second one is surprising when coalescence happens a long time before reaching a fixed point, and the third one is the most puzzling. For the second case, using di↵erent updating sequences would slow down coalescence and the "worst case" would be to coalesce once the fixed point is reached. Our qualitative exploration shows us that when coalescence happens on a configuration which is not a fixed point, this configuration completely depends on the updating sequence. Thus, we argue that ECA with no fixed points cannot have trivial coalescence. Next, we observe that all ECA having a set of fixed points S * {0 n , 1 n } cannot be trivial because their coalescence will depend on the ring size n.

Thus, we focus again in the set of ECA having a non empty set of fixed points S ✓ {0 n , 1 n } is: {0, 2, 8, 10, 18, 24, 26, 32, 34, 38, 40, 42, 46, 50, 54, 56, 58, 60, 62, 106, 110, 122, 126, 128, 130, 136, 138, 146, 152, 154, 160, 162, 168, 170, 178, 184}. According to the number of fixed points and their reachability, we can classify them as follows:

• ECA with a single fixed point {0 n } which is -Reachable: 0, 2, 8, 10, 18, 24, 26, 32, 34, 40, 42, 50, 56, 58, 106, and Let us start analysing the subset of ECA with two fixed points. If both are reachable, then some configurations may evolve to one of them and some to the other one and thus lead to full disagreement. In particular, the evolutions of the ECA initialised at 0 n and initialised at 1 n could never coalesce. This is a non coalescent behaviour which could be formally described by using the definitions of coalescence with probability p (see Definition 5.5 on page 23). If one of the fixed points is reachable but not the other, we find again a non coalescent behaviour because we are sure that if the ECA is initialised at the unreachable fixed point, it will be unable to coalesce with the evolution of any other initial condition. Thus, this set of ECA is not trivial either. However, it would still be interesting to study their coalescence for the subset {1 n } of initial configurations (see Definition 5.3 on page 22).

If an ECA that only has one fixed point which is unreachable coalesces, it means that it coalesces in a configuration di↵erent from a fixed point and, as discussed above, this configuration will depend on the updating sequence. Thus, this subset of ECA cannot be trivial. Finally, if our classification of homogenising ECA is correct, then we can conclude that the set of ECA with trivial coalescence (i.e., both independent of the initial configuration and the sequence of updates, see Definition 5.2 on page 21) are the subset of ECA (conjectured homogenising) that have {0 n } as only fixed point and it is reachable, that is, ECA 0, 2, 8, 10, 18, 24, 26, 32, 34, 40, 42, 50, 56, 58, 106, and 122. Most of them coalesce very quickly, i.e., in logarithmic time, few do it more slowly (they could take linear or quadratic time), and only ECA 122 does not coalesce quickly (we leave for future works the proof of its W ECT 122 (see Definition 2.4 on page 11), which could be exponential or even infinite). However, these claims should be formally proven by finding lower and upped bounds to the coalescence time

t(n).
With all this information, we further claim that trivially coalescent ECA will coalesce in time t(n) = W ECT f (see Definitions 2.4, 5.1 and 5.2).

Quadratic coalescence study

We have seen that coalescence may happen either if there is convergence to a fixed point or not. It is not very surprising when there is convergence to a fixed point and coalescence happens when this fixed point is reached. This kind of coalescent behaviour could be fully determined by studying the W ECT f of these rules. However, we experimentally found that some ECA which are attracted to a (sometimes unreachable) fixed point coalesce a long time before this fixed point is reached, and this surprising behaviour cannot be fully determined by studying the W ECT f , because it will not correspond to the coalescence time.

Among the ECA presenting this kind of behaviour, we chose to study rule 154 (BCEG), which is doubly quiescent (see Definition 2.8 on page 14), because even though it takes a very long time to reach a fixed point, its coalescence is rather fast. In particular, we would like to prove that it has a quadratic coalescence for any initial condition but the unreachable fixed point.

Using a de Bruijn diagram, it is easy to see that ECA 154 (BCEG) has only two fixed points: 0 n and 1 n . However, under fully asynchronous updates and starting from any configuration di↵erent from 1 n , only 0 n is reachable because an isolated zero could never disappear (D is not active).

Local behaviour analysis

We start by analysing how zones evolve in ECA 154. First of all, notice that any zero-zone having a size smaller than the ring size n limits with one-zones, and so it has a left frontier [START_REF] Deutsch | Cellular automaton modeling of biological pattern formation: characterization, applications, and analysis[END_REF] and a right frontier (01), which we will respectively denote by L and R.

The active transitions of ECA 154 are B, C, E and G. From a detailed exploration of its letter code (see page 7), we can derive the following facts (see Figure 24):

• Since transitions A and H are not active, the number of zones cannot increase.

• The application of transitions B and C will increment the number of ones whilst the application of transitions E and G will increment the number of zeros.

• Since D is not active, an isolated zero cannot disappear. This implies that a zero-zone cannot disappear.

• The size of a zero-zone can evolve with the only constraint that it will bounce in case it has size one because D is not active.

• Since E is active, two zero-zones can merge once they are separated by only one zero. This implies that the number of zero-zones can decrease.

• Transitions B and C are only applicable if there is at least one zero-zones of size two or more.

If so, transition B can be applied on its right boundary, and this would move R to the left and reduce the size of the zero-zone by one. Similarly, transition C can be applied on its left boundary, and this would move L to the right and reduce the size of the zero-zone by one.

• Transition G is only applicable where a zero-zone limits to its left-hand side with a one-zone of at least size two. If so, then the application of transition G would move L to the left and increase the size of the zero-zone by one.

• Since transition F is not active, a zero-zone cannot increment its size from the right-hand side frontier unless it merges from the right hand side with another zero-zone because transition E is applicable.

Global behaviour analysis

If we visualise the evolution of ECA 154 (see Figure 25) we see that the number of ones increases very quickly and zero-zones travel in average to the left forming streaks and merge when they meet. This global behaviour can be explained from its local behaviour as follows: • Zero-zones in ECA 154 tend to reduce their size (except when they have size one or when they merge with another zero-zone after applying transition E) because two active transitions (B and C) can reduce it and only one increase it (transition G). This implies that the number of ones increases in general.

• Zero-zones in ECA 154 travel in general to the left (except when they merge with another zerozone after applying transition E) because the right boundary R can either remain or move to the left each time transition B is applied, and the left L boundary behaves as a random walk because transitions C and G act on it in opposite directions; i.e. each time that transition C is applied L moves to the right, and each time that transition G is applied L moves to the left.

• Zero-zones tend to merge because left boundaries travel faster than the right ones in average. These observations will be formally proven in the following section by using Markov chains.

Remember that ECA 154 has a reachable fixed point 0 n and an unreachable fixed point 1 n . Hence, with the information we have so far we see that this ECA tends rather quickly to a configuration with a single zero-zone, the size of which will behave as a random walk biased against the reachable fixed point. In particular, it can be shown that ECA 154 will eventually converge to 0 n with a W ECT 154 in ⇥(2 n ) [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF].

Mathematical analysis

We can analytically describe the evolution of the size of any zero-zone by means of the following Markov chain

1 2 3 ... n 1 n 1 ✏ ✏ 1 3✏ 2✏ ✏ 1 3✏ 2✏ ✏ 2✏ ✏ 1 3✏ 2✏ ✏ 1
where n is the ring size.

Thus, we see that zero-zones have a small size with high probability and that size one is a bouncing state. The state probabilities when n and t go to infinity can be found as follows:

Let i 2 {1, . . . , n} and p

(t) i = P(X t = i),
where t is the time step and X t a random variable taking values in {1, . . . , n} representing the length a zero-zone can have. For i 2,

p (t) i = (1 3✏)p (t 1) i + 2✏p (t 1) i+1 + ✏p (t 1) i 1 .
Thus, when t goes to infinity, we have:

8i 2, lim t!1 p (t) i = p i = p i 1 + 2p i+1 3
.

For i = 1 we have that

p (t) 1 = (1 ✏)p (t 1) 1 + 2✏p (t 1) 2
, so that when t goes to infinity, p 1 = 2p 2 . We can solve this recursive equation as follows:

x 2 3 2 x + 1 2 = (x 1)(2x 1) = 0
which has roots 1 and 1 2 , so

p i = ↵ + ✓ 1 2 ◆ i .
Together with

p 1 = 2p 2 and knowing that X i 1 p i = 1
we can deduce that ↵ = 0 and = 1. Hence p i = 1

to the left with an average speed v of p✏, because G is the only active transition applicable in this situation. For any other size, the left frontier L will not move in average because both C and G will be equiprobably applicable and they move L in opposite directions. This can be formally written as follows: let Z t be the random variable indicating the position of L and let

Z t+1 = Z t+1 Z t . If X t = 1 (state H n 3 GDF), then E[ Z t+1 | x t ] = ✏, else E[ Z t+1 | x t ] = 0.
In particular, since we found that p = 1 2 and taking ✏ = 1 n , v = 1 2n . This can be illustrated with the experiment shown in Figure 26. According to these results, if we start from two zero-zones that are far apart and they both travel in the same direction (sense) and at the same average speed, they should in average never coalesce if there is no randomness. However, there is randomness in a fully asynchronous ECA because at each time step a cell is randomly and uniformly selected to be updated, i.e., it is a stochastic process.

Thus, what we need to prove now is that these streaks moving to the left will merge.

We have seen that the left frontier L of a single zero-zone having size greater than one will not move in average. How is it possible, then, that we observe white streaks (zero-zones) moving rather quickly to the left? The answer is because, when a zero-zone has size greater than one, transition B is applicable on the right boundary R, it moves it to the left and reduces the size of the zero-zone by one; and we have already proved that size one is the most probable state in the Markov chain representing the size evolution of a zero-zone.

We experimentally observe that all zero-zones merge until only one is left, and ECA 154 coalescence usually takes place when the two single zero-zones of each copy coincide. Thus, studying the merging of two zero-zones we will be able to characterise the global behaviour of this ECA and bound its coalescence time.

Our hypothesis is that ECA 154 coalesces in ⇥(n 2 ), i.e., quadratic time. In order to formally prove this claim we would have to provide quadratic lower and upper bounds. This is quite di cult, especially because any claim or general property about an ECA has to be proven for any ring size and any possible initial condition. This is a computationally untreatable figure without a proper previous formal study which reduces the number of study cases. In what follows, we will provide a lower bound and a particular case of upper bound.

Lower bound

Two copies of ECA 154 following the same fully asynchronous sequence of updates and starting from an initial configuration with a single zero-zone will not be able to coalesce before these two possibly disagreeing zones meet in the agreement space-time diagram; i.e. the two zero-zones reach the same position at the same time (see Figure 27). Thus, a lower bound to ECA 154 coalescence time will be given by the expected time that it takes for two separate zero-zones to meet. Let n be the ring size and k 2 {0, ..., n} be the distance between two zero-zones. Since we have periodic boundary conditions, we take the distance that goes from one zero-zone to the other without crossing any ring boundary. Thus, we will first only be concerned about the right boundary of the zero-zone in the left hand side position and with the left boundary of the zero-zone in the right hand side. Later we will see that we can treat the zero-zones as points on a line without loss of generality.

From the previous analysis we know that a zero-zone will have, in average, size one with probability 1 2 , and so it will have a size bigger than one with probability 1 2 . Thus, we have:

• With probability 1 4 both zero-zones will have size one. In this situation, only transition G applied in the right hand side zero-zone will modify the distance between zero-zones. Hence, k will be reduced by one with probability 1 n .

• With probability 1 4 both zero-zones will have size greater than one. In this situation we will go to k 1 with probability 1 n (because of transition G possible application in the right hand side zero-zone) and to k + 1 with probability 2 n (because of transition C possible application in the right hand side zero-zone and transition B possible application in the left hand side zero-zone).

• With probability 1 4 the zero-zone in the left hand side will have size one and the other one will have size greater than one. In this situation, only transition C and G applied in the right hand side zero-zone will modify the distance between zero-zones. In particular, we will obtain k + 1 with probability 1 n and k 1 with probability 1 n . • With probability 1 4 the zero-zone in the left hand side will have size greater than one and the other one will have size one. In this situation, only transition B applied in the left hand side zero-zone and G applied in the right hand side zero-zone will modify the distance between zero-zones. In particular, we will obtain k + 1 with probability 1 n and k 1 with probability 1 n . Hence we have that the distance between two zero-zones will increase by one with probability n . We conclude that, in average, it has the same probability to increase than to decrease. Thus, the distance k behaves as an unbiased random walk and, without loss of generality, we can study it as follows:

Since we are in a ring, there are two possibilities that two zero-zones can meet: if the right one catches the left one or if the left one catches the right one (by crossing the boundary and becoming the zero-zone in the right). Let T k be the expected time to reach 0 or n from position k. Then

E[T k ] = 1 2 E[T k 1 ] + 1 2 E[T k+1 ] + 1,
which rewritten in the form of a recursive equation becomes

l k = l k 1 2 + l k+1 2 + 1,
that has solution l k = k 2 + ↵k + . Knowing that l(0) = l(n) = 0, we can deduce that ↵ = n and = 0, so that

l k = k(n k). Thus, max k E[T k ] = n 2 (n n 2 ) = n 2 4 , because k = n 2
is the maximum distance to both 0 and n. From the definition of coalescence, we have that

t(n) = max x,y E[T xy ] E[T xy ] for all x, y 2 Q U .
Thus t(n) l () 9x, y such that E[T xy ] l. This means that finding a particular lower bound for E[T xy ] gives us a general lower bound for t(n). Notice that in order to avoid trivial lower bounds such as t(n) > 0, we would like to find sharp or tight bounds (see Definition 6.2 on page 26).

We discussed above that coalescence cannot happen before the two last zero-zones (in di↵erent copies) meet, and we found that this meeting time is bounded by n 2 . Thus, we can say that ECA 154 coalescence time t(n) n 2 has a quadratic lower bound; i.e. t(n) = ⌦(n 2 ).

Particular upper bound

Let

t | K t ] = 1 4n 1 4n = 0, so (K t ) is a martingale, and if 0 < K t < n, then P ( K t+1 1 | K t ) = P ( K t+1  1 | K t ) = ✏ = 1 4n
. Thus, we can apply Lemma 6.2 (see page 25) and obtain

E[T k ]  k 0 (n k 0 ) 2✏ = 2n 2 k 0 2nk 2 0 = 2nk 0 (n k 0 )
where k 0 is the initial distance between two zero-zones.

This gives us a particular quadratic upper bound for E[T xy ], but it is not a general upper bound for t(n) because 9x, y :

E[T xy ]  u 6 =) t(n)  u.

Linear coalescence study

In this section we choose to study one of the most surprising coalescent behaviours, namely when an ECA coalesces very quickly to a configuration which is not a fixed point. From the ECA presenting this kind of behaviour, we choose to study rule 62 (BCDGH). We conjecture that ECA 62 (and also ECA 38 and ECA 46 which present a similar behaviour) coalesces in linear time (see Figure 28).

Upper bound

In order to find a linear upper bound, we would like to construct an always-decreasing energy function for any ring size and any initial configuration and apply Lemma 6.1 to it (see page 25). We studied all possible transitions in all possible neighbourhoods of size 5 and created a Java program in order to test our hypothesis. However, we could not find yet an always decreasing energy function that would allow us to apply Lemma 6.1 and give proof of the existence of a linear upper bound.

Conclusion

We have defined and studied cellular automata (CA). From their general definition we focused on the study of elementary cellular automata (ECA) with periodic boundary conditions. We studied their basic properties and saw that the total of 256 ECA can be reduced to 88 equivalence classes.

We were able to visualise their global behaviour by plotting their space-time diagram using FiatLux software. We discussed di↵erent updating schemes, namely synchronous, partially asynchronous and fully asynchronous and their influence in the dynamics of a CA. Then we informally defined the concept of coalescence and extended FiatLux in order to plot what we called agreement space-time diagram, which is the superimposition of two space-time diagrams showing the di↵erence between them.

With this tool we performed an extensive qualitative exploration of the coalescent behaviour of the 88 minimal representatives of all ECA under fully asynchronous dynamics. From this experimental exploration we distinguished several di↵erent kinds of coalescence styles (e.g. trivial, for a subset of configurations, etc.), which we later fully characterised after formally defining coalescence.

The general goal of this project was to give the first steps towards a global classification of all ECA according to their coalescence behaviour. We did a first rough classification based on our experimental study, but conjectures need to be formally proven. However, this is a di cult task because all claims need to be proven for any ECA size and any possible initial configuration. After more than 40 years of study and lots of e↵ort, it is still di cult for the community to even classify the set of synchronous ECA, which are deterministic and the simplest kind of CA. This clearly shows the hidden complexity of this kind of discrete systems. We are very far from reaching a complete characterisation of this new CA property, but maybe the study of new and old ECA features will allow us to understand them or at least provide a full taxonomy.

Nevertheless, we started the analytical study of coalescence in fully asynchronous ECA and were able to give some formal proofs. In particular, we analytically studied trivial coalescence and conjectured that the only fully asynchronous ECA that could have this kind of coalescence (independent of both the initial condition and the sequence of updates) are ECA 0, 2, 8, 10, 18, 24, 26, 32, 34, 40, 42, 50, 56, 58, 106, and 122.

We conjectured that ECA 154 coalesces in quadratic time for any initial configuration di↵erent from 1 n and began the formal proof of this statement by finding a quadratic lower bound and a particular upper bound. We also conjectured that ECA 62 coalesces in linear time and began the formal proof of this claim by finding a linear lower bound and suggesting an analytical way to find a linear upper bound in order to prove the conjecture. In particular, we propose to find an alwaysdecreasing energy function (this can be tested for any size and configuration using our Java code) to be able to apply a mathematical result that would give us a linear upper bound for any size and any initial configuration.

These results have been obtained after a four-months research internship. They are still partial and might seem limited, but these are some of the first steps in the study of coalescence. We should keep working in order to further understand cellular automata and their significance.

A Taxonomy table

Figure 1 :

 1 Figure 1: Space-time diagram (see page 7) showing the evolution, from bottom to top, of ECA 90, where each row represents the ECA state at consecutive times. The initial configuration is the bottom row, where there is a single cell in state one (blue), and the rest are in state zero (white).

Figure 3 :

 3 Figure 3: Evolution, from bottom to top, of ECA 2 under fully asynchronous updating (see Section 2.2) and starting from two di↵erent initial configurations (left and centre). Diagram with the superimposition of both CA showing their di↵erences in green and orange (right).

Figure 4 :

 4 Figure 4: Evolution, from bottom to top, of ECA 46 with periodic boundary conditions (see page 8) following the same partially asynchronous updating sequence (see Section 2.2) and starting from two di↵erent initial configurations (left and centre). Diagram with the superimposition of both CA

Figure 5 :Example 2 . 1 .

 521 Figure 5: Space-time diagram of ECA 182 (BCDFG) starting from a configuration with a single one (blue cell) and where each cell is simultaneously updated at each time step. Time, thus, goes upwards.

Figure 6 :

 6 Figure 6: Space-time diagrams of ECA 146 (BCEFG) with periodic boundary conditions and ↵ = 1 (left), ↵ = 0.5 (centre), and ↵ = 0 (right), all starting from the same initial configuration. Note that, for the fully-asynchronous case (right), the k-th line from bottom to top corresponds to the configuration at time t = nk, where n is the size, whilst for the other dynamics, t = k (centre and left).

Example 2 . 3 .

 23 From a de Bruijn diagram we can deduce that the set of fixed points of ECA 45 (ADGH) with ring size n = 3k is {(001) k } because the only possible cycle of inactive transitions (B, C, E, F) is BEC. Note that this fixed point will be impossible to reach if n 6 = 3k, where k 2 N.

Figure 7 :

 7 Figure 7: De Bruijn diagram representing all possible transitions of an ECA. Each node is one of the eight possible neighbourhoods (labelled with the letter code presented in Table 2 on page 7). Each path of length k corresponds to a possible configuration of size n = 3 + k. Each cycle corresponds to a possible fixed point.

Figure 8 :

 8 Figure 8: Space-time diagrams of four equivalent ECA with periodic boundary conditions. Changing the initial configuration accordingly and using synchronous updating, we can see that ECA 2 (top left) is indeed equivalent to ECA 16 (top right) under reflection, to ECA 191 (bottom left) under conjugation, and to ECA 247 under both reflection and conjugation.

  Lemma 2.1 ([42, page 6]). For both asynchronous dynamics, a ne ECA rules are exactly the rules for which the agreement space-time diagram is the space-time diagram of an elementary cellular automaton.

Figure 9 :

 9 Figure 9: Space-time diagrams of four equivalent ECA with periodic boundary conditions. Changing the initial configuration accordingly and using synchronous updating, we can see that ECA 45 (top left) is indeed equivalent to ECA 101 (top right) under reflection, to ECA 75 (bottom left) under conjugation, and to ECA 89 under both reflection and conjugation.

  y) for any x and y[START_REF] Wolfram | A new kind of science[END_REF].

Figure 10 :

 10 Figure 10: We can see that the agreement space-time diagram of fully asynchronous ECA 105 (left), exactly corresponds to the space-time diagram of ECA 150 (right). Thus, ECA 150 is the quotient rule of ECA 105.

Figure 11 :

 11 Figure 11: The agreement space-time diagram of fully asynchronous ECA 90 (left), is equal to the space-time diagram of the same rule (right). Thus, applying exactly the same sequence of updates, the quotient rule of ECA 90 is itself.

Figure 12 :

 12 Figure 12: ECA 2 is homogenising under fully asynchronous dynamics (left) but not under a synchronous updating scheme (right).

2

 2

Figure 13 :

 13 Figure 13: Qualitatively di↵erent examples of di↵erent coalescence styles. From left to right, ECA 40, 58, 62, 154, 184, 51, 14 and 1.

Figure 14 :

 14 Figure 14: ECA 15 with periodic boundary conditions and under fully asynchronous dynamics with an even ring size of n = 50 is able to reach the fixed point (01) n/2 (left) but this configuration is unreachable when an odd ring size of n = 49 is used (right).

Figure 15 :

 15 Figure 15: ECA 90 with periodic boundary conditions and under synchronous dynamics with ring size n = 50 (left) and ring size a power of two, like n = 64 (right), have a completely di↵erent asymptotic behaviour.

Figure 16 :

 16 Figure 16: ECA 37 with periodic boundary conditions and under fully asynchronous dynamics with ring size n = 50 (left) and ring size n = 500 (right), where we can note that the coalescence of the first is apparent and due to the e↵ect of periodic boundary conditions.

Figure 17 :

 17 Figure 17: All depicted ECA have periodic boundary conditions and fully asynchronous dynamics. From left to right, coalescence reached in logarithmic (O(log n)), logarithmic (O(log n)), linear (O(n)) and quadratic times (O(n 2 )).

Figure 18 :

 18 Figure 18: Examples of trivial coalescence. All depicted ECA have periodic boundary conditions and fully asynchronous dynamics.

Figure 19 shows

 19 Figure 19 shows an example of an ECA coalescent for S = Q \ {1 n } = 1 n ; i.e. an ECA having two fixed points: one (1 n ) unreachable from any configuration di↵erent from the fixed point itself, and the other one (0 n ) reachable from any other configuration.

Figure 19 :

 19 Figure 19: Space-time diagrams of ECA 130 with periodic boundary conditions and under fully asynchronous dynamics with initial configuration the fixed point 1 n (left) and starting from a random initial configuration (centre). Agreement space-time diagram showing that full disagreement is quickly reached (right).

Figure 20 :

 20 Figure 20: Agreement space-time diagrams of ECA 170 with periodic boundary conditions and under fully asynchronous dynamics reaching full agreement (left) and reaching full disagreement (right).

Figure 21 :

 21 Figure 21: Agreement space-time diagrams of ECA 15 with periodic boundary conditions and under fully asynchronous dynamics reaching full agreement (left) and reaching full disagreement where one configuration is a shift of the other (right).

Figure 22 :

 22 Figure 22: From left to right, agreement space-time diagrams with periodic boundary conditions and under fully asynchronous dynamics of ECA 134 reaching coalescence, ECA 134 unable to reach full coalescence because of some small remaining disagreement, ECA 142 very close to coalescence but unable to reach it, and ECA 142 very close to full disagreement.

Figure 23 :

 23 Figure 23: From left to right, agreement space-time diagrams of ECA 58, 154 and 62 with periodic boundary conditions and under fully asynchronous dynamics. ECA 58 coalesces once its only fixed point 0 n is reached (left); ECA 154, which has one reachable fixed point (0 n ) and an unreachable one (1 n ), coalesces a long time before reaching the fixed point (centre, full coalescence is not shown due to space constraints); and ECA 62 has a single fixed point which is unreachable, but it quickly coalesces to a non trivial configuration (right).

Figure 24 :

 24 Figure 24: Space-time diagrams of ECA 154 with periodic boundary conditions and under fully asynchronous dynamics starting from an initial configuration with a single zero-zone (left) and starting from an initial configuration with two zero-zones (right).

Figure 25 :

 25 Figure 25: Evolution, from bottom to top, of ECA 154 with periodic boundary conditions following the same fully asynchronous updating sequence and starting from two di↵erent initial configurations (left and centre). Diagram with the superimposition of both CA showing their di↵erences in green and orange and their agreement in white and grey (right).

Figure 26 :

 26 Figure 26: From bottom to top, evolution of fully asynchronous ECA 154 with ring size n = 50 starting from a configuration with a single zero (white cell) during 100 time steps. This example shows that, indeed, the zero-zone travels to the left with an average speed of 1 2n = 1 100 .

Figure 27 :

 27 Figure 27: Two space-time diagrams of ECA 154 with periodic boundary conditions following the same fully asynchronous sequence of updates and starting from a single 0 (left and centre). The agreement space-time diagram illustrates that coalescence is not possible before the two zero-zones meet (right).

n

  and will decrease by one with probability 14 1

Figure 28 :

 28 Figure 28: Evolution, from bottom to top, of ECA 62 with periodic boundary conditions following the same fully asynchronous updating sequence and starting from two di↵erent initial configurations (left and centre). Diagram with the superimposition of both CA showing their di↵erences in green and orange and their agreement in white and grey (right).

Table 1 :

 1 This example of transition function corresponds to rule 210 = 11010010 2 .

1

Another original notation was proposed by

Macauley et al. in

Table 2 :

 2 This example of transition function corresponds to rule BCEF, which is rule 210 in Wolfram's notation.

Table 3 :

 3 Examples of resulting configuration after the application of an active transition.

	1 000 11010111 10 001 1010111	100 011010111 10001 101 0111
	# A 101011010111	# B 100111010111	# C 110011010111	# D 100011110111
	100011 010 111 100 011 010111 1000 110 10111 100011010 111
	# E 100011000111	# F 100001010111	# G 100010010111	# H 100011010101
	Note that this is the local behaviour of each possible transition if updated separately. The
	combination of several updates applied at the same time on the same neighbourhood can
	produce di↵erent global behaviours (see Note on page 10).

Table 4 :

 4 List of ECA conjectured to be homogenising. They are listed together with their letter code, arranged in columns according to the number of active transitions, and sorted out by the number of active transitions that increase the number of ones.

	10	BEGH	2	BEFGH	18 BCEFGH	50 BCDEFGH
	24	CEGH	32	DEFGH	34 BDEFGH
	40	DEGH	26	BCEGH	58 BCDEGH
	106 BDEH	42	BDEGH
			56	CDEGH
			122 BCDEH

  122. -Not reachable: 38, 46, 54, 60, 62, 110, and 126. • ECA with two fixed points {0 n , 1 n } of which -Both are reachable: 160, 162, 168, 170, 178, and 184.

	-One is reachable and the other one is unreachable: 128, 130, 136, 138, 146, 152, and 154.

  K t be the random variable taking values in {0, ..., n} representing the distance between two zero-zones, let K t = K

	t	K	t 1 , and let (K	t )	t2N be the sequence of past values taken by K	t up
	to t. Then, with the previous study it is clear that (K	t )	t2N is a sequence of random variables of type
	I (see Definition 6.1 on page 25) because E[ K

Table 5 :

 5 Each row corresponds to one of the 88 minimal representatives ECA. Their Wolfram's code is given in the first column, together with the code of the rest of ECA belonging to the same class. The second column contains Fatès' letter code for the minimal representative. The third column gives the set of fixed points of the minimal representative. Conjectures about the coalescent behaviour of each of the 88 ECA are given in the fourth column. Notice that this classification is experimental-based and provisional until it is formally proven. Columns five, six and seven give visual examples of the global behaviour and coalescence style of each minimal ECA. If needed, some comments are given in the rightmost column. BFH j G(DFH k G) l ) m

	! 44

DE 0 n , 1 n , (CA i BFH j G) k -

i when n is large enough. Studying the evolution of a single zero-zone, we see that if the probability of having length one (i.e. being in configuration H n

GDF) is p, then a zero-zone (actually, its left frontier 10) will move

Acknowledgements

I would like to thank both of my supervisors for their guidance, encouragement and advice. They have both been very attentive and helpful.

Using a de Bruijn diagram, it is easy to see that ECA 62 (BCDGH) has only one fixed point 0 n . However, under fully asynchronous dynamics and starting from any configuration di↵erent from 0 n , this fixed point is unreachable because an isolated one could never disappear (E is not active).

Lower bound

After performing a similar qualitative study and mathematical analysis than the one we realised in the previous section for ECA 154 (see Figure 29), we deduce that, if each copy has a single one-zone, coalescence cannot happen before these one-zones meet. Let k be the distance between two one-zones. Then the furthest apart that they can be from each other is n 2 (because we have periodic boundary conditions). Then, to go from k = n 2 to k = 0 (i.e., the two one-zones meet), we need in average at least n 4 time steps. This gives us a linear lower bound, because

Wolfram's code