Theory Comput Syst (2011) 48: 693714 DOI 10.

1007/s00224-010-9255-x

Topological Dynamics of Cellular Automata: Dimension Matters

Published online: 10 April 2010 Springer Science+Business Media, LLC 2010

Abstract Topological dynamics of cellular automata (CA), inherited from classical dynamical systems theory, has been essentially studied in dimension 1. This paper focuses on higher dimensional CA and aims at showing that the situation is different and more complex starting from dimension 2. The main results are the existence of non sensitive CA without equicontinuous points, the non-recursivity of sensitivity constants, the existence of CA having only non-recursive equicontinuous points and the existence of CA having only countably many equicontinuous points. They all show a difference between dimension 1 and higher dimensions. Thanks to these new constructions, we also extend undecidability results concerning topological classication previously obtained in the 1D case. Finally, we show that the set of sensitive 0 in dimension 1, but becomes 0 -hard for dimension 3. CA is only 2 3 Keywords Multidimensional cellular automata Topological dynamics Complexity of decision problem 1 Introduction Cellular automata were introduced by J. von Neumann as a simple formal model of cellular growth and replication. They consist in a discrete lattice of nite-state machines, called cells, which evolve uniformly and synchronously according to a local rule depending only on a nite number of neighbouring cells. A snapshot of
M. Sablik ( ) LATP, UMR 6632CNRS, Universit de Provence, CMI, Universit de Provence, Technople Chteau-Gombert, 39, rue F. Joliot Curie, 13453 Marseille Cedex 13, France e-mail: sablik@cmi.univ-mrs.fr G. Theyssier LAMA, UMR 5127CNRS, Universit de Savoie, Campus Scientique, 73376 Le Bourget-du-lac Cedex, France e-mail: guillaume.theyssier@univ-savoie.fr

694

Theory Comput Syst (2011) 48: 693714

the states of the cells at some time of the evolution is called a conguration, and a cellular automaton can be view as a global action on the set of congurations. Despite the apparent simplicity of their denition, cellular automata can have very complex behaviours. One way to try to understand this complexity is to endow the space of congurations with a topology and consider cellular automata as classical dynamical systems. With such a point of view, one can use well-tried tools from dynamical system theory like the notion of sensitivity to initial condition or the notion of equicontinuous point. This approach has been followed essentially in the case of one-dimensional cellular automata. P. K urka has shown in [10] that 1D cellular automata are partitioned into two classes: Equ , the set of cellular automata with equicontinuous points, Sens , the set of sensitive cellular automata. We stress that this partition result is false in general for classical (continuous) dynamical systems. Thus, it is natural to ask whether this result holds for the model of CA in any dimension, or if it is a miracle or an anomaly of the one-dimensional case due to the strong constraints on information propagation in this particular setting. One of the main contributions of this paper is to show that this is an anomaly of the 1D case (Sect. 3): there exist a class N of 2D CA which are neither in Equ nor in Sens . Each of the sets Equ and Sens has an extremal sub-class: equicontinuous and expansive cellular automata (respectively). This allows to classify cellular automata in four classes according to the degree of sensitivity to initial conditions. The dynamical properties involved in this classication have been intensively studied in the literature for 1D cellular automata (see for instance [3, 4, 6, 10]). Moreover, in [5], the undecidability of this classication is proved, except for the expansivity class whose decidability remains an open problem. In this paper, we focus on 2D CA and we are particularly interested in differences from the 1D case. As said above, we will prove in Sect. 3 that there is a fundamental difference with respect to the topological dynamics classication, but we will also adopt a computational complexity point of view and show that some properties or parameters which are computable in 1D are non recursive in 2D (Propositions 8 and 9 of Sect. 5). To our knowledge, only few dimension-sensitive undecidability results are known for CA [2, 9]. However, we believe that such subtle differences are of great importance in a eld where the common belief is that everything interesting is undecidable. Moreover, we establish in Sect. 5 several complexity lower bounds on the classes dened above and extend the undecidability result of [5] to dimension 2. Notably, we show that each of the class Equ , Sens and N is neither recursively enumerable, nor co-recursively enumerable. This gives new examples of natural properties of CA that are harder than the classical problems like reversibility, surjectivity or nilpotency (which are all r.e. or co-r.e.). Finally, we show two additional results advocating the importance of dimension in topological dynamics: rst, there are 2D CA having only a countable set of equicon0 in dimension 1 to tinuous points and, second, the set of sensitive CA raises from 2 0 -complete in dimension 3. These results improve [13]. 3

Theory Comput Syst (2011) 48: 693714

695

2 Denitions Let A be a nite set and M = Zd (for the d -dimensional case). We consider AM , the conguration space of M-indexed sequences in A. If A is endowed with the discrete topology, AM is compact, perfect and totally disconnected in the product topology. Moreover one can dene a metric on AM compatible with this topology: x, y AM , dC (x, y) = 2 min{
i
:xi =yi

i M}

Let U M. For x AM , denote xU AU the restriction of x to U. Let U M be a nite subset, is a subshift of nite type of order U if there exists F AU such that x xm+U F m M. In other word, can be viewed as a tiling where the allowed patterns are in F . In this paper, we will consider tile sets and ask whether they can tile the plane or not. In our formalism, a tile set is a subshift of nite type: a set of states (the tiles) given together with a set of allowed patterns (the tiling constraints). A cellular automaton (CA) is a pair (AM , F ) where F : AM AM is dened by F (x)(m) = f ((x(m + u))uU ) for all x AM and m M where U Z is a nite set named neighbourhood and f : AU A is a local rule. The radius of F is r(F ) = max{ u : u U}. By Hedlunds theorem [8], it is equivalent to say that F is a continuous function which commutes with the shift (i.e. m F = F m for all m M). We recall here general denitions of topological dynamics used all along the article. Let (X, d) be a metric space and F : X X be a continuous function. x X is an equicontinuous point if for all > 0, there exists > 0, such that for all y X , if d(x, y) < then d(F n (x), F n (y)) < for all n N. (X, F ) is sensitive if there exists > 0 such that for all > 0 and x X , there exists y X and n N such that d(x, y) < and d(F n (x), F n (y)) > . In the denition above about properties of topological dynamics, the dimension of the cellular automaton considered do not appear explicitly. Whereas essentially studied in dimension 1 in the literature, the present paper consider those properties in any dimension. A rst (trivial) approach to study topological dynamics properties according to dimension is given by the following proposition through the notion of canonical lift from dimension d to dimension d + 1. The canonical lift of a CA of dimension d with neighbourhood U and local rule f is the CA of dimension d + 1, of local rule f and of neighbourhood U obtained by adding a coordinate equal to 0 to each vector of U. Proposition 1 Let F be a CA of dimension d and let F be its canonical lift to dimension d + 1. Then we have the following: F has equicontinuous points if and only if F has equicontinuous points; F is sensitive to initial conditions if and only if F is sensitive to initial conditions. Proof Straightforward.

696

Theory Comput Syst (2011) 48: 693714

This proposition essentially says that what can be seen in dimension d (concerning some topological dynamics properties) can also be seen in dimension d + 1. One of the main point of the present paper is to show that the converse is false: some behaviours cannot be seen in low-dimensional cellular automata.

3 The Core Construction In this section, we will construct a 2D CA which has no equicontinuous point and is not sensitive to initial conditions. This is in contrast with dimension 1 where any non-sensitive CA must have equicontinuous points as shown in [10] (such differences according to dimension will be further discussed in Sect. 5). The CA (denoted by F in the following) is made of two components: a solid component (almost static) for which only nite type conditions are checked and corrections are made locally; a liquid component whose overall behaviour is to inltrate the solid component and allow some particles to move left and to bypass solid obstacles. The general behaviour of this cellular automaton can be seen as an erosion/inltration process. States from the solid component can be turned into liquid state according to certain local conditions but the converse is impossible. Therefore the set of solid states is decreasing (erosion process) until some particular kind of conguration is reached (erosion result). Then, in such congurations, the particles can bypass any sequence of obstacles and reach any liquid position (inltration). 3.1 Denition Formally, F has a Moores neighbourhood of radius 2 (25 neighbours) and a state set A with 12 elements : A = {U, D, 0, 1, , , , , , , , } where the subset S = {1, , , , , , , , } corresponds to the solid component and L = {U, D, 0} to the liquid component where 0 should be thought as the substratum where particles made of elementary constituents U and D can move. 2 Let S be the subshift of nite type of AZ dened by the set of allowed patterns constituted by all the 3 3 patterns appearing in the following set of nite congurations: L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L 1 1 1 1 1 1 L L L L L L L L 1 1 1 L L L L L L L L L L L L L L L L L L L L L L L L

Intuitively, S denes the admissible solid obstacles, i.e. solid shapes that are stable and no longer eroded in a liquid environment.

Theory Comput Syst (2011) 48: 693714 Fig. 1 A particle separating into two parts (U and D ) to bypass a solid obstacle (the black region)

697

The local transition function of F can be sketched as follows: states from S are turned into 0s if nite type conditions dening S are violated locally and left unchanged in any other case; states U and D behave like a left-moving particle when U is just above D in a background of 0s, and they separate to bypass solid obstacles, U going over and D going under, until they meet at the opposite position and recompose a left-moving particle (see Fig. 1). A precise denition of the local transition function of F is the following: 1. if the neighbourhood (5 5 cells) forms a pattern forbidden in S , then turn into state 0; 2. else, apply (if possible) one of the transition rules depending only on the 3 3 neighbourhood detailed in Fig. 2; 3. in any other case, turn into state 0. Note for instance, that any solid state surrounded by a valid neighbourhood is left unchanged by F (second case of the denition above apply since the 3 rst transitions of Fig. 2 include all possible valid 3 3 neighbourhoods seen by a solid state). 3.2 Erosion and Inltration A conguration x is said to be nite if the set {z : x(z) = 0} is nite. The next lemma shows that S attracts any nite conguration under the action of F . Moreover, after some time, all particles are on the left of the nite solid part. Lemma 1 (Erosion process) For any nite conguration x , there exists t0 such that t t0 : F t (x) S and, in F t (x), any occurrence of U or D is on the left of any occurrence of any state from S . Proof First, the set {z : x(z) S } is nite and decreasing under the action of F . Moreover, U and D states can only move left, or move vertically or disappear. Since the total amount of vertical moves for U and D states is bounded by the cardinal of {z : x(z) S }, there is a time t after which all U or D state are on the left of all occurrences of states from S , and each U is above a D in a 0 background (the U D particle is on the left of the nite non-0 region). From this time on, the evolution of

698

Theory Comput Syst (2011) 48: 693714

Fig. 2 Part of the transition rule of F (curved arrows mean that the transition is the same for any rotation of the neighbourhood pattern by an angle multiple of /2)

cells in a state of S is governed only by the rst case of the denition of F . Therefore, after a certain time, nite type conditions dening S are veried everywhere. To conclude, it is easy to check that S is stable under the action of F . The following lemma states that nite congurations from S consist of rectangle obstacles inside a liquid background. Moreover, obstacles are spaced enough to ensure that any position sees at most one obstacle in its 3 3 neighbourhood. In the sequel we use notation South(), East(), West(), North() for the elementary translations in Z2 . Lemma 2 (Erosion result) Let x S be a nite conguration. Then the set X = {z Z2 : x(z) S } is a union of disjoint rectangles which are pairwise spaced by at least 2 cells.

Theory Comput Syst (2011) 48: 693714 Fig. 3 Denition of the path (zn )n in the presence of obstacles

699

Proof Straightforward from denition of S . An obstacle is a (nite) rectangular region of states from S surrounded by liquid states. The following lemma establishes the key property of the dynamics of F : particles can reach any liquid position inside a nite eld of obstacles from arbitrarily far away from the eld. Lemma 3 (Inltration) Let x S be a nite conguration. For any z0 Z2 such that x(z0 ) = 0 there exists a path (zn ) such that: 1. zn 2. n0 , n n0 , if xn is the conguration obtained from x by adding a particle at position zn (precisely, xn (zn ) = U and xn (South(zn )) = D) then (F n (xn ))(z0 ) {U, D }. Proof First, we suppose that x S ({0} S )Z . Since x S and x(z0 ) = 0, then either x(South(z0 )) = 0 or x(North(z0 )) = 0 by Lemma 2. We will consider only the rst case since the proof for the second one is similar. Let (zn ) be the path starting from z0 dened as follows:
2

If x(East(zn )) = 0 and x(South(East(zn ))) = 0 then zn+1 = East(zn ). Else, position East(zn ) and/or position South(East(zn )) belongs to an obstacle P . Let a , b and c be the positions of the upper-left, upper-right and lower-right outside corners of P and let p be its half perimeter. Then dene zn+1 , . . . , zn+p+1 to be the sequence of positions made of (see Fig. 3): a (possibly empty) vertical segment from zn to a , the segment [a ; b], a (possibly empty) vertical segment from b to zn+p+1 where zn+p+1 is the point on [b; c] such that zn a + bzn+p+1 = bc.

700

Theory Comput Syst (2011) 48: 693714

We claim that the path (zn ) constructed above has the properties of the lemma. Indeed, one can check that for each case of the inductive construction of a point zm from a point zn we have: zm > zn , F mn (xm )(zn ) = U and F mn (xm )(South(zn )) = D . The lemma is thus proved for x S ({0} S )Z . It extends to any nite x S because in such a conguration Lemma 1 ensures that after some time t0 all occurrences of U and D are on the left of z0 , whereas the path constructed above is on the right of z0 . More precisely, if x is the conguration obtained from x by replacing any liquid state by 0, and if (zn )n is the path constructed for x , then the path (zt0 +n )n fullls the requirements of the lemma for x .
2

3.3 Topological Dynamics Properties The possibility to form arbitrarily large obstacles prevents F from being sensitive to initial conditions. Proposition 2 F is not sensitive to initial conditions. Proof Let > 0. Let c be the conguration everywhere equal to 0 except in the square region of side 2 log around the center where there is a valid obstacle. 2 y AZ , if d(y, c ) /4 then t 0, d(F t (c ), F t (y)) since a well-formed obstacle (precisely, a partial conguration that would form a valid obstacle when completed by 0 everywhere) is unalterable for F provided it is surrounded by states in L (see the 3 rst transition rules of case 2 in the denition of the local rule): this is guarantied for y by the condition d(y, c ) /4. The erosion and inltration process described above ensures that particles can circulate everywhere in the liquid part of nite congurations. This is the key ingredient of the following proposition. Proposition 3 F has no equicontinuous points. Proof Assume F has an equicontinuous point, precisely a point x which veries > 0, : y, d(x, y) t, d(F t (x), F t (y)) . Suppose that there is z0 such that x(z0 ) = 0 and let = 2 z0 1 . We will show that the hypothesis of x being an equicontinuous point is violated for this particular choice of . Consider any > 0 and let y be the conguration everywhere equal to 0 except in the central region of radius log where it is identical to x . Since y is nite, there exists t0 such that y+ = F t0 (y) S (by Lemma 1). Moreover, Lemma 1 guaranties that for any positive integer t , F t (y+ )(z0 ) = x(z0 ) = 0. Applying Lemma 3 on y+ and position z0 , we get the existence of a path (zn ) allowing particles placed arbitrarily far away from z0 to reach the position z0 after a certain time. For any sufciently large n, we construct a conguration y obtained from y by adding a particle at position zn . By the property of (zn ), we have:

Theory Comput Syst (2011) 48: 693714

701

F n (y)(z0 ) = F n (y )(z0 ) and therefore d(F n (y), F n (y )) > . Since, if n > log , both y and y are in the ball of center x and radius , we have the desired contradiction. Assume now that z, x(z) S . There must exist some position z0 such that x(z0 ) S \ {1} (it is straightforward to check that the uniform conguration everywhere equal to 1 is not an equicontinuous point). It follows from the denition of S that z0 belongs to a forbidden pattern for S (any solid state different from 1 must have a liquid state in its neighbourhood). Therefore F (x)(z0 ) = 0 and we can use the reasoning of the previous case of this proof on conguration F (x). Finally, if z, x(z) = 0 and z0 , x(z0 ) {U, D } then necessarily F (x)(z0 ) = 0 and the rst reasoning of the proof can be applied.

4 Variations 4.1 Adding Wang Tile Constraints The rst variation on F we consider is to add some tiling constraints to the solid component. More precisely, for any tile set , we dene a 2D CA F which is identical to F except for the following modications: the solid state 1 is replaced by the set so that the state set of F is A = {U, D, 0, , , , , , , , } where the solid component is the subset S = {, , , , , , , } and the liquid component is also L = {U, D, 0}; the sub-shift of admissible obstacles now becomes F, dened by the set of allowed patterns constituted by all the 3 3 patterns appearing in the following set of nite congurations: L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L

with the additional condition that two adjacent cells in a state from must fullls the tiling constraints involved in the tile set . The behaviour of F is similar to that of F replacing S by F, . More precisely: 1. if the neighbourhood (5 5 cells) forms a pattern forbidden in F, , then turn into state 0; 2. else, apply (if possible) one of the transition rules depending only on the 3 3 neighbourhood detailed in Fig. 2 (replacing S by S );

702

Theory Comput Syst (2011) 48: 693714

3. in any other case, turn into state 0. As for F , the erosion/inltration mechanism prevents from any equicontinuous point. Moreover the sensitivity to initial conditions of F is controlled by the tile set as shown by the following proposition. Proposition 4 Let be any tile set. Then we have the following: F has no equicontinuous point; F is sensitive to initial conditions if and only if does not tile the plane. Moreover, in this case, the maximal sensitivity constant is an exponential function of n, where n n is the size of the largest admissible square tiling. Proof Firstly, it follows from denition of F that Lemmas 1, 2 and 3 as well as Proposition 3 remain true. Indeed, considering any conguration x of F , and any t 0, then we have {z : Ft (x)(z) S } {z : F t (x )(z) S } where x is the conguration of F obtained from x be replacing any occurrence of states from by 1. Moreover, if can tile the plane then it is possible to form arbitrarily large valid obstacles, so F is not sensitive to initial conditions (same reasoning as in Proposition 2). Conversely, if cannot tile the plane, then there is n such that no valid tiling of a (2n + 1) (2n + 1) square exists. This implies that, in any conguration x of F , there is some z0 with z0 n such that either x(z0 ) L, or F (x)(z0 ) L (z0 corresponds to some error for F, ). Then, applying Lemma 3 to position z0 as in the proof of Proposition 3, we have: > 0, y, t 0 : d(x, y) and d(Ft (x), Ft (y)) 2n .

Since the constant n is independent of the choice of the initial conguration x , we have shown that F is sensitive to initial conditions with sensitivity constant 2n . 4.2 Controlling Erosion In this section, we dene G , another variant of F , which has an overall similar behaviour but uses a different kind of obstacles and a different kind of erosion process depending on a tile set . Obstacles are protected from liquid component by a boundary as the classical obstacles of F , but they are made only of successive boundaries like onion skins. Moreover, invalid patterns in the solid component do not provoke the complete destruction of obstacles as in F . The solid component of G is the set R = X where X = {, , , , , , , , }.

The liquid component is identical to that of F , precisely L = {U, D, 0}.

Theory Comput Syst (2011) 48: 693714 Fig. 4 Inside (white) and outside (black) positions for states of X

703

The obstacle sub-shift G, of G is dened by the set of allowed patterns constituted by all 3 3 patterns appearing in the following set of partial congurations: L L L L L L L L L L L L L L L L R R R L L R R R L L R R R L L L L L L L L L L L

with the additional conditions that the component is a valid tiling and the X component is made exclusively from the set of 2 2 patterns appearing in the following partial conguration:

The X component is used to give to any cell inside a solid region a local notion of inside and outside as depicted by Fig. 4 (up to /2 rotations): arrows point to the inside region. The behaviour of G is precisely the following: 1. if the neighbourhood (5 5 cells) forms a pattern forbidden in G, , then the state is left unchanged except for the following cases where it turns into state 0: if the cell is in a liquid state; if the inside region of the cell forms a forbidden pattern, the cell together with one of its neighbour forms a forbidden pattern 2. else, apply (if possible) one of the transition rules depending only on the 3 3 neighbourhood detailed in Fig. 2 (replacing S by R ); 3. in any other case, leave the state unchanged if it is solid and turn into 0 if it is liquid. As for F , a conguration is said nite if it contains only a nite number of cells in a solid state. Lemma 4 (Erosion result) Let be any tile set. Let x G, be a nite conguration. Then the set X = {z Z2 : x(z) R } is a union of disjoint squares with sides of odd length containing the state at the center, and which are pairwise spaced by at least 2 cells.

704

Theory Comput Syst (2011) 48: 693714

Proof By denition of G, , x is necessarily made of rectangular obstacles which are pairwise spaced by at least 2 cells. Moreover, the X component ensures that the border of any rectangular obstacle is made as follows: only state (resp. , and ) on the left (resp. right, top and bottom) side; only state (resp. , and ) on the top-left (resp. top-right, bottom-right and bottom-left) corner. Remark that the X component requires that the sequence of state obtained by starting from a corner and advancing in the corresponding diagonal direction is a succession of identical diagonal arrows, then the state and then a sequence of opposite diagonal arrows. This implies that the obstacle is a square of odd side length and that the state is in the center. From now on, we call valid obstacle for G a n n square (n odd) of solid states with state in the center and forming a valid pattern of G, . Lemma 5 (Conservative erosion process) Let be any tile set. For any nite conguration x we have the following:
t 1. there exists t0 such that, t t0 , Gt (x) G, and, in G (x), any occurrence of U or D is on the left of any occurrence of any state from R ; 2. if z0 and n 7, n odd, are such that x contains a valid n n obstacle centered on z0 then t 0 Gt (x) contains the same valid (n 4) (n 4) square obstacle centered on z0

Proof The rst part of this lemma follows by applying arguments of the proof of Lemma 1 to G . The only point to check is that given any forbidden pattern for G, we have (straightforward from the denition of G, and interior regions): either a pair of cells at distance at most 2, both in a solid state, and which form a forbidden pattern by themselves, or a cell in a solid state whose inside region forms a forbidden pattern. Thus, the number of cells in a solid state is guaranteed to decrease while the current conguration is not in G, . Therefore G, is reached in nite time (any conguration without solid states belongs to G, ). For the second part of the lemma, consider all cells z of the lattice such that 5 z z0 n 2 (i.e. cells belonging to the (n 4) (n 4) square centered on z0 ). Initially, those cells have a valid neighbourhood so after one step, they all stay in the same state. Therefore, by denition of a valid square obstacle, they all have a valid interior region after one step. Moreover, in their exterior region, they all have either valid solid states as in the initial step, or liquid states (if some cell at the boundary of the n n square has turned into state 0): in any case, by denition of exterior regions, no such cell z has a cell in its neighbourhood to form a forbidden pattern with. Therefore, all cells z stay unchanged after two step, and the reasoning can be iterated forever.

Theory Comput Syst (2011) 48: 693714

705

The inltration lemma (Lemma 3 for F ) remains true here, simply replacing S by G, . Combined with the above lemmas, it implies the following proposition. Proposition 5 Let be any tile set. Then G is sensitive to initial conditions if does not tile the plane, and it admits equicontinuous points if tiles the plane. Moreover, in the latter case, any equicontinuous point has the following properties: it is made only of solid states; it contains exactly one occurrence of state ; its component forms a valid tiling. Proof First, suppose that cannot tile the plane. Then there exists n such that there is no valid square tiling of size n n. Using the same reasoning as in Proposition 4, we deduce that G is sensitive to initial conditions (because, by Lemma 5, after some time a liquid state must appear at some position z with z n and the inltration can be applied to that position). Now suppose that can tile the plane. Consider the conguration x made only of solid states and such that: the component is a valid tiling; the X component is made of state is at position (0, 0) and completed everywhere in a valid way. Since any n n square centered on position (0, 0) is a valid square obstacle, Lemma 5 shows that x is an equicontinuous point. Indeed, for any n and for any conguration y having a valid n n square obstacle centered on position (0, 0), we have that the orbits of x and y under the action of G coincide on the central (n 4) (n 4) part. Finally, consider any equicontinuous point x of G . Using the reasoning of the rst part of this proof, we show that x contains only solid states and that its component forms a valid tiling. Moreover, suppose that the X component contain at least 2 occurrences of state and let n be such that 2 occurrences of are contained in the n n central square of x . By Lemmas 5 and 4, for any nite conguration y identical to x on the central n n region, there is some time after which some cell in the central n n region is in a liquid state (because no valid obstacle can contain two occurrences of ). From that point, the inltration argument can be applied, contradicting the fact that x is an equicontinuous point. To conclude the proposition, it remains the case where the conguration x considered contains no occurrence of . This case is treated as above, since valid square obstacles must contain an occurrence of as stated by Lemma 4. 4.3 Combining Two Solid Components Our last variation, called H , is a simple combination of F and G (for any given tile set ). More precisely, it is the CA dened over state set S R L with the following behaviour: if the neighbour contains only states from S L then behave like F ;

706

Theory Comput Syst (2011) 48: 693714

Automaton F F G H
Fig. 5 Summary of constructions

Solid component S S R R S

Behaviour N Sens if tiles, N else Equ if tiles, Sens else Equ if tiles, N else

if the neighbour contains only states from R L then behave like G ; in any other case, turn into state 0. Using what was previously established for F and G , we have the following proposition for H . Proposition 6 Let be any tile set. Then H is not sensitive to initial conditions and it admits equicontinuous points if and only if tiles the plane. Proof Since arbitrarily large obstacles of type S can be formed, the reasoning of the proof of Proposition 2 can be applied here showing that H is not sensitive to initial conditions. Moreover, any equicontinuous point of x of G is an equicontinuous point of H . Indeed, for any n, any conguration y identical to x is the central n n region veries that at any time t , the central n n region of Ht (y) is made only of states from R L and is therefore governed by G . Thus, the reasoning of Proposition 5 applies here. Hence, if can tile the plane, then H admits equicontinuous points. Conversely, suppose that cannot tile the plane. So H has no equicontinuous 2 points in (R L)Z because it would be an equicontinuous point for G , thus con2 tradicting Proposition 5. Similarly, there cannot be equicontinuous point in (S L)Z because it would contradict Proposition 3. Finally, a conguration x containing states from both sets S and R cannot be an equicontinuous point either because x or H (x) necessarily contains a liquid state and in such a case the inltration argument can be applied as in Proposition 3 (Lemmas 2, 1 and 3 are true for H ).

5 Topological Classication Revisited Equipped with the various constructions detailed above (see Fig. 5), we study in this section the topological classication of P. K urka (put aside expansivity) for higher dimensional cellular automata. In [5], the authors give a recursive construction which produce either a 1D CA with equicontinuous points or a 1D sensitive CA according to whether a Turing machine halts on the empty input or not. By Proposition 1, we get the following result. Proposition 7 For any dimension, the classes Sens and Equ are recursively inseparable. Moreover, Sens is not recursively enumerable and Equ is not co-recursively enumerable.

Theory Comput Syst (2011) 48: 693714

707

However, this is not enough to establish the overall undecidability of the topological classication of 2D CA. The main concern of this section is to complete Proposition 7 in order to prove a stronger and more complete undecidability result summarised in the following theorem. Theorem 1 For any dimension strictly greater than 1, we have the following: each of the classes Equ , Sens and N is neither recursively enumerable nor corecursively enumerable; any pair of them is recursively inseparable. Proof The proof of this theorem is made of 3 similar parts: each one gives the inseparability of two classes A and B among Sens , Equ and N , as well as the non enumerability of A and the non co-enumerability of B . The propositions focus on 2D cellular automata but, by Proposition 1, results remain true for higher dimensions (because the canonical lift from some CA F to F is recursive). The 3 parts are proved in the following way: A = Sens and B = Equ : this is Proposition 7 (our construction G gives an alternative proof by Bergers theorem). A = N and B = Sens : this follows by Bergers theorem [1] (the set of tile sets which can tile the plane is not recursively enumerable) and Proposition 4 since F can be recursively constructed from . A = Equ and B = N : again since the set of tile sets that can tile the plane is not recursively enumerable, this follows by Proposition 6. Besides complexity of decision problems, other differences appears between dimension 1 and higher dimensions. Let us rst stress the dynamical consequence of the construction of CA F . It is well-known that for any 1D sensitive CA of radius r , 22r is always the maximal admissible sensitivity constant (see for instance [10]). Thanks to the above construction it is easy to construct CA with tiny sensitivity constants as shown by the following proposition. Proposition 8 The (maximal admissible) sensitivity constant of sensitive 2D CA cannot be recursively (lower-)bounded in the number of states and the neighbourhood size. Proof This follows directly from Proposition 4 since the size n of the largest n n valid tiling for a given tile set is not a recursive function of the tile set. To nish this section, we will discuss another difference between 1D and 2D concerning the complexity of equicontinuous points. Let us rst recall that equicontinuous point in 1D CA can be generated by nite words often called blocking words. A nite word u is blocking for some CA F if for any pair of congurations x and y

708

Theory Comput Syst (2011) 48: 693714

both having pattern u in their center, we have:1 t 0, z : z

F t (x)(z) = F t (y)(z)

where r is the radius of F . For any F with equicontinuous points, there exists a nite word u such that u is an equicontinuous point for F (proof in [10]). The construction G can be used with the tile set of Myers [11] which can produce only non-recursive tilings of the plane. Therefore the situation is more complex in 2D, and we have the following proposition. Proposition 9 For any dimension strictly greater than 1, there exists a CA having equicontinuous points, but only non-recursive ones. Proof By Proposition 5, any equicontinuous point of G is made solely of solid states and its component forms a valid tiling. Now consider the tile set 0 of Myers [11]: it can tile the plane but only with non-recursive tilings. Therefore, by Proposition 5, G0 admits equicontinuous points, but only non recursive ones. Remark 1 Since the construction G enforces the apparition of a particular state () in any equicontinuous point, we could have proved Proposition 9 using the simpler tile set of Hanf [7], which produces only non-recursive tilings provided some xed tile is placed at the origin. Any 1D CA with equicontinuous points, admits in fact uncountably many equicontinuous points. Indeed, if u is a blocking word and if c is any bi-innite sequence of 0 or 1, then the conguration: c(n) u c(1) u c(0) u c(n) is always an equicontinuous point. The next proposition shows that it is no longer the case for higher dimensional CA. Proposition 10 For any dimension strictly greater than 1, there exists a CA having a countably innite set of equicontinuous points. Proof Let 0 be a trivial tile set (a single tile and no constraint). By Proposition 5, G0 admits equicontinuous points which are all identical on their tiling component. Moreover, it follows from denition of G,0 that if two equicontinuous points have the state in the same position, then they are identical. Thus G0 possesses only a countable set of equicontinuous points and the proposition follows for dimension 2.
1 To simplify the denition, we require that the blocking word xes the 2r + 1 central columns of the space-time diagrams of any conguration having u in its center. In fact 2r columns would be enough (and it is the standard denition) but it doesnt change anything for our purpose since with our denition of blocking word, we still have the property that a 1D CA admits equicontinuous points if and only if it has a blocking word.

Theory Comput Syst (2011) 48: 693714

709

For dimension 3 we will use a lifted version G+ of G0 : G+ is essentially a canonical lift of G0 with the additional condition that 2 cells whose coordinates differ by 1 only on the third dimension must be in the same state, otherwise they turn into state 0 whatever the 2D dynamics of G0 says. By a straightforward adaptation of the reasoning of Proposition 5 we have the following: for any equicontinuous point of G+ , the set of occurrences of states is exactly a line co-linear to the third dimension. Therefore, by the same reasoning as above, we deduce that G+ has only a countable set of equicontinuous points. The lift arguments can be iterated and thus the proposition follows for any dimension.

6 Complexity of Sensitivity According to Dimension In this section, we study the complexity of the set of Sens from the point of view of the arithmetical hierarchy. More precisely, we establish an upper bound in the 1D case and a lower bound in the 3D case showing that the complexity of Sens does vary with dimension.
0. Proposition 11 For 1D cellular automata, the set Sens is 2

Proof As said above, a 1D CA is sensitive if and only if it does not possess any blocking word [10]. Let F be a CA of radius r . Following the denition of blocking words given in Sect. 5, the fact that F possesses a blocking word can be expressed as follows: ut R(u, t)

where R(u, t) is true if and only if for all t t and all pair of congurations x and y having u in their center, we have: z : z

F t (x)(z) = F t (y)(z).

R(u, t) is recursive since the checking involve only a nite part of the initial conguration (precisely the 2r(t + 1) central cells). Hence, the set Sens is characterised by 0 predicate ut R(u, t). the 2 We will now give a hardness result for the set Sens in dimension 3. We will reduce the set of Turing machines halting on a co-nite set of inputs, to Sens thus 0 -hard (see [12] for the proof of 0 -completeness of COFIN ). proving that Sens is 3 3 We will use simulations of Turing machines by tile sets in the classical way (originally suggested by Wang [14]): the tiling represents the space-time diagram of the computation and the transition rule of the Turing machine are converted into tiling constraints. For technical reasons which will appear clearly in the proof of Lemma 6, we slow down the computation (what can be done by a recursive modication of the machine): the head takes 2 time steps to move 1 cell left or right. Moreover, the tile sets we consider always contain some blank tile (corresponding to a blank tape
COFIN ,

710

Theory Comput Syst (2011) 48: 693714

symbol of the Turing machine) and some special tile used to initiate the computation, but no tile corresponding to a nal state of the Turing machine. More precisely, each tile set enforces the following: if some row contains , it is of the form w where w is a sequence of nonblank symbols which will be treated as input (at this point we can not enforce by tiling constraint that w is nite); the tile on the right of must represent the Turing head in its initial state reading the rst letter of the input. Thus, each time a valid tiling contains , we are guaranteed that it contains a valid non-halting computation starting on some (potentially innite) input. The i th Turing machine in a standard enumeration is denoted by Mi and to each Mi we associate a tile set i whose constraints ensure the simulation of Mi as mentioned above, and which contains the special tiles i and i as described above. We now describe the construction, for any Turing machine Mi , of a cellular automaton Ii which is sensitive to initial conditions if and only if Mi COFIN . It will essentially consist in a lift to dimension 3 of a modied version of Gi . We rst describe this modied version, denoted G i , which is a 2D CA. The intuition is the following: we want that any equicontinuous point of G i contains a valid non-halting computation of Mi starting from a nite input. More precisely, we will dene G i in such a way that any equicontinuous point has a valid i -tiling on some of its components, which contains an occurrence of the special state i , and which contains only a nite sequence of non blank symbols on the right of i . The denition of G i differ from that of Gi only by the denition of the subshift G,i : for G i this subshift becomes i dened as follows. A conguration x is in i exactly when: x G,i ; i is the only tile allowed in the tiling component of a state having its X component equal to ; a solid state having a tile different from i in its tiling component is not allowed to be on the immediate left of a liquid state. G i is built upon i exactly as Gi is built upon G,i . Precisely, any cell of G i behave like this: 1. if the neighbourhood (5 5 cells) forms a pattern forbidden in i , then the state is left unchanged except in the following cases where it turns into state 0: if the cell is in a liquid state; if the inside region of the cell forms a forbidden pattern, the cell together with one of its neighbour forms a forbidden pattern 2. else, apply (if possible) one of the transition rules depending only on the 3 3 neighbourhood detailed in Fig. 2 (replacing S by Ri ); 3. in any other case, leave the state unchanged if it is solid and turn into 0 if it is liquid. From this denition and the result already established for Gi we easily get the following lemma.

Theory Comput Syst (2011) 48: 693714

711

Lemma 6 G i is sensitive to initial conditions if Mi halts on any input. Moreover, if Mi doesnt halt on all inputs, then G i admits equicontinuous points and each equicontinuous point veries the following: its tiling component forms a valid tiling for i ; it contains exactly one occurrence of the special tile i ; there is a nite sequence w of consecutive non-blank symbols on the right of i , therefore the tiling component simulates a valid non-halting computation of Mi starting on a nite input w . Proof The modications introduced in G i (compared to Gi ) concern only new cases in which a solid state is turned into 0. Therefore, all necessary conditions about equicontinuous points of Gi (Proposition 5) apply here. Besides, if Mi possesses a non-halting input, it is easy to construct an equicontinuous point x which contains a valid space-time diagram of a non-halting computation. The fact that the computation is slow ensures that we can nd arbitrarily large squares centered on the tile i (and the state ) without any non-blank on the right boundary of the square. With such precautions, the conservative erosion apply here exactly as in the proof of Proposition 5. Finally, since the denition of G i implies that occurrences of coincide with occurrences of i , the lemma follows from the following property: if a conguration x of G i contains a cell having an innite sequence of non-blank symbols on its right, then it is not an equicontinuous point. This property follows from the denition of i since, for any nite conguration sufciently close to x , the non-blank symbols allow liquid states to inltrate towards a xed position (after some time) and therefore the usual technique of particle inltration shows that x cannot be an equicontinuous point. The 3-dimensional cellular automaton Ii The idea is that on each horizontal plane Pc = {(a, b, c) : a, b Z2 } of the space, Ii generally behaves like G i . However, Ii contains an additional 3D mechanism, whose role is to ensure that the non-halting simulations done on successive planes start from different inputs of Mi . Ii contains an additional component of states, called Z , that can take 3 values +, and = (the state set of Ii is Qi Z where Qi is the state set of G i ). To describe the local constraints on Z , we use notations South(), North(), East(), West() to describe relation between positions in the same horizontal plane, and Top() and Bot() for the 3rd dimension: if the Z -component of a cell z Z3 is = then it is also the case for cells East(z), West(z), Top(z) and Bot(z); if the Z -component of a cell z Z3 is + then it is also the case for cells East(z), West(z) and Top(z), whereas North(z) and South(z) must have a Z -component equal to =; if the Z -component of a cell z Z3 is then it is also the case for cells East(z), West(z) and Bot(z), whereas North(z) and South(z) must have a Z -component equal to =;

712

Theory Comput Syst (2011) 48: 693714

Fig. 6 Two planar (simplied) views of a valid solid conguration

if the tiling component of a cell z (in a solid state) is i then its Z -component must be either + or ; moreover Top(z) and Bot(z) must also be in a solid state with a tiling component equal to i ; if a cell z in a solid state has its Z -component equal to + and its tiling component is i , then, if West(Bot(z)) has also its Z -component equal to + and is also solid, it must have its tiling component also equal to i ; if a cell z in a solid state has its Z -component equal to and its tiling component is i , then, if West(Top(z)) has also its Z -component equal to + and is also solid, it must have its tiling component also equal to i . The global result of those local conditions is illustrated by the following lemma. Lemma 7 Let x be a purely solid conguration of Ii such that, each horizontal plane contains one occurrence of i and a valid tiling, and all the previous local conditions are veried. Then x has the following form: on each plane, all Z components are = except on an east/west line which contains i ; all the occurrences of i are aligned in a top/bottom column; the space is made of a top half corresponding to planes Pc having some state with Z -component + and a bottom half corresponding to planes Pc having some state with Z -component ; if a plane Pc is in the top half and simulates Mi on an input of length n, then for any a > 0, the plane Pc+a simulates Mi on an input of length strictly greater than n; similarly for the bottom half, the input length is strictly greater for plane Pca than for plane Pc . Proof Straightforward. Ii is then dened as follows: if one of the previous local conditions is violated in the neighbourhood of a cell in a solid state surrounded only by cells in a solid state, then the cell turns into state (0, =), else it behaves according to G i depending only on cells in the same plane.
0 -hard. Proposition 12 For dimension 3, the set Sens is 3

Theory Comput Syst (2011) 48: 693714

713

Proof We show that Ii is sensitive to initial conditions if and only if Mi admits an innite set of non-halting inputs, which yields a reduction from COFIN to Sens . First, it is easy to see that if Mi has an innite set of non-halting inputs, then an equicontinuous point for Ii can be build: given an innite sequence of non-halting inputs of different lengths, one can build a purely solid conguration, made of two halves, each one corresponding to the sequence of valid simulations on each plane for successive inputs, and respecting all the conditions on the Z component. It is straightforward to check that such a conguration is an equicontinuous point. Conversely, if x is an equicontinuous point for Ii then each plane Pc must be an equicontinuous point for G i when we forget the Z component. Indeed, the additional 3D conditions of Ii never affect liquid states and can only turn a solid state into state 0. Now, adding 3D constraints, we deduce by Lemmas 6 and 7 that Mi must have an innite set of non-halting inputs. 7 Future Work In this paper, we adopted the classical framework of topological dynamics (which does not explicitly refer to dimension) and studied how its application to cellular automata may vary with dimension. The rst research direction opened by this paper is the study of new dynamical behaviour appearing in dimension 2 and more. Indeed, the mechanisms of information propagation can no longer be explained by the presence of particular nite words (blocking words in dimension 1). In this general direction, the following questions seems particularly relevant to us: what kind of dynamics can be found in the class N ? what kind of 2D cellular automata can be built which are in Equ and have a set of equicontinuous points of full measure? can we characterise such CA? what happens when we restrict to reversible cellular automata? more generally to surjective ones? The second part of the paper concerns complexity of decision problems related to topological dynamics properties. Our construction techniques allow to prove several complexity lower bounds. However, upper bounds seems harder to establish. We think the following questions are worth being investigated: what is the exact complexity of Sens in 1D? is it 2 -complete or only at level 1 of the arithmetical hierarchy? we believe that the set Sens is in the arithmetical hierarchy for any dimension, but we have no proof yet starting from dimension 2. can we generally implement Turing-jumps in the complexity of the problem we consider when we increase dimension? or is there limitation coming from the nature of the problem? Finally, the various kind of sensitivity to dimension change we encountered, suggest to consider those problems from of more general point of view by allowing the lattice of cells to be any Cayley graph. Can we then characterise graphs for which Sens and Equ are complementary classes? What can be said on the complexity of the different classes of topological dynamics?

714

Theory Comput Syst (2011) 48: 693714

References
1. Berger, R.: The undecidability of the domino problem. Mem. Am. Math Soc. 66 (1966) 2. Bernardi, V., Durand, B., Formenti, E., Kari, J.: A new dimension sensitive property for cellular automata. In: Fiala, J., Koubek, V., Kratochvl, J. (eds.) Mathematical Foundations of Computer Science 2004. Lecture Notes in Computer Science, vol. 3153, pp. 416426. Springer, Berlin (2004) 3. Blanchard, F., Maass, A.: Dynamical properties of expansive one-sided cellular automata. Isr. J. Math. 99 (1997) 4. Blanchard, F., Tisseur, P.: Some properties of cellular automata with equicontinuity points. Ann. Inst. Henri Poincar, Prob. Stat. 36, 569582 (2000) 5. Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classication for cellular automata. In: Morvan, M., Rmila, . (eds.) DMCS03. DMTCS Proceedings, vol. AB, pp. 117128 (2003) 6. Fagnani, F., Margara, L.: Expansivity, permutivity, and chaos for cellular automata. Theory Comput. Syst. 31(6), 663677 (1998) 7. Hanf, W.: Nonrecursive tilings of the plane. I. J. Symb. Log. 39(2), 283285 (1966) 8. Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 3(4), 320375 (1969) 9. Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48(1), 149182 (1994) 10. K urka, P.: Languages, equicontinuity and attractors in cellular automata. Ergod. Theory Dyn. Syst. 17, 417433 (1997) 11. Myers, D.: Nonrecursive tilings of the plane. II. J. Symb. Log. 39(2), 286294 (1966) 12. Rogers, H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1967) 13. Sablik, M., Theyssier, G.: Topological dynamics of 2d cellular automata. In: CiE, pp. 523532 (2008) 14. Wang, H.: Proving theorems by pattern recognition II. Bell Syst. Tech. J. 40(2) (1961)

Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.