# Filling Curves Constructed in Cellular Automata with Aperiodic Tiling

Gaétan Richard

► To cite this version:

Gaétan Richard. Filling Curves Constructed in Cellular Automata with Aperiodic Tiling. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.165-175, 10.1007/978-3-319-58631-1_13. hal-01656356

HAL Id: hal-01656356

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

Submitted on 5 Dec 2017

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Filling curves constructed in cellular automata with aperiodic tiling

Gaétan Richard

Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14 000 Caen, FRANCE
gaetan.richard@unicaen.fr

**Abstract.** In many constructions on cellular automata, information is transmitted with signals propagating through a defined background. In this paper, we investigate the possibility of using aperiodic tiling inside zones delimited by signals. More precisely, we study curves delineated by CA-constructible functions and prove that most of them can be filled with the NW-deterministic tile set defined by Kari [1]. The achieved results also hint a new possible way to study deterministic tile sets.

## Introduction

Cellular automata are studied as a computation model with a theoretical computer science approach [2], and as a dynamical complex system with a multidisciplinary approach [3]. The former approach uses specific portions of the whole configuration to encode computation and manages to achieve strong results on complexity or decidability. The latter looks at all configurations and try to prove results on the global behaviour. Roughly speaking, most results for computation deal with the existence of a specific configuration, whereas dynamics study the evolution for all of them.

It is a matter of fact there exists a few results that exploit the computational tools to prove behaviours on all configurations. The key example of such a result is the undecidability of nilpotency by Jarkko Kari [1] in which he uses an aperiodic tiling to recursively embed everywhere in the configuration some parts of computation of arbitrary size. Using this tool, he can send ill-formed configurations “into a sink-hole” and work on the correct ones. More recently, a result has been obtained in the context of synchronisation using the same aperiodic tiling [4]. This construction generates linear zones embedding the aperiodic tiling is used.

In this paper, we investigate the possibility of constructing zones of various shapes embedding aperiodic tiling. Intuitively, we wonder whether we can fill inside of curves generated by methods similar to those used in [5, 6] with Kari's tiling. The results also open interesting questions on determinism of tile sets.

The paper is organised as follow: in section 1, we present the two used models (cellular automata and tile sets) along with notions of constructing and filling. In section 2, we focus on determinism in tiling and look with more details at Kari's tiling. In section 3, we state several results about aperiodic filling. At last, we propose some perspectives in section 4.
# 1 Constructions and fillings

## 1.1 Cellular automata

In this paper, we consider cellular automata in dimension one with nearest neighbours. Therefore, a cellular automaton is a pair $(Q, \delta)$ where $Q$ is a finite set of states and $\delta: Q^3 \to Q$ is the local transition function. We assume that the automaton has a quiescent state $B \in Q$ satisfying $\delta(B, B, B) = B$. The global dynamics is achieved by applying uniformly and synchronously the local transition function to a bi-infinite line of cells: a space-time diagram $D$ is an element of $S^{\mathbb{Z}\times\mathbb{N}}$ satisfying for all $(i,j) \in \mathbb{Z} \times \mathbb{N}, D(i,j+1) = \delta(D(i-1,j), D(i,j), D(i+1,j)).$ One can note that the space-time diagram is fully determined by the initial line $\{D(i,0) | i \in \mathbb{Z}\}$. In this paper, we shall look at the space-time diagram $D_q$ generated by an initial state $q \in Q$, defined as $D_q(0,0) = q$ and $D_q(i,0) = B$ for $i \neq 0$. By the previous remark, this is sufficient to define the whole space-time diagram.

We want to look at functions which can be constructed by cellular automaton as depicted in Figure 1: in the space time diagram generated from a configuration containing only one cell in $q$ and all other cells blank, the curve $f$ is drawn with a subset of marked states $M \subset Q$. The portion above the curve is filled with non-marked non-blank symbols whereas the portion below the curve is filled with blanks.

**Definition 1.** A function $f: \mathbb{N} \to \mathbb{N}$ is constructible if there exists a cellular automaton $(Q \cup \{B\}, \delta), q \in Q$, and $M \subset Q$, such that $D_q$ satisfies:

- $D_q(i, j) = B$ for $i < 0$ and $j \in \mathbb{N}$;

- $D_q(i, f(i)) \in M$ for $i > 0$;

- $D_q(i, j) = B$ for $i > 0$ and $j < f(i)$;

- $D_q(i, j) \in Q \setminus M$ for $i \in \mathbb{N}$ and $j > f(i)$.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** A basic example of constructible function</figcaption></figure>

It can be seen that the definition only makes sense for function $f: \mathbb{N} \to \mathbb{N}$ that are strictly increasing and satisfy $f(0) = 0$.

This notion of constructibility has already been investigated, leading to hierarchy results [7] or even impossibility results [6]. Here, we will focus on filling the zone above the curve with an aperiodic tiling.
## 1.2 Tile set

A Wang tile $t$ is a square tile with coloured edges, as represented in Figure 2. Formally, it is given by a quadruplet $(t_e, t_w, t_n, t_s)$ of symbols chosen among a finite alphabet. A tile set $\tau$ is a finite set of Wang tiles. A tiling of the plane by $\tau$ is a map $T: \mathbb{Z}^2 \to \tau$ from the discrete plane to the tile set so that two tiles that share a common edge agree on the colour: For all integers $i, j$ we have $T(i, j)_e = T(i+1, j)_w$ and $T(i, j)_n = T(i, j+1)_s$. A tiling $T$ is said periodic if there exists $p, p' > 0$ such that for any $i, j \in \mathbb{Z}$, $T(i, j) = T(i+p, j) = T(i, j+p')$.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Wang tiles</figcaption></figure>

Given a constructible function, we want to see in which case the portion above the curve can be (in a constructive way) filled with tiles from a chosen tile set.

**Definition 2.** A function $f$ is fillable by a tile set $\tau$ if it is constructible by a cellular automaton $(Q \cup \{B\}, \delta)$ and there exists a projection $\pi: Q \to \tau$ and a tiling $T$ such that for any $i \in \mathbb{N}$ and $j > f(i)$, $\pi(D_q(i, j)) = T(i, j)$.

With this definition, it is not so difficult to prove that any constructible function can be filled by a tile set which has a periodic tiling.

**Proposition 1.** Let $\tau$ be a tile set which admits a periodic tiling, then any constructible function $f$ is fillable with $\tau$.

*Proof.* Let us take a tile set $\tau$ and $T: \mathbb{Z} \to \tau$, $T(i[p], j[p']) = \tau_{(i,j)}$ be one of its periodic tiling. Let $f$ be a constructible function by a cellular automaton $(Q \cup \{B\}, \delta)$. We extend this automaton by adding a new layer containing the tiling $((Q \cup \{B\}, \tau \cup \{C\}), \delta')$ where

$$ \delta'((q_l, t_l), (q_c, t_c), (q_r, t_r)) = (\delta(q_l, q_c, q_r), t(\delta(q_l, q_c, q_r), t_l, t_c)) $$

and

$$ t(q, t_l, t_c) = \begin{cases} \tau_{(i,j+1[p'])} & \text{if } q \in Q \setminus M \text{ and } t_c = \tau_{(i,j)} \\ \tau_{(i+1[p],j+1[p'])} & \text{if } q \in M \text{ and } t_l = \tau_{(i,j)} \\ C & \text{otherwise} \end{cases} $$

If we set $B' = (B, C)$ and $q'_0 = (q_0, \tau_{(0,0)})$ then it is easy to show by recurrence over $j$ and $i$ that the cellular automaton fills $f$. $\square$
This notion of fillable can be extended to get rid of the constructible constraint. This extension can model the fact that the curve dominated by an external action.

**Definition 3.** A function $f$ is loosely fillable with a tile set $\tau$ if there exists, a cellular automaton $(Q \cup \{B\}, \delta)$, $q \in Q$, a tiling $T$, a diagram $\tilde{D} \in \mathbb{Z} \times \mathbb{N} \to Q$, and a projection $\pi : Q \to \tau$ such that, if we define the diagram $\tilde{D} \in \mathbb{Z} \times \mathbb{N} \to Q$ as

$$ - \tilde{D}(i, j) = B \text{ for } i < 0 \text{ and } j \in \mathbb{N}; $$

$$ - \tilde{D}(i, j) = B \text{ for any } i \ge 0 \text{ and } j < f(i); $$

$$ - \tilde{D}(0, 0) = q; $$

$$ - \tilde{D}(i, j) = \delta(\tilde{D}(i-1, j-1), \tilde{D}(i, j-1), \tilde{D}(i+1, j-1)) \text{ otherwise,} $$

$$ \text{we have for any } i \in \mathbb{N} \text{ and } j > f(i), \pi(\tilde{D}(i, j)) = T(i, j) $$

As previously, this definition makes sense only for functions $f : \mathbb{N} \to \mathbb{N}$ that are strictly increasing and satisfy $f(0) = 0$.

Remark that even if this definition removes the set $M$ to mark the points $(i, f(i))$, it is possible to construct an automaton having this additional property since those points are the first ones in the column which are not in state $B$. The last remark implies that the construction of Proposition 1 applies as well to this extension.

**Proposition 2.** Let $\tau$ be a tile set which admits a periodic tiling, then any function $f$ is loosely fillable with $\tau$.

*Proof.* Just replace the test $q \in M$ by $q \neq B$ and $t_c = C$ in the previous construction.

# 2 Aperiodic tile set

Since filling is easy when the tile set admits a periodic tiling, let us look at what happens in the other case: A tile set $\tau$ is said to be *aperiodic* if there exists at least a valid tiling of the plane but no periodic tiling. A tile set of this kind was first found by Robert Berger [8] to prove undecidability of the AEA fragment of logic. Since, several other aperiodic tile sets have been found [9–12].

## 2.1 From tile set determinism to cellular automaton

In our case, the filling by cellular automata introduces some kind of determinism in the tiling. The corresponding notion has been introduced by Jarkko Kari: a tile set is said to be *north-west deterministic* if there is at most one possible tile $(t_e, t_w, t_n, t_s)$ for every possible choice of $(t_e, t_s)$. To keep the original terminology, north is going down.
This definition introduces one difficulty: the determinism has defined previ-
ously does not go in the same direction than the one induced by cellular au-
tomata. To overcome this problem, we shift each column of 1 relative to the
previous one as depicted in Figure 3.

With this operation, for any $x, y \in \mathbb{N}$, the point at coordinates $(x, y)$ is mapped to the position $(i, j) = (x, y+x)$. Since we have taken $f$ strictly increasing, $f(n) \ge n$ and thus those points are the only ones used in the definition of filling.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** From tile set determinism to cellular automata</figcaption></figure>

We slightly alter the definition of fillable to match this transformation:

**Definition 4.** A function $f$ is fillable by a north-west deterministic tile set $\tau$ if it is constructible by a cellular automaton $(Q \cup \{B\}, \delta)$ and there exists a projection $\pi : Q \to \tau$ and a tiling $T$ such that for any $i \in \mathbb{N}$ and $j > f(i)$, $\pi(D_q(i, j)) = T(i, j - i)$.

The loose fillable variant can be adapted in the same way.

This transformation achieves one easy implication from tile set determinism to cellular automata determinism: if a tile set is north-west deterministic, it can be “simulated” by a cellular automata. The converse is also true: any cellular automata can be “simulated” by a north-west deterministic tiling.

## 2.2 A NW-Deterministic aperiodic tile set

This part is devoted to present the north-west deterministic tile set constructed
by Jarkko Kari in [1] which is built over the tiling from Raphael Robinson [9]).
The reader can refer to those papers for the formal proof of aperiodicity.

This tile set can be described with two layers (corresponding to a Cartesian product). The first one is just a regular 4 coloured grid. The second one is usually depicted using lines. The tiles are depicted in figure 4.

**Theorem 1 (J. Kari, 1992 [1]).** The tile set depicted in figure 4 is north-west deterministic and aperiodic.
<figure><img src="image_5.png" /><figcaption>(a) Background (b) Signals (only light tiles may appear with starred background)</figcaption></figure>

<caption>**Fig. 4.** A north-west deterministic aperiodic tile set</caption>

*Proof (Idea).* The north-west deterministic property is easy to check. The ape-
riodicity is more complex but relies on the following fact: the first layer forces
a 4-periodic background supporting squares of size 2 on the second layer. The
second layer is designed such that squares of size *n* force the existence of squares
of size 2*n*.

We are particularly interested in the specific tiling depicted in figure 5. Due
to the auto-similar characteristic of the tile set, we can see (as represented in
figure 6) that the tiling can be extended to the infinite quarter of plan. Also note
that we can even construct a full tiling of the plan but this will not be of use
here. The main useful point of this partial tiling is that its regularity will allow
to achieve filling.

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** A valid quarter of the plan tiling</figcaption></figure>
### 3 Aperiodic filling

In this section, we shall fill curves using Kari's tile set $\tau_K$ presented in the previous section and especially the portion of the tiling depicted in Figure 5. To better see what happens in this tiling, Figure 6 decorates the lines with different widths (that are not present in the tile set) to highlight the hierarchical structure in which squares assemble themselves into larger squares.

<figure><img src="image_7.png" /><figcaption>Fig. 6. Hierarchical vision of Kari's Tiling</figcaption></figure>

Since the tile set is NW deterministic, we define as $K : \tau_K \times \tau_K \to (\tau_K \cup \emptyset)$ the application which associate to two tiles, the unique one fitting in the NW corner (if it exists).

#### 3.1 Linear functions

The first result concerns identity function and corresponds to the case used in [4].

**Proposition 3.** *The function $f(n) = n$ is fillable by Kari's tile set.*

*Proof.* The constructibility of $f$ is trivial.

To fill the curve, we shall add a layer similarly than in the proof of Proposition 1. This layer correspond to the tiling depicted previously. Inside the curve, we use NW determinism to guess the tile; On the borders (vertical on the left and diagonal on the right), we use the property that this correspond to lines over which the tiling has periodic behaviour of period 2 (see Figure 6. Let us call $\tau_0^l = T(0, 2i), i \ge 0$, $\tau_1^l = T(0, 2i + 1), i \ge 0$, $\tau_0^r = T(2i, 0), i > 0$, and $\tau_1^r = T(2i + 1, 0), i \ge 0$.
Let $f(n) = n$ be constructible by a cellular automaton $(Q \cup \{B\}, \delta)$. We extend this automata by adding a new layer containing the tiling $((Q \cup \{B\}, \tau_K \cup \{C\}), \delta')$ where $\delta'((q_l, t_l), (q_c, t_c), (q_r, t_r)) = (\delta(q_l, q_c, q_r), t(\delta(q_l, q_c, q_r), t_l, t_c))$ and

$$t(q, t_l, t_c) = \begin{cases} K(t_l, t_c) & \text{if } q \in Q \setminus M, t_l \neq C \text{ and } K(t_l, t_c) \neq \emptyset \\ \tau_{i+1[2]}^r & \text{if } q \in M \text{ and } t_l = \tau_i^r \\ \tau_1^r & \text{if } q \in M \text{ and } t_l = \tau_0^l \\ \tau_{i+1[2]}^l & \text{if } q \in Q \setminus M, t_l = C \text{ and } t_c = \tau_i^l \\ C & \text{otherwise} \end{cases}$$

If we set $B' = (B, C)$ and $q'_0 = (q_0, T(0,0) = \tau_0^l)$, we can see that the forth case of $t$ correspond to cells which are on the Y-axis of both the tiling and the space-time diagram; the second case correspond to the X-axis of the tiling and the marked diagonal of the space-time diagram (the third case is the specific case happening at (0,0). At last, the first case cover the inside of the tiling and the curve.

As we have chosen a valid tiling, it can be noted that the condition $K(t_l, t_c) \neq \emptyset$ is always valid in the first case and thus $C$ only occurs outside the curve. It follows that our conditions do correctly match boundaries and fill it with correct tiles. $\square$

The previous proof relies on the fact that the tiling we use has two non-collinear lines on which it is periodic. It may be interesting to search whether this condition is sufficient or necessary to achieve the result and eventually look at aperiodic deterministic tile set not exhibiting such condition if they exists.

The previous result can be extended to linear functions for which the coefficient is a rational number.

**Corollary 1.** For any $\alpha \in \mathbb{Q}$, $\alpha > 1$ The function $f(n) = \alpha n$ is fillable by an aperiodic tile set.

*Proof.* Constructing $f$ consist on a signal of slope $1/\alpha$ which is the most simple one to construct.

To fill, it is sufficient to apply a grouping by bloc of $(n \times m)$ where $\alpha = m/n$ to Kari's tiling and reuse the previous proof. The grouping preserves the NW-determinism and the regular lines in the tiling are shifted to the correct place. $\square$

## 3.2 Over-logarithmic growth functions

For now, we haven't still make use of the regularity visible in the tiling. This will allow us to gave a more general result:

**Proposition 4.** Let $f$ be a constructible function such that, for all $n \in \mathbb{N}$, $f(n+1) - f(n) > 2\log_2(n)$, then $f$ is fillable with Kari's tile set.
*Proof.* Once again, we shall use the same method as in the proof of proposition 3. In fact, the only difference is in the second and third case in the definition of $t$ (the method to find the correct tile on the curve). All other cases are unchanged. Thus, the only case posing problem is to find the tile to put at positions marked $(i, f(i))$.

Let us look at the corresponding part in the tiling (see Figure 7). It can be easily seen that among the information needed, most of it can be deduced from the cell to the bottom left of it (the east one). In fact, the background colour, the diagonal and the horizontal signals can be deduced leaving only the vertical signal.

<figure><img src="image_8.png" /><figcaption>**Fig. 7.** Guessing the correct tile at position $(i, f(i))$</figcaption></figure>

Looking more in detail at figure 6, we can see that this signal has a high regularity: if we consider the $x$-th vertical line, the signal is periodic of period $2^{i+2}$ where $i$ is the least significant non-zero bit of $x+1$ (that is, all odd columns have period 4, all even but not multiple of 4 have period 8, ...). More specifically, the signal alternates every $2^i$ on a cycle of 4 colours with the same starting point on the X-axis. Thus, to find the last missing piece of information, it is sufficient to keep track of $x+1$ and $y$ (Y-value) corresponding to the position in the tiling and extract the correct bits.

Let us now look if it is possible to compute such values inside the interval. To do this, it is possible to maintain two integers recording $x$ and $y$. To increment the value of $y$ at each time steps, we need to use an increment with a lazy carry as in Figure 8a. In this setup, the value of the counter can be read diagonally. It is also possible to shift the counter to the right keeping the same value as in Figure 8b. The counter $x$ is done in a similar way. Once both counters are present, the value needed can be easily extracted in $2 \log(n)$ steps as depicted in Figure 8c.

The previous method is correct but gives the result with a $2\log(n)$ delay (which explain the condition on the growth of $f$). However, since there are only 4 possibilities, it is easy to try all of them simultaneously and erase the incorrect one when the result arrives. To be fully coherent with our definition, which require the projection to know exactly which is the tile, the previous method
<figure><img src="image_9.png" /><figcaption>**Fig. 8.** Finding missing information for a new tile</figcaption></figure>

can be slightly altered to guess one vertical line in advance and keep it in addition
to the current tile.

One last point to underline is that our proof assumes that there is always
enough place to keep the counters. If it is true for $x$, it may not be the case for $y$. However, in the latter case, it means that $y = O(2^x)$ and since the vertical
strip of width $x$ the tiling is periodic of period $4^x$, we can forget the high bits of $y$ and still fill with a valid tiling. $\square$

Even if our proof only use the marked *M* subset from the constructible
function, this set can be emulated also in loose fill which allows to extend the
result to this case.

**Corollary 2.** Let $f$ be a function such that, for all $n \in \mathbb{N}$, $f(n+1) - f(n) > 2\log_2(n)$, then $f$ is loosely fillable with Kari's tile set.

For the constructibility, there exists a gap between $n-\log(n)$ and $n$ where any
function is not constructible [6]. At the moment, our result would suggest that
there may be a similar gap for filling. This kind of result could prove interesting
to better understand computation by cellular automata.

# 4 Conclusions and perspectives

In this paper, we have shown that Kari's tile set can be used deterministically
to fill curves. This method may open new possibilities to results on the whole
set of configuration using computability tricks since it is easy to force this tile
set to embed computation.
With respect to this specific tile set, the question of optimality of results in section 3 is still an open question. The logarithmic growth condition is due to the maximal complexity of our method to find the next valid tile. It can be noted that the mean complexity is constant so there is perhaps room for improvement even using our proof.

All those results are based on the “regularity” of one tiling in periodic or Kari’s tile set. This leads directly to try and generalise this for a wider range of tile set. In particular, one question is to find if there exists tile set for which the set of fillable function is different and understand why.

In this way, one class of tile set which may prove interesting are the one that can be depicted using substitutions. One first look at this set was done by Fernique and Ollinger [13]. The introduction of determinism and fill may allow to further discriminate into this class.

At last, one cannot end without asking how results extend in dimension two. Here, the main point is that this changes a lot the problem since the determinism is no more inside the tiling but only on its frontier and that it involves more complex geometric concepts since the border is no longer restricted to two points. Although very different, it may also be interesting in particular linking with the concept of self-assembly tile sets [14].

## References

1. Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM Journal on Computing **21**(3) (1992) 571–586

2. Kari, J.: Theory of cellular automata: a survey. Theoretical Computer Science **334**(1-3) (2005) 3–33

3. Ganguly, N., Sikdar, B.K., Deutsch, A., Canright, G., Chaudhuri, P.P.: A survey on cellular automata. Technical report, Centre for High Performance Computing, Dresden University of Technology (2003)

4. Richard, G.: On the synchronisation problem over cellular automata. In: 34th International Symposium on Theoretical Aspects of Computer Science. (2017) To appear.

5. Fischer, P.C.: Generation of primes by a one-dimensional real-time iterative array. Journal of the ACM **12**(3) (1965) 388–394

6. Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata. Theoretical Computer Science **217**(1) (1999) 53–80

7. Iwamoto, C., Hatsuyama, T., Morita, K., Imai, K.: Constructible functions in cellular automata and their applications to hierarchy results. Theor. Comput. Sci. **270**(1-2) (jan 2002) 797–809

8. Berger, R.: The undecidability of the domino problem. PhD thesis, Harvard University (1964)

9. Robinson, R.: Undecidability and nonperiodicity for tilings of the plane. Inventions Mathematicae **12** (1971)

10. Penrose, R.: The role of aesthetics in pure and applied mathematical research. Bulletin of the Institute of Mathematics and Its Applications **10**(2) (1974) 266–271
11. Čulík II, K., Kari, J.: An aperiodic set of wang cubes. In Puech, C., Reischuk, R., eds.: STACS. Volume 1046 of Lecture Notes in Computer Science., Springer (1996) 137–146

12. Ben-Abraham, S.I., Gähler, F.: Covering cluster description of octagonal mnsial quasicrystals. Phys. Rev. B 60 (Jul 1999) 860–864

13. Fernique, T., Ollinger, N.: Combinatorial substitutions and sofic tilings. In Kari, J., ed.: Second Symposium on Cellular Automata "Journeacute;es AutomatesCEL- LULAIRES", JAC 2010, Turku, Finland, December 15-17, 2010. Proceedings, Turku Center for Computer Science (2010) 100–110

14. Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Natural Computing 13(2) (2014) 195–224