Katsunobu Imai
email: imai@iec.hiroshima-u.ac.jp

Takahiro Hatsuda
email: thatsuda@iec.hiroshima-u.ac.jp

Victor Poupet
email: victor.poupet@lirmm.fr

Kota Sato
email: ksatou@iec.hiroshima-u.ac.jp

A 6-state Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings

In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose.

We show that, despite the irregularity of the underlying grid, it is possible to devise a semitotalistic CA capable of simulating any boolean circuit and any Turing machine on this aperiodic tiling.

Introduction

Since the discovery of quasi-periodic tilings and the related quasi-cristals, much research work has been done to study the behavior of cellular automata working on the resulting aperiodic structure.

In 2002, McClure designed a 3-states stochastic cellular automaton whose behavior converges to a stable 3-coloring of Penrose tilings [START_REF] Mcclure | A Stochastic Cellular Automaton for Three-Coloring Penrose Tiles[END_REF]. In 2005, Chidyagwai and Reiter showed that the broken symmetry of quasi-periodic tilings, while still retaining a highly organized structure, could be used to simulate the complex growth of snow crystals [START_REF] Chidyagwai | A local cellular model for growth on quasicrystals[END_REF] by studying real-valued CA on such lattices. They could produce global n-fold symmetry models where regular hexagonal grids could only produce 6-fold symmetry models.

Reiter also investigated the behaviors of cyclic CA rules on several quasi-periodic tilings. Cyclic CA are special CA that can be regarded as a model of excitable media [START_REF] Dewdney | Computer recreations: a cellular universe of debris, droplets, defects and demons[END_REF][START_REF] Fisch | Cyclic cellular automata and related processes[END_REF]. Once a cell enters a specific state, it must go through a fixed cycle of other states before being active again, thus implementing a refractory period mechanism. Reiter found that cyclic CA on quasi-periodic tilings, despite having a very simple local behavior, can take advantage of the lattice geometry to exhibit complex and smooth spiral patterns [START_REF] Reiter | Medley of spirals from cyclic cellular automata[END_REF]. A variety of Cyclic CA rules are illustrated and commented on Wojtowicz's online CA rules lexicon [START_REF] Wójtowicz | Cellular Automata rules lexicon[END_REF].

Variants of John H. Conway's Game of Life [START_REF] Gardner | Mathematical Games -The fantastic combinations of John Conway's new solitaire game[END_REF] have also been studied on Penrose tilings. In particular, Owens and Stepney found many stable and periodic patterns, similar to the ones known in the usual euclidian Game of Life [START_REF] Owens | Investigation of the Game of Life cellular automata rules on Penrose tilings: lifetime, ash and oscillator statistics[END_REF][START_REF] Owens | The Game of Life rules on Penrose tilings: still life and oscillators[END_REF]. Despite this, no equivalent to the glider structures of the euclidian case are known on quasi-periodic variants of the Game of Life. Indeed, because of the non-periodic nature of the underlying grid, the very definition of gliders is unclear.

Some other works on CA working on aperiodic structures have also been described in books or web sites [START_REF] Griffeath | A CA run on Penrose Tiles[END_REF][START_REF] Weeks | Cellular automata on quasicrystals[END_REF][START_REF] Wolfram | New Kind of Science[END_REF].

In this paper, we investigate some semi-totalistic CA on Penrose's kite and dart aperiodic tiling of the plane. We show in particular that there exists a 6-state semi-totalistic CA capable of simulating any boolean circuit based on our previous 8-state version [START_REF] Imai | A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings[END_REF]. The usual difficulty of synchronizing signals, made even more problematic in an aperiodic setting, is avoided by embedding universal asynchronous logical elements. This construction is similar to that employed to construct a universal CA on an hyperbolic space [START_REF] Imai | A Five-State von Neumann Neighbor Universal Hyperbolic Cellular Automaton[END_REF]. Once we are able to simulate logical circuits, we use Morita's construction [START_REF] Morita | Constructing a reversible turing machine by a rotary element, a reversible logic element with memory[END_REF] to simulate a Turing machine with simple finite memory logical elements.

2 Semi-totalistic Cellular Automata on Penrose Tilings

Penrose's Kite and Dart Tiling

This famous tiling of the plane was discovered by Roger Penrose as a simplification of his previous 6tiles aperiodic tilings. It is generated by two quadrilateral proto-tiles : a convex one called kite and a non-convex one called dart. To avoid periodic arrangements, tiling constraints are added on the tiles [START_REF] Gardner | Extraordinary nonperiodic tiling that enriches the theory of tiles[END_REF]. Figures 1 and2 illustrate the tiles and their possible combinations. It is known that there exist infinitely many different possible tilings of the plane with the kite and dart tiles. They are all aperiodic but quasi-periodic, that is to say that there exists a constant k ∈ R such that for any r ∈ R, any finite pattern of size r × r that appears somewhere on the tiling appears in every square window of size kr × kr.

Much more is known about this tile set and the resulting tilings of the plane but these are the only properties that we will need for this article.

The Moore Neighborhood on a Penrose Tiling

In order to define a CA on a Penrose tiling, we need to define a neighboring relation between the different tiles. To do so, we extend the usual Moore neighborhood (8 closest neighbors on the regular square grid) by considering that two Penrose tiles are neighbors if they share at least one vertex.

Because all tiles are not identical and not periodically arranged, different tiles might have different neighborhood. In the case of the kite and dart tiling, there are 8 different possible neighborhoods [START_REF] Owens | Investigation of the Game of Life cellular automata rules on Penrose tilings: lifetime, ash and oscillator statistics[END_REF], illustrated by Figure 3.

It is important to notice that not only these neighborhoods have different shapes, they also have different sizes ranging from a minimum of 9 cells to a maximum of 11. Although this would normally be a problem when defining a cellular automaton (because it would not be possible to define a unified rule for all cells), we will see that the special class of semi-totalistic CA is especially well suited for non-homogeneous neighborhoods.

Semi-totalistic Cellular Automata

Because we want to work on aperiodic tilings of the plane, the usual definition of a cellular automaton must be changed in order to be compatible with the fact that different cells might have different neighborhoods. The subclass of semi-totalistic cellular automata is particularly well suited for this as the position of the different neighbors is irrelevant, only the number of neighbors in a given state has an effect on the evolution of a cell.

Definition 1 (Semi-totalistic Cellular Automaton) A semi-totalistic cellular automaton is a pair A = (N, δ ) where :

• N ∈ N is the number of states of the automaton. The set of states of the automaton is therefore

Q A = {0, 1, . . . , N -1} ; • δ : Q A × N N → Q A is the totalistic local transition function of the automaton.
Definition 2 (Configuration) A configuration of the automaton A = (N, δ ) over a tiling of the plane by Penrose's tiles is a mapping C that associates a state of Q A to each tile.

In accordance with usual cellular automaton terminology, in this context, the tiles of the Penrose tiling will be denoted as cells.

Definition 3 (Global Evolution) Given a configuration C, the image C ′ of C by the automaton

A = (N, δ ) is such that for each cell c, the state C ′ (c) is defined by C ′ (c) = δ (q c , n 0 , n 1 , . . . , n N-1 )
where q c is the current state of c and for every i ∈ 0, N -1 , n i is the number of neighbors of c in state i.

We will denote by A (C) the image of a configuration C by such a process. The global action of the automaton can be iterated over each new configuration, defining in such a way the infinite evolution of the initial configuration.

In other words, at each time every cell of the automaton updates its state according to the number of neighbors it has in each state.

Remark: In order to be as general as possible, and to be able to define a CA independently of the lattice on which we will consider it, we have defined the local transition function as a function from and infinite set Q A × N N . However, once the geometric structure of the cells has been decided (in our case the Penrose tiling), it is sufficient to define the local transition function over the tuples that can actually appear. In particular, since we know that in the kite and dart tiling all cells have between 9 and 11 neighbors (themselves included), only the input tuples of the form (q, n 0 , n 1 , . . . , n N-1 ) where 9 ≤ ∑ i n i ≤ 11 should be considered.

Previous Studies

Owens and Stepney studied the Game of Life on Penrose tilings [START_REF] Owens | Investigation of the Game of Life cellular automata rules on Penrose tilings: lifetime, ash and oscillator statistics[END_REF][START_REF] Owens | The Game of Life rules on Penrose tilings: still life and oscillators[END_REF].

Even though the average size of the neighborhoods is larger than that of the standard Moore neighborhood in the regular case, the same parameters for the rule (a cell survives with 2 or 3 live neighbors and a new cell is born when surrounded by 3 live neighbors) exhibits behaviors very similar to the classical Game of Life and many similar stable and periodic patterns were found.

However, no glider or similarly propagating pattern has been found so far, possibly because of the strong irregularity of the encountered geometry as the signal moves. Gliders being the heart of the computational and intrinsic universality proofs of the Game of Life in the classical case, this approach cannot be used in the quasi-periodic case.

Another noteworthy difference between the Penrose case and the classical case is that long string-like (closed or not) connected alive cells can be stable on a Penrose tiling. Such patterns, called rings and snakes have been studied in [START_REF] Owens | The Game of Life rules on Penrose tilings: still life and oscillators[END_REF].

A Universal CA on Kite and Dart Penrose Tilings

In this section we present the construction of a semi-totalistic CA working on Penrose's kite and dart tilings that is logically universal in the sense that it can simulate the behavior of any boolean circuit.

Universal Reversible Logical Elements

In order to construct a universal CA, we will use very simple reversible logical elements with 1-bit memory.

The usual difficulty when embedding circuits in a larger structure (such as a cellular automaton) is to synchronize the different signals. In the case of an aperiodic geometry, the problem is even harder as construction patterns cannot be precisely shifted in a given direction. To solve this problem we use asynchronous elements that can simulate any circuit while only having one signal at a time.

Figure 4 shows every 2-symbol reversible logical elements with 1-bit memory. There are only eight types of such elements. The left part of each illustration represents the element in state 0, the right part being state 1. Each element only accepts one signal from one of two possible inputs (left side) at a time. Lines (full and dotted) represent the output through which the signal will exit the element.

When a signal traverses the element through a full line, the state of the element is changed. If the signal traverses through a dotted line its state is unchanged. It has been shown that any reversible Turing machine can be constructed by 4-symbol reversible logical elements (rotary elements) [START_REF] Morita | Constructing a reversible turing machine by a rotary element, a reversible logic element with memory[END_REF]. Its computing process is executed by a signal, thus there is no need to synchronize signals. The rotary element can be realized by any combination of two elements amongst 2-3, 2-4, and 2-17 [START_REF] Lee | An asynchronous cellular automaton implementing 2-state 2-input 2-output reversed-twin reversible elements[END_REF][START_REF] Mukai | Universality of 2-symbol reversible logic elements with memory[END_REF]. So the combination of two elements are universal.

In our construction we will use elements 2-3 and 2-17.

General Overview of the Automaton

The automaton has 6 states :

• State 0 is a quiescent state, meaning that a cell in state 0 surrounded by other cells in the same state will not change. This state is therefore used as a "background" for the whole construction and a "filler" in the local transition rule to account for the different sizes of neighborhoods (the number of other states in the neighborhood is significant but the exact number of 0 states is not).

• States 1, 2 and 3 are used to transmit the signal through wire-like structures. Connected cells in state 1 will act as a wire along which the signal moves. The signal itself is made of two states to orient it. State 3 is the head of the signal and state 2 is the refractory state that remains after a cell was in state 3 in order to avoid the signal going back through the wire in the opposite direction.

• Finally, states 4 and 5 are used internally in the logical elements to control the behavior and store the inner state of each element.

Any boolean circuit can be simulated by an asynchronous 1-signal circuit containing only copies of the elements 2-3 and 2-17, connected by wires [START_REF] Lee | An asynchronous cellular automaton implementing 2-state 2-input 2-output reversed-twin reversible elements[END_REF][START_REF] Mukai | Universality of 2-symbol reversible logic elements with memory[END_REF]. Because the circuit is two-dimensional, wires must also be able to cross.

It is therefore enough to show that our automaton can accurately simulate the behavior of the logical elements and that these elements can be connected by wires.

Simple Wires

Wires can be easily represented by a continuous line of neighboring cells in state 1 surrounded by cells in state 0. It is important that each cell of the wire is connected to exactly two other cells of the same wire. This constraint is not very restrictive though, and it is easy to draw a wire going from any point of the tiling to any other. Simple wires cannot cross, and we will need a specific construction to allow crossings.

A signal on the wire is represented by two consecutive cells in states 3 (front) and 2 (back).

The transition rules needed to describe the behaviors on the wires are quite simple :

• a cell in state 1 that has a neighbor in state 3 (head of the signal) changes to state 3 ;

• a cell that is in state 3 changes to state 2 (refractory state) ;

• a cell in state 2 returns to the simple wire state 1 ;

• finally, cells in state 1 remain in that state in the absence of a neighboring signal.

Figure 5 illustrates a wire on which there is a signal moving towards the right.

Logical Elements

The simulation of the elements 2-3 and 2-17 can be done by adding new states to the automaton. It would be very tedious to devise a construction that could behave as a specific logical gate in every possible neighborhood, but we only need to have a pattern that works in a specific geometric neighborhood because the tilings produced by the kite and dart tiles are all quasi-periodic. This means that if we can position the widget at a given position because the surrounding tiles correspond to what we need, there are such appropriate positions in every sufficiently large surface of the tiling.

For instance, Figures 6, 7, 8, 9, and 10 illustrate a widget that behaves as element 2-3. This widget must be located on a neighborhood of type a7 (according to the classification of Figure 3) in order to work properly as any other positioning would change the number of neighbors of one of the cells and significantly alter its behavior.

But because of the quasi-periodicity of the tiling, there are such locations in every area of the tiling. We can therefore put different copies of the widget in different areas of the tiling and connect them with wires as needed (the wires do not require specific arrangements of the tiles).

The quasi-periodicity can also be used for larger constructions. If we create part of a circuit in some specific location and want to copy it somewhere else, we know that there exists another appropriate location not too far from the original (the maximal distance is proportional to the radius of the widget we need to copy). Because of this, it is enough to verify that the widget works as intended in its appropriate environment to ensure that we can use it to build arbitrarily large circuits. There are four distinct combinations of an input {a, b} and an internal state {0, 1}. For example, Figure 6 shows the two patterns that will simulate the element 2-3 with internal states 0 and 1 respectively. Figure 8 illustrates the evolution of this pattern when a signal enters from its second input (b) and exits through its first output (x) while changing its internal state.

Similarly, Figures 11,12, and 13 illustrate the pattern used to simulate element 2-17. In this case, the element is symmetric for an input {a, b}, the behavior of the widget is also symmetric. We only show the two cases, (input, state) = (a, 0) and (a, 1).

Because we can control the environment in which the widget evolves, we can precisely set the local transitions up to behave as intended.

Finally, in order to be able to connect all the elements freely, it is necessary to add the possibility of crossing wires. This is achieved by connecting two 2-17 elements as illustrated by Figure 14. Their initial states should have opposite values. Each time a signal pass through, the two elements flip their internal states and the elements act as a crossing module.

Table 3.4 gives a full description of the local transition rule of the automaton.

Simulation of a Turing Machine

It has been shown in [START_REF] Morita | Constructing a reversible turing machine by a rotary element, a reversible logic element with memory[END_REF] that it is possible to create a circuit that simulates the behavior of a Turing machine cell by arranging eleven copies of a simple logical element with one-bit memory (called rotary element). In order to simulate a Turing machine it is then sufficient to connect an infinite line of such 3, * , 1, 1, 0, 0, 0 → 2 2, * , 1, 0, 1, 0, 0 → 1 5, 0, 3, 0, 1, 6, 0 → 0 1, * , 1, 0, 1, 0, 0 → 3 1, * , 1, 0, 1, 2, 1 → 3 1, * , 2, 0, 1, 4, 1 → 3 1, * , 1, 0, 1, 1, 0 → 3 1, * , 1, 0, 1, 2, 0 → 3 0, 0, 3, 0, 1, 6, 0 → 3 1, * , 3, 0, 1, 4, 0 → 3 2, 0, 3, 0, 1, 6, 0 → 5 1, * , 2, 0, 1, 1, 0 → 3 1, * , 2, 0, 1, 2, 1 → 3 1, * , 3, 0, 1, 1, 0 → 3 1, * , 2, 0, 1, 0, 0 → 3 1, * , 0, 0, 1, 2, 1 → 3 0, 0, 2, 0, 1, 6, 1 circuits. The resulting simulation only requires one active signal to move through the whole infinite circuit.

t =0 t =1 t =2 t =3 t =4 t =5
t =0 t =1 t =2 t =4 t =5 t =6 t =3
t =0 t =1 t =2 t =4 t =5 t =6 t =3
t =0 t =1 t =2 t =3 t =4 =5
t =0 t =1 t =2 t =3 t =4 t =5
t =0 t =1 t =2 t =4 t =5 t =6 t =3
→ 3 2, 0, 2, 0, 1, 6, 1 → 0 1, * , 1, 0, 1, 1, 0 → 3 1, * , 1, 0, 1, 3, 0 → 3 1, * , 2, 0, 1, 3, 1 → 3 1, * , 2, 0, 1, 3, 0 → 3 1, * , 3, 0, 1, 2, 1 → 4 1, * , 3, 0, 0, 2, 1 → 5 5, * , 2, 1, 0, 2, 1 → 1 4, * , 3, 1, 0, 2, 1 → 1 1, * , 3, 1, 0, 2, 2 → 2 1, * , 1, 1, 0, 0, 2 → 3 1, * , 1, 0, 1, 1, 2 → 5 5, * , 1, 1, 0, 1, 2 → 1 1, * , 1, 0, 1, 1, 2 → 5 5, 0, 3, 0, 0, 5, 2 → 3 3, 0, 4, 0, 0, 5, 1 → 2 2, 0, 3, 0, 1, 5, 1 → 0 1, * , 1, 0, 1, 1, 1 → 5 1, * , 2, 0, 0, 3, 2 → 5 0, 0, 3, 0, 0, 5, 2 → 5 1, * , 1, 0, 0, 1, 1 → 3 5, * , 1, 0, 0, 1, 3 → 1 5, * , 2, 0, 0, 3, 3 → 2 0, 0, 3, 0, 1, 5, 1 → 2 1, * , 3, 1, 0, 3, 1 → 3 1, * , 2, 2, 0, 4, 0 → 2 2, 0, 3, 1, 0, 5, 1 → 5 5, * , 1, 1, 0, 1, 2 → 1 5, 0,
The rotary element itself can be simulated by elements 2-3 and 2-17 but arranging an infinite line of copies of a given pattern cannot be done periodically on Penrose's tiling. However, since every tiling by Penrose tiles is quasi-periodic, if we can embed a circuit that simulates a Turing machine cell on a certain pattern of the tiling, there exists a constant N such that on every square portion of the plane of size N × N the pattern appears. This means that if we consider an infinite stripe of the plane divided in squares of size N × N, we can put a Turing machine cell in each square and connect them into an infinite line as illustrated by Figure 15.

Conclusion

Despite working on an aperiodic structure with heterogeneous neighborhoods, the 6-state cellular automaton that we have described can simulate any logical circuit and even simulate the evolution of a Turing machine, if the infinite circuit is correctly embedded on the tiling (it can be, but in an aperiodic manner). It can work on any valid tiling of the plane by the kite and dart tiles because all such tilings contain the same finite patterns so any finite configuration on one can be inserted in another.

The number of states of the automaton is likely not minimal for a universal CA. It seems likely that there exist ways to simulate the simple logical elements (or even a different universal combination) with fewer states but possibly larger widgets. It is however very difficult to optimize these constructions as many different environments have to be considered in the search.

Intrinsic universality (the ability to simulate any other cellular automaton) should also be investigated. In that case however, a single-signal asynchronous system cannot work but it might be possible by arranging infinitely many circuits in similar environments, each simulating the behavior of a cell, and connecting them with wires of fixed length to avoid synchronization problems.

Recently gliders are found in the case of Penrose Rhomb tiling [START_REF] Goucher | Gliders in Cellular Automata on Penrose Tilings[END_REF]. It is also meaningful to investigate the possibility of a glider based universal cellular automaton.

Figure 1 :

 1 Figure 1: Roger Penrose's Kite and Dart tiles.

Figure 2 :

 2 Figure 2: Combination rules of the Kite and Dart tiles.

Figure 3 :

 3 Figure 3: The generalized Moore neighborhoods on a kite and dart Penrose tiling[START_REF] Owens | Investigation of the Game of Life cellular automata rules on Penrose tilings: lifetime, ash and oscillator statistics[END_REF]

Figure 4 :

 4 Figure 4: 2-symbol reversible logical elements with 1-bit memory [12].

Figure 5 :

 5 Figure 5: A signal on a wire and their state-color mapping table.

Figure 6 :

 6 Figure 6: Logical element 2-3 in states 0 (left) and 1 (right). White cells in state 0, light gray cells in state 1.

Figure 7 :

 7 Figure 7: Element 2-3: a transition from state 0, input a to state 0, output x.

Figure 8 :

 8 Figure 8: Element 2-3: a transition from state 0, input b state 1, output x.

Figure 9 :

 9 Figure 9: Element 2-3: a transition from state 1, input a to state 1, output y.

Figure 10 :Figure 11 :

 1011 Figure 10: Element 2-3: a transition from state 1, input b to state 0, output y.

Figure 12 :

 12 Figure 12: Element 2-17: a transition from state 0, input a to state 1, output x.

Figure 13 :Figure 14 :

 1314 Figure 13: Element 2-17: a transition from state 1, input a to state 0, output y.

Figure 15 :

 15 Figure 15: How to simulate the behavior of a Turing machine with copies of a circuit that simulates the behavior of one tape cell.

Table 1 :

 1 Local transition rule of the 6-state universal cellular automaton. The symbol '*' is a wildcard that matches any value. In case of multiple matches, the first matching rule is applied (left to right, top to bottom). The rules with no wildcard are only applicable for the a7 neighborhood.

		2, 1, 0, 5, 2 → 0	2, * , * , * , * , * , * → 1	3, * , * , * , * , * , * → 2
	1, * , * , * , * , * , * → 1	4, * , * , * , * , * , * → 4	5, * , * , * , * , * , * → 5.

Acknowledgments.

Katsunobu Imai gratefully acknowledges the support of the Japan Society for the Promotion of Science and the Grant-in-Aid for Scientific Research (C) 22500015.


Anaël Grandjean

Victor Poupet

Comparing 1D and 2D Real Time on Cellular Automata

Keywords: 1998 ACM Subject Classification F.1.1 Models of Computation Cellular automata, real time, language recognition

We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.

Introduction

Cellular automata (CA) were first introduced in the 1940s (published posthumously in 1966) by J. von Neumann and S. Ulam as a mathematical model to study self-replication [START_REF] John Von Neumann | Theory of Self-Reproducing Automata[END_REF]. Although initially studied as a a dynamical system, A.R. Smith III proved that it was possible to embed Turing machines in their behavior [START_REF] Alvy | Simple computation-universal cellular spaces[END_REF] and were as such a convenient model for massively parallel computation.

Cellular automata are also well suited to work on various dimensions. The original CA by von Neumann is 2-dimensional, but the natural simulation of Turing machines is on one dimension. CA represent therefore a natural way to study how the dimension of the space affects the computing power of the machines [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF][START_REF] Terrier | Low complexity classes of multidimensional cellular automata[END_REF].

This article presents some results comparing the computational power of 1-dimensional and 2-dimensional CA on parallel input. The main open question in that respect is to determine whether or not all languages that can be recognized in real time on 2-dimensional CA can also be recognized in real time in 1 dimension [START_REF] Delorme | Open problems on cellular automata[END_REF].

The organization of the article is as follows. Section 2 recalls the basic definitions and concepts about cellular automata that are used throughout the article. Section 3 presents a construction on 1-dimensional CA that shows how it is possible to consider that a real time CA knows approximately where the middle (or any other fixed rational proportion) of the input word is from the start. This construction is used to prove the main theorem of Section 5. In Section 4 we present a classic technique on cellular automata that compresses the space-time diagram of a 1-dimensional CA. The main novelty here is that we perform the compression not on the middle of the input word but on an approximate position "near the center". Section 5 presents and proves the main result of the article, which states in essence that 2-dimensional CA can simulate in real time a linear number of simulations of a 1-dimensional real time CA. Finally Section 6 discusses some consequences of the main theorems.

Q is denoted Conf(Q). For a given configuration C ∈ Conf(Q) and a cell c ∈ Z d , define the neighborhood of c in C N C (c) = N → Q n → C(c + n)
From the local transition function δ, we define the global transition function ∆ A of the automaton. The image of a configuration C by ∆ A is obtained by replacing the state of each cell c by the image by δ of the neighborhood of c in C :

∆ A :    Conf(Q) → Conf(Q) C → Z d → Q c → δ(N C (c))
In this article, we will only consider 1-dimensional CA working on the standard neighborhood N std = {-1, 0, 1} and 2-dimensional cellular automata working on the Moore neighborhood N M = {(x, y) | -1 ≤ x, y ≤ 1} (see Figure 1).

Language Recognition

Definition 2 (Language Recognizer). Given a finite alphabet Σ and a language

L ⊆ Σ * , a d-dimensional CA A with states Q is said to recognize L in time f : N → N with accepting states Q a ⊆ Q and quiescent state q 0 ∈ Q if, Σ ⊆ Q and for any word w = u 0 u 1 . . . u n-1 ∈ Σ * , starting from the configuration Z d → Q (x, y 1 , y 2 , . . . , y d-1 ) → u x if x ∈ 0, n -1 and ∀i, y i = 0 q 0 otherwise the state of the origin at time f (n) is in Q a if and only if w ∈ L.
Definition 3 (Real and Linear Time). The real time function is the function n → n -1. This time function corresponds to the minimal time necessary for information held on the last letter of the input word to reach the origin and hence affect the recognition of the word. The class of languages recognized in real time on 1 dimensional (resp. 2-dimensional) CA will be denoted CA(n) (resp. CA 2 (n)).

We will say that a language is recognized in linear time if it can be recognized in time n → 2n. The class of languages recognized in linear time on 1-dimensional (resp. 2 dimensional) CA will be denoted CA(2n) (resp. CA 2 (2n)).

Because there are linear acceleration theorems on 1-dimensional and 2-dimensional CA [START_REF] Mazoyer | A linear speed-up theorem for cellular automata[END_REF] (on the simple neighborhoods that we consider), any language recognized in time n → kn for k > 0 is also recognized in time n → 2n, which explains the denomination of linear time. As for real time, it is a long open question to determine whether CA(n) = CA(2n).

In this article, we investigate whether adding a dimension to the automaton increases linear and real time recognition power, namely if CA(n) = CA 2 (n) and CA(2n) = CA 2 (2n). These questions are long open problems (see problem 26 in [START_REF] Delorme | Open problems on cellular automata[END_REF]).

Tools

Space-Time Diagram

A space-time diagram is a 2-dimensional representation of the evolution of a 1-dimensional CA from a specific configuration. Each configuration in the evolution is represented by a line of the diagram, with time going from bottom to top. We do not usually consider space-time diagrams of 2-dimensional CA as these would be in 3 dimensions.

A specific point in space and time will be referred to as a site of the space-time diagram.

Layers

Given a CA A = (d, Q, N , δ), adding a layer to A that performs a certain task consists in designing a specific CA working on a set of states Q that performs the task and extending the set of states of A to the product Q × Q . In doing so, the new product automaton can mimic the behavior of A on its first coordinate and perform the new task on the second coordinate. From there, it is possible to modify the behavior of the automaton by having the two layers interact with each other. As long as each layer requires only a finite number of states and there are only a finite number of layers, the total number of states of the resulting automaton remains finite.

Markers

In this section we investigate whether "marking" specific positions on the input word can help real time recognition of a language. The results in this section are a generalization of a technique used by O. Ibarra and T. Jiang in their proof that if CA(n) is closed under reversal then CA(n) = CA(2n) [START_REF] Ibarra | Relating the power of cellular arrays to their closure properties[END_REF]. Given a finite alphabet Σ, we mark some letters of words of Σ * by considering the extended alphabet Σ×{0, 1}. We say that the word (u i , δ i ) i∈ 0,n-1 ∈ (Σ×{0, 1}) * corresponds to the word (u i ) i∈ 0,n-1 where all the positions i such that δ i = 1 have been marked (δ i = 0 means that the letter has not been marked).

Exact and Fuzzy Marking

Definition 4 (Proportional Marking). Given α ∈ [0, 1[ and a language L over an alphabet Σ, we define L [α] ∈ (Σ × {0, 1}) * as the language of words of L for which only the letter at position αn has been marked (n is the length of the word).

Formally, the word (u i , δ i ) i∈ 0,n-1 ∈ (Σ × {0, 1}) * is in L [α] if and only if u 0 u 1 . . . u n-1 ∈ L, δ αn = 1 and for all other i, δ i = 0.

When working on real time CA algorithms it would sometimes be convenient to know where the middle of the word is, or some other specific ratio. Whether marking the letter of the input word corresponding to a fixed proportion of the word length can help recognize in real time languages that were not in CA(n) is still an open question to our knowledge 1 . Although an answer to this question would be very interesting, we can actually make many constructions with a weaker version that we can prove : instead of requiring a mark on the exact cell at position αn , it is enough to have a mark on one of the cells between positions αn and βn for α < β. Definition 5 (Fuzzy Marking). Given α, β ∈ [0, 1[ with α ≤ β and a language L over an alphabet Σ, we define L [α,β] ∈ (Σ × {0, 1}) * as the language of words of L for which exactly one letter between position αn and βn has been marked (n is the length of the word).

Formally, the word

(u i , δ i ) i∈ 0,n-1 ∈ (Σ×{0, 1}) * is in L [α,β] if and only if u 0 u 1 . . . u n-1 ∈ L, there is exactly one i 0 such that δ i0 = 1 and i 0 ∈ αn , βn .
The rest of this section will be devoted to the proof of the following theorem: Theorem 6. For any language L and any α, β

∈ [0, 1] with α < β, L [α,β] ∈ CA(n) ⇒ L ∈ CA(n)
First, notice that it is sufficient to prove the theorem for α and β rationals with 0 < α < β < 1. Indeed, for any α, β ∈ [0, 1] and α , β ∈ Q such that α ≤ α < β ≤ β if L [α,β] ∈ CA(n) then we can recognize L [α ,β ] in real time by simulating the automaton A that recognizes L [α,β] in real time while simultaneously verifying that the marker is placed between α n and β n , which can be done in real time because α and β are both rationals. If the marker is in the right range then the input word is in L [α ,β ] if and only if A accepts it. If the marker is not in the right range, then the word is not accepted. From now on, we can therefore assume that α, β ∈ Q and 0 < α < β < 1.

To prove the theorem, we assume that we have a CA A that recognizes the language L [α,β] in real time, for some α, β ∈ [0, 1], with α < β. We will show how to make a CA A that recognizes L in real time.

The construction will be done in two steps. First we describe a CA that starts with a fixed set of positions marked (independently of the input length) and we show that with these markers we can recognize L in real time. Then we transform this CA into one that does not need the positions to be marked ahead of time.

Universal Markers

Let n 0 be the smallest integer such that 1 + 1 2 n 0 < β α and consider the set M of integers whose binary representation is such that all the digits 1 are on the (n 0 + 1) most significant 1 4 8 16 24 5 6 7 10 12 14 20 28 32 40 48 2 3 0

1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 ×2 3 ×2 2 ×2 1 ×2 0 Figure 2 The set M for n0 = 2.
bits (see Figure 2):

M = {x×2 k | x ∈ 0, 2 n0+1 -1 , k ∈ N} = 0, 2 n0 -1 ∪{x×2 k | x ∈ 2 n0 , 2 n0+1 -1 , k ∈ N}
The set M contains an initial segment 0, 2 n0 and copies of 2 n0 , 2 n0+1 multiplied by the powers of 2 (indicated as bracketed "blocks" in Figure 2).

Let us now consider the ratio between consecutive elements of M . Denote by (m i ) i∈N the elements of M in increasing order. For all m i ≥ 2 n0 , we have

1 + 1 2 n0+1 -1 ≤ m i+1 m i ≤ 1 + 1 2 n0 (1)
The lower bound corresponds to the ratio between the last element of a block and the first of the next block (in the example with n 0 = 2, this ratio is 8 7 ) and the upper bound corresponds to the ratio between the two first elements of a block (in the example it is 5 4 ). From the definition of n 0 , we have

∀m i ≥ 2 n0 , mi+1 mi < β α and mi+1 β < mi α so intervals [ mi β , mi α ] and [ mi+1 β , mi+1 α ] overlap, and hence [2 n0 , +∞[ ⊆ m∈M m β , m α . From this, we get ∀x ≥ 2 n0 , ∃m ∈ M, αx ≤ m ≤ βx .
Since M contains all the elements in the the missing initial segment 0, 2 n0 , we have proved the following lemma:

Lemma 7. ∀n ∈ N, ∃m ∈ M, αn ≤ m ≤ βn
We now know that for any input word w of length n, at least one of the elements of M lies between αn and βn and can therefore be used by A as a marker to know whether w is in L.

Moreover, from Equation (1), we have ∀i, k ∈ N,

m i 1 + 1 2 n0+1 -1 k ≤ m i+k (2)
Define k 0 as the smallest integer such that

1 α ≤ 1 + 1 2 n0+1 -1 k0 (3)
Equations ( 2) and (3) state that for any i, if m i+k0+1 ≤ n then m i+1 ≤ αn and thus m i < αn , which means that if a word is long enough to have a letter on m i+k0+1 , then m i is out of the range of valid markers. As a consequence, it is never necessary to consider more than (k 0 + 1) elements of M at any given time.

We can now describe the first part of the construction. We assume that the automaton is given as input a word w of Σ * on which all letters at indexes in M are marked. On such an input the automaton simulates the behavior of A on w (as if no letter was marked), but each marked cell also starts a separate simulation of A that considers that the letter is the only marked letter of the input. However, as previously observed, only the (k 0 + 1) simulations corresponding to the largest elements of M are significant, all others correspond to markers at positions before the required range. This means that each cell only needs to simulate at most (k 0 + 1) computations of A and whenever a new computation should be taken into account, the one corresponding to the lowest element of m is discarded.

This behavior is illustrated by Figure 3. This figure represents a space-time diagram of the automaton. Each cone corresponds to a simulation of A for which the marked cell is the origin of the cone. The figure corresponds to a case where k 0 = 2, meaning that at most 3 simulations are performed in parallel by each cell. The thick dashed line illustrates the area of the space-time diagram on which the simulation corresponding to the marker on m 4 is performed. Since this specific simulation starts on the cell m 4 , all space-time sites outside of the cone starting from that cell are not performing this specific simulation (they are however simulating the behavior of A without any marker, wich coincides with the behavior with a marker on m 4 on said sites out of the cone). As time passes, more and more cells are included in this cone and start performing this specific simulation. The two sites indicated by ! correspond to events where a cell enters a fourth cone. Instead of starting a fourth simulation, it discards the simulation corresponding to the lowest m i : on the left, the simulation for a marker at m 1 is discarded, on the right it's the simulation corresponding to the marker at m 4 that is discontinued.

In each simulation of A, the automaton checks that the marker is located between αn and βn by sending two signals from the marker towards the origin, one at speed α and the other at speed β (it is possible if α and β are rationals). If the marker is in the correct range, the signal moving at speed β will arrive before real time while the one moving at speed α will arrive after real time.

From Lemma 7, we know that there is a marker m in the correct range and since A properly recognizes L [α,β] , the simulation of A for the marker m will let the automaton know whether w is in L or not.

Construction of M

We now have to remove the requirement that the elements of M be marked on the input. To do this, we use a space-time compression technique: instead of starting the computation counter computation immediately, the automaton moves the states from the input word towards the orgin to group them three by three, and only then simulates the behavior of the original (uncompressed) CA. By performing such a compression, the initial configuration is mapped to the space-time line of slope 2, and the computation takes place in the cone between this line and the vertical axis (as illustrated by the green cone in Figure 4 in which each dark green cell on the right border holds 3 states from the initial configuration). Although the space-time diagram is strongly modified by the compression, the computation of the states on the origin cell does not suffer any slow down.

To mark the elements of M for the compressed computation, the CA builds a binary counter on the main diagonal of the space-time diagram to obtain the index of each transverse diagonal (see Figures 4 and5).

Since it is easy to recognize binary representations of elements in M (all bits but the (n 0 + 1) most significant must be 0), a signal can be sent along the diagonals whose index is in M so that the letters of the input word at positions in M can be marked before the compressed computation effectively starts.

From an input word w in Σ * , the automaton can therefore simulate the previously described automaton as if the positions in M were marked from the start, and determine in real time whether w is in L. This concludes the proof of Theorem 6.

Central Compression

In this section we describe a way to simulate the behavior of a 1-dimensional CA A on an input w ∈ Σ * working in real time with another 1-dimensional CA A on input w with a marked position, by compressing the space-time diagram of A.

General Description

Assume that a special position has been marked on the input word of A . We want to group the states of the original simulated CA by groups of 3 around the mark as illustrated by Figure 6. To do so, the letters of the input word (represented as large circles in the figure) are shifted towards the marked position (indicated by a thick dashed line). Because the letters do not know in advance whether the mark is to their right or to their left, the AC uses two separate layers, one that shifts the letters to the right and the other to the left. Letters that move away from the mark will never be grouped and will not affect the simulation.

When letters reach the marked position, they stack on the corresponding cell. When a cell has 3 letters, it is considered full and its neighbors start gathering letters in turn. In Figure 6, grouped states are represented by small circles.

Once a cell is fully grouped, it watches its neighbors until it has enough information to simulate 3 steps of the original automaton at once on all its grouped states. This happens when its neighbors are fully grouped and their simulated time is at least equal to its own. During the compressed simulation, the difference between the simulated times of a cell and its neighbor is at most 3 (it can be -3, 0 or 3 since the simulation advances by 3 steps at a time). If a cell advances faster than its neighbor it has to memorize its previous state so that the neighbor can use it when doing its own transition. In Figure 6, the number in each cell represents the simulated time step: a cell numbered 3 for instance has to wait until both its neighbors are labelled 3 or more before it can compute step 6 for all 3 of its grouped states. Cells represented with a grey square are cells that don't contain any significant information (they correspond to sites that are outside of the real time cone in the original space-time diagram) so their neighbors do not need to wait for their information.

If the mark around which the cells are grouped is in the first half of the input word (which is the case in Figure 6 as there are 9 letters left of the mark and 15 right) the simulation can take place properly as the left part can compute its states faster and have the information ready for the right part. The key point is that from the time when the rightmost cell is fully grouped (this time is indicated by a thick horizontal line in Figure 6) all the sites on the diagonal must be able to advance their computation by 3 steps. This guarantees that the leftmost cell has eventually computed as many steps of the original diagram as if it had started at the indicated time and advanced by 3 steps each time, which corresponds to the whole computation of the original diagram.

In Figure 6, the leftmost cell of the compressed area seems to be 2 steps behind real time at the end of the simulation (the initial configuration has 24 letters so the real time is 23). However, because the cell holds the states of the 3 leftmost cells of the original configuration at time 21, it has all the relevant information to determine the state of the origin at time 23.

There are of course many rounding problems when the number of letters left or right or the mark is not a multiple of 3. However these roundings cause at most a constant delay, which can be corrected by using a constant speed-up theorem [START_REF] Mazoyer | A linear speed-up theorem for cellular automata[END_REF].

Properties

By compressing the space-time diagram of the automaton around the marked position, we are able to perform the same computation with some significant differences.

First, the letters of the input word are not taken into account from the start of the computation, but rather in a sequential order. The time at which a given letter of the input word is effectively considered to determine the result of a transition in the simulation is proportional to its distance to the initial mark (see Figure 7 in which the sites where the letters of the input word are first taken into account are along the thick arrows).

Second, the result of the computation is obtained significantly before real time, on a cell that it not the origin. The site where the result is obtained is represented by ! in Figure 7.

Let us denote by α the proportion of the word at which the mark is set. When using the compression in a later section, we will need the free space left of the compressed area (which is of width 2α 3 ) to be larger than each of the sides of the compressed area. As said before, we need α ≤ 1 2 for the simulation to work without delay, which means that the left side of the compressed area is smaller than the right side. Since the right side is of width 1-α 3 , this means that we want 1-α 3 ≤ 2α 3 , which amounts to

1 3 ≤ α ≤ 1 2 .

The Power of Space

In this section we compare the computational power of 2-dimensional CA working on the Moore neighborhood to that of 1-dimensional CA working on the standard neighborhood.

Definition 8. Given a marked language L ⊆ (Σ × {0, 1}) * , we define L ⊆ Σ * as the language obtained by removing the marks of words in L ( L can be seen as the result of the first projection map on L). Proof. Let L ⊆ (Σ × {0, 1}) * be a language in CA(2n) of words having at most one marked position and A be a 1-dimensional CA that recognizes L in time n → 2n. Let us describe a 2-dimensional CA A that recognizes L in linear time.

The input of A is an unmarked word w ∈ Σ * of length n. The idea is to use the second dimension of A to run n simulations of A, one for each possible position of the mark as shown on Figure 8.

At time t = 0, the input is on the first line and a simulation of A starts on that line with a mark on the leftmost cell of the word. At each subsequent time, the original input is copied on the next line (moving up), and a new simulation of A is started on that line with the mark on the next position (moving right). At time t = n, the first line has simulated n steps of A with a mark on the first cell, while the n-th line starts a new simulation with the mark on the last cell.

When a simulation finishes, the result is sent back towards the origin (on the first line). At time t = 3n the simulation on line n is finished, and at time t = 4n the results of all simulations are available on the origin (to be complete, the automaton must also run an extra simulation on the first line that simulates the behavior of A on input w without any mark). The language L is therefore recognized in time n → 4n, and by using a linear acceleration we get L ∈ CA 2 (2n).

Theorem 10. For any language L ⊆ (Σ × {0, 1}) * of words having at most one marked position, L ∈ CA(n) ⇒ L ∈ CA 2 (n).

Proof. The basic idea is again to run parallel simulations of a 1-dimensional CA on the lines of the 2-dimensional CA, but because the automaton must work in real time it is not possible to waste a linear time starting the simulations, nor a linear time bringing back the results of the farthest simulation to the origin, which is why we use the compressed simulation presented in Section 4.

Consider a language L ∈ (Σ × {0, 1}) * such that all words of L have at most one marked position and a 1-dimensional CA A that recognizes L in real time. We want to describe a 2-dimensional CA A 2 that takes an unmarked word w ∈ Σ * of length n and decides in real time if by adding at most one mark to w we can obtain a word in L.

For now, let us assume that the input word w has a mark on a position between n 3 and n 2 so that we can run the compressed simulation easily. This mark will be referred to as the compression mark, it is different from the marks of L that we want to simulate on each line.

Instead of simulating A, A 2 will simulate an automaton A C that simulates A with a central compression on the compression mark as described in Section 4.

The behavior of A 2 is as follows: at time t = 0, the first line of A 2 starts a simulation of A C as if no letter of the input was marked; at each time, this "unmarked" simulation is copied to the next line (moving up), each line continues the simulation from the step at which it is when copied (so that more and more lines are performing the same simulation of A C , without suffering any delay); meanwhile, each line has one or two special positions. The special position of the first line is the one where the compression mark is, and the special positions of line (i + 1) are the one left of the leftmost special position of i, and the one right of the rightmost position of i (see Figure 9). Special positions on each line are marked when the line copies the simulation from the previous line. during the simulation of A C by a line, when one of the cells at a special position finishes grouping 3 letters of the input word, 3 new simulations of A C are started on this line, each considering that there was a mark on one of the letters of the input word that was grouped on the special position. Because each line has at most two special positions, at most 7 simulations of A C are run in parallel on each line (3 for each special position and the unmarked one).

This construction works because of the properties of the central compression discussed in Section 4.

First, the simulations of A C on each line can be performed properly without any delay because the time at which an input letter that eventually is grouped on a special position of the line becomes significant is after the activation of the line and the marking of its special positions. Therefore, all simulations of A C on all lines are synchronized, and the farther lines do not suffer any delay.

Second, the number of lines really used (on which significant simulations that correspond to a potential mark on an input letter) is equal to the length of the largest side of the compressed area (which is 1-α 3 , see Figure 7). This length is less than the time remaining when the simulations of A C obtain their result ( 2α3 ), so it means that there is enough time to send back the result of the parallel simulations to the origin in real time.

The last detail is now to remove the requirement for the compression mark to be given as input. From Theorem 6, we know that if the computation can be performed in real time with a mark anywhere between positions n 3 and n 2 then it can be done in real time without previous marking. Technically, Theorem 6 only applies to 1-dimensional CA, but in this case the 2-dimensional CA performs 1-dimensional computations on each line almost independently so by having each line perform the construction from the proof of Theorem 6 we obtain the result for this specific 2-dimensional CA.

Consequences

Let us now discuss some consequences of Theorem 10.

Corollary 11. The concatenation L 1 L 2 of two 1-dimensional real time languages L 1 and L 2 is recognizable in real time by a 2-dimensional CA working on the Moore neighborhood.

Proof. Given a word w = uv with a mark between u and v, it is easy to check in real time if u ∈ L 1 and v ∈ L 2 , so from Theorem 10 the unmarked language is in CA 2 (n).

Figure 1

 1 Figure 1The standard 1-dimensional neighborhood (left) and the Moore 2-dimensional neighborhood (right).

Definition 1 (

 1 Cellular Automaton). A cellular automaton (CA) is a quadrupleA = (d, Q, N , δ) where: d ∈ N is the dimension of A; Q is a finite set whose elements are called states; N ⊂ Z d is a finite set called neighborhood of A such that 0 ∈ N ; δ : Q N → Q is the local transition function of A.A configuration of the automaton is a mapping C : Z d → Q. The elements of Z d are called cells and for a given cell c ∈ Z d , we say that C(c) is the state of c in the configuration C. The set of all configurations over

Figure 3

 3 Figure 3Space-time diagram of the simulation. Each cone represents the area on which a simulation corresponding to an element of M is done. The cones extend to the left until the origin, but are interrupted to the right when there are too many simulations running at once.

Figure 4 Figure 5

 45 Figure 4 The diagonal counter is added on the compressed space-time diagram. Because the diagonal indexes are of logarithmic length, the counter and the main computation overlap only on a finite number of cells. Diagonals of indexes in M (here with n0 = 2) are represented with a darker square.

Figure 6 Figure 7

 67 Figure 6 Simulation of a CA by compressing its space-time diagram by a factor 3 around a given mark (indicated by a thick dashed line). Each cell in the simulating area holds 3 states that correspond to states in the original spacetime diagram. Numbers on the cells indicate which time step of the original automaton they are currently simulating.

Figure 8 Figure 9

 89 Figure 8Running n simulations of a 1dimensional CA with a 2-dimensional CA.

Comparing 1D and 2D Real Time on Cellular Automata

Note that if CA(n) = CA(2n) then proportional marking with a rational ratio does not help real time recognition since the cell at position αn can be marked in n time steps for any rational α.

Comparing 1D and 2D Real Time on Cellular Automata

Corollary 12. If CA(n) = CA 2 (n), CA(n) is closed under concatenation.

Without the assumption that CA(n) = CA 2 (n), it is still unknown whether CA(n) is closed under concatenation. Actually, it is also unknown whether CA(2n) is closed under concatenation and even if the concatenation of two languages in CA(n) is in CA(2n).

Corollary 13. For any language L and any

Proof. Given a word with one marked position, it is easy to check simultaneously in real time if the mark is at position αn and if the marked word is in L [α] .

Under the assumption that CA(n) = CA 2 (n), Theorem 10 can also be strengthened:

Proof. By induction on k. The case k = 1 is a direct consequence of Theorem 10 and the assumption that CA(n) = CA 2 (n).

If the corollary is true for up to k marks, and L is a language of words with up to (k + 1) marks, let us consider the language L ⊆ (Σ × {0, 1} 2 ) * obtained from L by changing the first marked letter (u i , 1) to (u i , 0, 1), all other marked letters (u i , 1) into (u i , 1, 0) and all unmarked letters (u i , 0) into (u i , 0, 0) (effectively distinguishing the first mark from the others).

If L ∈ CA(n) then L ∈ CA(n) since it's possible to simulate the recognition of L by considering that all marks are the same, while independently checking in real time that the distinguished mark is the first marked position. From Theorem 10 the language of words in L in which the first mark has been removed is therefore in CA 2 (n) and hence also in CA(n). The words of this language have at most k marks so from the induction hypothesis, L ∈ CA(n).


Anaël Grandjean
email: anael.grandjean@lirmm.fr

Victor Poupet
email: victor.poupet@lirmm.fr

A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods

Keywords: 1998 ACM Subject Classification F.1.1 Models of Computation Keywords and phrases 2D Cellular automata, linear acceleration, language recognition

Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all twodimensional languages recognized by cellular automata working on complete neighborhoods.

Introduction

Cellular automata (CA) were initially introduced by S. Ulam and J. von Neumann [START_REF] John Von Neumann | Theory of Self-Reproducing Automata[END_REF] in the 1960s to study self-reproduction in discrete dynamical systems. They are massively parallel systems consisting of an infinite array of cells. Cells evolve synchronously depending on the states of their neighbors according to a uniform deterministic rule. Although initially considered in two dimensions, the definition can be adapted to any dimensional cellular space and even more general uniform graphs [START_REF] Róka | Simulations between cellular automata on Cayley graphs[END_REF].

Soon after their introduction, they were shown to be computationally universal [START_REF] Alvy | Simple computation-universal cellular spaces[END_REF][START_REF] Albert | A simple universal cellular automaton and its one-way and totalistic version[END_REF]. As a computation model, they have been extensively studied as one-dimensional language recognizers [START_REF] Alvy | Real-time language recognition by one-dimensional cellular automata[END_REF][START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF] but are also very well suited to the study of two-dimensional "picture languages" [START_REF] Alvy | Two-dimensional formal languages and pattern recognition by cellular automata[END_REF]12,[START_REF] Terrier | Two-dimensional cellular automata and their neighborhoods[END_REF].

The neighborhood of a cellular automaton defines the underlying communications graph of the cells. Although most of the existing work on two-dimensional cellular automata focuses on the von Neumann (4 closest neighbors) and Moore (8 closest neighbors) neighborhoods, understanding how the choice of the neighborhood affects the algorithmic capabilities of the model is a key to understanding parallel computation.

Linear acceleration theorems are well known for most of the commonly considered computation models. It was first proved for one-dimensional cellular automata working on the standard neighborhood and two-dimensional cellular automata on von Neumann's neighborhood by W. T. Beyer [START_REF] Beyer | Recognition of topological invariants by iterative arrays[END_REF], inspired by similar constructions for sequential input cellular automata [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF][START_REF] Fischer | Generation of primes by one-dimensional real-time iterative array[END_REF][START_REF] Hennie | Iterative Arrays of Logical Circuits[END_REF]. The one-dimensional case was later generalized by J. Mazoyer and N. Reimen for arbitrary neighborhoods [START_REF] Mazoyer | A linear speed-up theorem for cellular automata[END_REF]. As for two-dimensional neighborhoods, V. Terrier extended the construction to the Moore neighborhood [12] and then to the slightly more general class of neighborhoods whose convex hull has at most one vertex in the positive quarter plane [START_REF] Terrier | Two-dimensional cellular automata and their neighborhoods[END_REF].

115:2 Linear Acceleation on 2DCA

In this paper, we prove a general linear acceleration result for all complete neighborhoods on two-dimensional cellular automata.

The main theorem is stated in Section 3 and proved in Sections 4 to 7. Sections 4 and 6 describe the two main elements of the construction (compression of the input and accelerated simulation of the original automaton respectively). Section 5 presents a technique to perform a sequence of tasks on a cellular automaton without the need for synchronization at the start of each new task, used in the proof of the theorem to combine sections 4 and 6. Although this technique is elementary and has been used in previous publications (a special case was used by W. T. Beyer in 1969 [START_REF] Beyer | Recognition of topological invariants by iterative arrays[END_REF]), reviews of previous articles seem to indicate that it is not common knowledge. It is therefore presented here in a separate section and stated generally in the hopes that it can be easily reused in future publications.

The construction presented in this article is similar in several ways to previously published constructions, most notably those of V. Terrier in [START_REF] Terrier | Two-dimensional cellular automata and their neighborhoods[END_REF]. Significant improvements include compression of the input in almost optimal time (Section 4, specifically Subsection 4.2) and a more general simulation technique (Section 6).

∆(C) = Z d → Q c → δ(N C (c))
The action of the global transition rule makes A a dynamical system over the set

Q Z d .
Because of this dynamic, in the following we will identify the CA A with its global rule so that A(C) is the image of a configuration C by the action of the CA A, and more generally A t (C) is the configuration resulting from applying t times the global rule of the automaton from the initial configuration C.

Definition 3 (Quiescent and Permanent States). For a given CA A, we say that a state q is quiescent if a cell in state q remains in this state if all its neighbors are also in q. We say that q is permanent if a cell in state q remains in that state regardless of the state of its neighbors.

115:3

In this article we will only consider 2-dimensional cellular automata (2DCA). From now on the set of cells will always be Z 2 .

Neighborhoods

Throughout the article, we use the additive notation for vector sums, the power notation for neighborhood composition and the product notation for scalar product: Definition 4 (Vector Sum). Given two neighborhoods N 1 and N 2 and a cell c ∈ Z 2 , we define the vector sums

N 1 + N 2 = {x + y | x ∈ N 1 , y ∈ N 2 } and c + N 1 = {c + x | x ∈ N 1 }.
Definition 5 (Neighborhood Powers). Given a neighborhood N , we define

N 0 = {0} (1) ∀k ∈ N, N k+1 = N + N k (2)
Definition 6 (Scalar product). Given a neighborhood N and an integer k ∈ Z, we define the scalar product kN = {kx | x ∈ N }.

Definition 7 (Complete Neighborhood

). A neighborhood N is said to be complete if k∈N N k = Z 2
Definition 8 (Convex Hull and Convex Neighborhood). The convex hull of a neighborhood N is the smallest convex polygon CH(N ) ⊂ R 2 such that N ⊆ CH(N ). Moreover a neighborhood N is said to be convex if it contains all points of integer coordinates in its convex hull:

N = CH(N ) ∩ Z 2 .
Remark. If N is a convex neighborhood, N p is also convex for any p ∈ N.

Two-Dimensional Language Recognition

Definition 9 (Picture). For n, m ∈ N and Σ a finite alphabet, an (n, m)-picture (picture of width n and height m) over Σ is a mapping

p : 0, n -1 × 0, m -1 → Σ Σ n,
m denotes the set of all (n, m)-pictures over Σ and Σ * , * = n,m∈N Σ n,m the set of all pictures over Σ. A picture language over Σ is a set of pictures over Σ. Definition 10 (Picture Configuration). Given an (n, m)-picture p over Σ, we define the picture configuration associated to p with quiescent state q 0 / ∈ Σ as

C p,q0 :    Z 2 → Σ ∪ {q 0 } x, y → p(x, y) if (x, y) ∈ 0, n -1 × 0, m -1 q 0 otherwise
Definition 11 (Picture Recognizer). Given a picture language L over an alphabet Σ, we say that a 2DCA A = (2, Q, N , δ) such that Σ ⊆ Q recognizes L with quiescent state q 0 ∈ Q \ Σ, accepting state q a ∈ Q and rejecting state q r ∈ Q in time τ : N 2 → N if q a and q r are permanent states and for any picture p (of size n × m), starting from the picture configuration C p,q0 at time 0, the origin cell of the automaton at time τ (n, m) is in state q a if p ∈ L and state q r if p / ∈ L.

Definition 12 (Real Time). Given a complete neighborhood N , the real time function

RT N : N 2 → N associated to N is defined as RT N (n, m) = min{t | 0, n -1 × 0, m -1 ⊆ N t } I C A L P 2 0 1 6 115:4 Linear Acceleation on 2DCA 3
The Main Theorem

Most of the article will be dedicated to the proof of the following theorem Theorem 13 (Linear Acceleration). For any complete neighborhood N , any real number > 0, any finite alphabet Σ and any language L ⊆ Σ * , * , if L is recognized by a 2DCA working on N in time

(n, m) → RT N (n, m) + f (n, m) for some function f : N 2 → N then L can be recognized in time (n, m) → (1 + ) RT N (n, m) + f (n, m)
by a 2DCA with neighborhood N . Corollary 14. For any complete neighborhood N , any language recognized in time

(n, m) → k RT N (n, m) for some k > 1 can be recognized in time (n, m) → (1 + ) RT N (n, m) for any real number > 0.
To prove Theorem 13, we consider a 2DCA A working on a complete neighborhood N and describe the construction of a 2DCA A working on the same neighborhood that simulates the behavior of A in a way that enables it to recognize the same language as A in a linearly shorter time.

Preliminary Remarks

The following observations will greatly simplify the proof of Theorem 13.

Claim 15. It is sufficient to prove Theorem 13 up to an additive constant, meaning that we only need to prove that L can be recognized in time

(n, m) → (1 + ) RT N (n, m) + f (n, m) + O(1)
Proof. Consider that we have this weaker result. To get rid of the O(1) term simply choose < . For any C > 0, for (n, m) large enough we have

(1 + ) RT N (n, m) + f (n, m) > (1 + ) RT N (n, m) + f (n, m) + C
The automaton can handle all the finitely many inputs of small size in real time.

Claim 16. It is sufficient to prove Theorem 13 for all complete convex neighborhoods.

Proof. Consider a complete neighborhood N and let N be the convex neighborhood having same convex hull as N . The real time functions RT N and RT N differ by at most a constant. Moreover a CA on N can simulate the behavior of a CA on N with a loss of at most a constant number of steps and conversely (see [START_REF] Delacourt | Real time language recognition on 2d cellular automata: Dealing with non-convex neighborhoods[END_REF] for more details).

The property from the theorem therefore translates directly from one neighborhood to the other with at most a constant difference that can be ignored according to Claim 15.

From now on we will consider that N is a convex neighborhood.

Figure 1 Rules for the compression by a factor 3 of inputs of ratio n m = 2 with the neighborhood represented in the top left. The information that the cell takes as its new state is represented in grey. Information travels towards the bottom left. By looking down and left a cell determines if the information from the top right should simply pass through (first case) or if some of its neighbors are already full in which case it should start packing information. Left column shows simplified rules for which the cell has already packed information in one of the directions and therefore only the neighbors in the remaining direction are significant.

Compression of the Input

The first phase of the construction is to compress the input by a factor k > 1 . We want to move the states of the initial configuration towards the origin, packing them in groups of k × k as illustrated by Figure 2.

Although such compressions are relatively simple to perform on the von Neumann and Moore neighborhoods, on a more general neighborhood it is not possible to know in which direction the information should travel to move towards the origin at optimal speed. In general, the optimal travel direction depends on the proportion n m of the input. We first show that if the proportion of the input is fixed, compression can be done in optimal time on any complete neighborhood. Then, by performing a finite number of compressions in parallel, each assuming a different proportion, we show that any input is close enough to one of these assumed proportions to be compressed in "nearly optimal" time, which will be sufficient for the proof of Theorem 13.

Compression of an Input of Constrained Proportion

If the size of the input is known to be of proportion n m = α for some fixed rational α, we can perform a compression by a factor k with a neighborhood such as the one illustrated on the top left of Figure 1 with x y = α. On such a neighborhood, compressing the input is simply a matter of transferring the states from the top right to the bottom left, packing them in groups of (1 × k), (k × 1) or (k × k) when they cannot go any further in one or both directions (see Figures 1 and2). The compression is completed in time k-1 k RT . Note that in order to compress by a factor k, the cell must be able to see 1 k-1 times as far towards the left and bottom as it sees towards the right and top in order to properly determine when it should start packing states. Because the convex hull of a complete neighborhood N contains an open set around the origin (otherwise (N p ) p∈N would not expand in all directions), it contains its homothetic image of ratio -1 k0-1 for some k 0 (see Figure 3). On such a neighborhood compression by any factor k ≥ k 0 is possible. To compress inputs of proportion n m = α on some complete neighborhood N , we consider the largest rectangle [0, x] × [0, y] with x, y ∈ Q and x y = α included in the convex hull of N (see Figure 4). For all k ≥ k 0 , the rectangle [-

x k-1 , 0] × [-y k-1 , 0] is also in the convex hull of N .
These rectangles have rational but not necessarily integer dimensions. If we consider the neighborhood N p for some large p, all is scaled up by a factor p and the corresponding rectangles can be made of integer dimensions. The real time function on inputs of proportion α for N p is equal to the real time function of the neighborhood containing only the two rectangles (of integer coordinates). The compression algorithm described by Figures 1 and2 therefore finishes in time k-1 k RT N p +O(1) on N p . An automaton working on N can simulate one step of an automaton working on N p in p time steps, and since RT N p = 1 p RT N , the compression can be completed on N in time k-1 k RT N +O(1).

Compression of General Input

Let us now consider inputs of arbitrary proportions. As discussed in the previous subsection, for inputs of proportion α the optimal direction in which the information should travel for Figure 5 Choosing the set S of proportions that will be used by A for compressions. The thick line is the set of corners of maximal rectangles for all possible proportions. Along this line, we pick a finite set of points at intervals of at most η.

Figure 6

Compression of an input of arbitrary proportion. The optimal direction for the compression is represented by a dashed line. The closest chosen direction is represented by a solid line inside the neighborhood. It is at a distance at most η of the optimal vector. The travel path of the farthest cell of the input is represented as a solid black line, made of an initial segment along the almost-optimal direction and an extra segment to compensate for the deviation.

a compression is defined by the diagonal of the largest rectangle [0, x] × [0, y] with x y = α included in the convex hull of N . The first thing to note is that since N is complete, there exists η > 0 such that [0, η] × [0, η] ⊆ CH(N ) and hence all maximal rectangles in CH(N ) have at least one dimension greater than η. The corners (x, y) of such maximal rectangles all lie on a line. Let us pick a finite set S of rational points on this line from one extremity to the other with distance at most η between two consecutive points (see Figure 5).

For each proportion α = x y with (x, y) ∈ S, A performs a compression of the input as described in the previous subsection. All compressions take place at the same time in parallel. Note that even if the proportion of the input is not exactly that for which the compression is optimized, the input is still compressed properly although not as quickly.

Let us prove that one of the compressions that are run by the automaton compresses the input in time at most ( k-1 k + ) RT. A compression along the vector corresponding exactly to the proportion of the input would take a time k-1 k RT. A compression along one of the vectors in S that is closest to the optimal vector (at distance at most η) puts all states from the input within a distance at most η RT from their destination in time k-1 k RT +O [START_REF] Albert | A simple universal cellular automaton and its one-way and totalistic version[END_REF]. By choosing the closest vector properly amongst the two choices, the remaining distance can be travelled in time at most RT +O(1) as illustrated by Figure 6 (information travels at speed at least η in one of the dimensions).

For any possible input, at least one of the compressions completes in time at most ( k-1 k + ) RT +O(1).

Transition

After the input has been compressed, the automaton A should immediately start simulating the behavior of A, k steps at a time. However the cells of A receive the compressed input at different times. If we wanted all the cells to start the next phase at the same time, we would

I C A L P 2 0 1 6
115:8

Linear Acceleation on 2DCA

require some synchronization scheme such as a firing-squad synchronization algorithm but this would take a linear time. Instead, we show that synchronization is not required to start the accelerated simulation as each cell of the automaton proceeds with the next phase as soon as the relevant information is available. This technique is very general and can be used in numerous situations where a cellular automaton performs a computation by executing a series of separate tasks one after the other without having to spend time synchronizing all cells. In its general form, it can be stated in the following way:

Proposition 17 (Passive Synchronization). Given a CA A of any dimension working on a complete neighborhood N , there exists a CA A working on the same neighborhood N that can simulate the behavior of A on any input even if the configuration is given asynchronously in such a way that each cell of A computes states of the simulated automaton at least as fast as if the computation had started synchronously when the last cell receives its input.

Formally, if we denote by Q the states of A, A has states {⊥} ∪ (Q × Q ) where ⊥ is a permanent state (cannot be changed by the transition rule of the automaton) and Q is a set of extra working states containing a default state ν. The cells of A are initially in state ⊥ and considered inactive. Before each transition of the automaton, any number of inactive cells of A might be activated by some external action over which A has no control. Activating a cell c changes its state to (C(c), ν) where C is the input of the simulated automaton A.

If there exists a time t 0 at which all cells have been activated then for any cell c the projection on Q of the state of c in A at time (t 0 + t) is the state of c in the evolution of A from the configuration C at time t for some t ≥ t.

Proof. The idea is to make all cells of A compute one step of A whenever they have enough information to do so, while remembering their past states that other cells might need at a later time.

When a cell c is activated, it receives the initial state C(c) and we say that its simulated time is 0. From that point on, it looks at its neighbors and waits for all of them to be activated. When this happens, it sees all initial states in its neighborhood and can compute the next state in the evolution of A, increasing its simulated time to 1. As time passes it keeps watching its neighbors until all of them are also at a simulated time at least equal to its own, which means that it has all the information necessary to compute the next step and increase its simulated time further.

Let us prove that this process can be carried out with finitely many states. First, notice that since N is complete, there exists τ ∈ N such that -N ⊆ N τ . In order to compute its state for a simulated time (τ + t) a cell c needs to have had access to the state at the simulated time t of all cells in (c + N τ ) which includes the set (c -N ) of cells that have c in their neighborhood. This means that a cell cannot be more than τ steps ahead in its simulation than the cells that have it in their neighborhood, which implies that the difference of simulated times between two neighbor cells is at most τ . If each cell stores the value of its simulated time modulo (2τ + 1), it is possible for a cell to know the relative difference in simulated time with all cells in its neighborhood. Furthermore, it is sufficient that a cell remembers its last τ simulated states to be sure that when a cell c at simulated time t looks at its neighbors that are more advanced in the simulation it can see their simulated state at time t.

Finally, we prove by induction that at time (t 0 + t) all cells have a simulated time at least t. This is obviously true at time t 0 since all cells have been activated. By induction, at time (t 0 + t) for any cell at simulated time t all its neighbors are at least at simulated time t so it can compute a new step of the simulation, which proves that at time (t 0 + t + 1) all cells have a simulated time of at least (t + 1).

Note that this process is such that the cells who are behind in their simulation can compute new states without delay, whereas the ones ahead wait for their neighbors to catch up.

In the following section we describe how A can simulate k steps of A at a time starting from a compressed input. We assume that all cells complete the compression and start the simulation synchronously when the last cell receives its compressed information. Using Proposition 17, we can connect the two constructions (cells are activated for the simulation when they receive their compressed input) and ensure that the origin is always at least as advanced in its computation as if the simulation had started synchronously.

Simulation on a Compressed Input

Let us denote by ρ the function that maps a cell of A to the set of cells of A whose states it receives after the compression of a factor k :

∀c ∈ Z 2 , ρ(c) = {kc + (x, y) | x, y ∈ 0, k -1 }
and extend the notation to sets of cells by ρ(S) = c∈S ρ(c).

The states of A that are held in the neighborhood of a cell c in A are the ones corresponding to the cells of A in ρ(c + N ). To be able to compute k steps of the original automaton, the cell c in A needs to be able to see in its neighborhood the states corresponding to the cells (ρ(c) + N k ) of A. Although this is the case for simple rectangular neighborhoods, it is not true for some neighborhoods (see Figure 7).

What is true however is that ρ(c) + kN ⊆ ρ(c + N ) since for any v ∈ N if the state of a cell c in A is held by a cell c in A after compression of the input, the cell (c + v) in A holds the state of (c + kv) in A (see Figure 8). elements of N and therefore at least one of these elements appears at least k times, which proves that x ∈ N α + kN .

By Lemma 18, we can choose α such that N α + kN = N α + N k . We now modify the behavior of A so that during the first α steps of the computation, before starting the compression, all cells gather the initial states contained in their N α neighborhood. From here onwards, each cell performs all of the computation as described earlier on all the states it holds : a cell c holds at time (α + t) the states that would have been on all the cells in (c + N α ) at time t on the automaton A as described until now. At time (α + t) the cells in (c + N ) as a whole hold all the states that would have been on the cells in (c + N α+1 ) at time t, which is exactly what is needed to compute the states of all cells in (c + N α ) at time (t + 1). This extra step adds a constant time α to the computation of the automaton1 .

After the initial gathering and compression of the input, the cell c in A holds the initial states in A for the cells in (ρ(c) + N α ). Let us show by induction that this is enough to simulate the behavior of A with a linear speed-up of factor k. Assume that at time (t 0 + t), any cell c of A holds the states at time t for the cells of A in (ρ(c) + N α ).

This means that the cells in the neighborhood (c + N ) of c in A at time (t 0 + t) hold the states at time t in A of the cells in ρ(c + N ) + N α . By Lemma 18, we have

ρ(c + N ) + N α ⊇ ρ(c) + kN + N α ⊇ ρ(c) + N α+k
which shows that cell c in A at time (t 0 + t) sees enough information to compute the states in A for the cells in (ρ(c) + N α ) at time (t + k).

Total time

We have completed the description of the behavior of the automaton A . Let us now evaluate the total time taken to recognize the language L recognized by A in time RT N +f . The compression of the input takes a time ( k-1 k + ) RT N +O(1). The simulation of A from a fully compressed input takes a time 1 k (RT N +f ) + O(1) for some k ≥ 1 , and Proposition 17 shows that no time is lost by completing the compression asynchronously (the time of the compression is the time at which the last cell is correctly compressed).

The total time for the simulation of A is therefore

( k -1 k + ) RT N + 1 k (RT N +f ) + O(1) ≤ (1 + ) RT N + f + O(1)
By Claim 15, the O(1) term can be eliminated, which concludes the proof of Theorem 13.

Conclusion

The linear acceleration presented in this article is slightly weaker than the previously known results on a limited class of neighborhoods (which contains the von Neumann and Moore neighborhoods). On these neighborhoods, as well as all one-dimensional complete neighborhoods, any language that can be recognized in time (RT +f ) can be recognized in time (RT + f ) for any > 0.

Although the difference is only significant if f = o(RT), it would be interesting to know whether this stronger statement can be proved for general two-dimensional complete neighborhoods. This would either require an optimal-time compression of the input or a completely different construction skipping the compression altogether.

As we currently understand it, optimal-time compression seems unlikely on general neighborhoods. The problem is that states from the initial configuration should move towards the origin in the optimal direction permitted by the neighborhood. Before receiving any information from the axes, a cell has no way of knowing the precise direction to the origin. If the neighborhood's convex hull has more than one vertex in the positive quarter of the plane, moving along any of the directions permitted by the neighborhood might be sub-optimal, as oppposed to the case of the Moore neighborhood in which going diagonally at first is never sub-optimal and by the time it is necessary to change direction to go either horizontally or vertically information is received from the axes.

If only one cell needs to send its information towards the origin, the problem can be solved by spreading the information in all directions and spreading symmetric signals from the origin. It is however not possible to implement this for all cells at the same time with finitely many states.

Definition 1 (Definition 2 (

 12 Cellular Automaton). A cellular automaton (CA) is a quadruple A = (d, Q, N , δ) where d ∈ N is the dimension of the automaton ; Q is a finite set whose elements are called states ; N is a finite subset of Z d called neighborhood of the automaton ; δ : Q N → Q is the local transition function of the automaton. Configuration). A d-dimensional configuration C over the set of states Q is a mapping from Z d to Q. The elements of Z d will be referred to as cells. Given a CA A = (d, Q, N , δ), a configuration C ∈ Q Z d and a cell c ∈ Z d , we denote by N C (c) the neighborhood of c in C : N C (c) : N → Q n → C(c + n) From the local transition function δ of a CA A = (d, Q, N , δ), we can define the global transition function of the automaton ∆ : Q Z d → Q Z d obtained by applying the local rule on all cells :

Figure 2

 2 Figure 2 Compression of an input of size (14 × 7) with the neighborhood and rules from Figure 1.

Figure 3

 3 Figure 3 An example neighborhood on which a compression by a factor k = 4 is possible.

Figure 4

 4 Figure 4The area of the neighborhood that will be used for the compression of inputs of proportion n m = 2 by a factor k = 4.

Figure 7

 7 Figure 7 Compression of factor k = 2 with the von Neumann neighborhood. The thick line represents ρ(c + N ), the states that are visible to the central cell in one step. The circles represent ρ(c) + N k , the states that should be known to compute two steps of the original automaton on the states that the central cell holds.

Figure 8

 8 Figure 8 The thick line represents ρ(c + N ). The circles represent the cells in (c + kN ) for some c in ρ(c) (the one in the top left).

Lemma 18 .

 18 ∀k ∈ N, ∃α ∈ N, N α + kN = N α + N kProof. The inclusion N α + kN ⊆ N α + N k is obvious for any α. As for the converse, choose α such that α + k > |N |(k -1). Any x ∈ N α + N k can be written as the sum of (α + k)

The constant time α is actually not lost since the origin holds the states that would be on the cells in N α , which enables it to compute its own state α time steps ahead. However, for the purpose of proving Theorem 13, adding a constant time to the computation is irrelevant.

Acknowledgments. The authors would like to thank Jacques Mazoyer for his helpful conversations and inspiring ideas at the start of the work that led to this article.