Transcription
Linear Cellular Automata andthe Garden-of-EdenK. Sutner1. The All-Ones ProblemSuppose each of the squares of an n x n chessboard isequipped with an indicator light and a button. If thebutton of a square is pressed, the light of that squarewill change from off to on and vice versa; the samehappens to the lights of all the edge-adjacent squares.Initially all lights are off. Now, consider the followingquestion: is it possible to press a sequence of buttonsin such a way that in the end all lights are on? We willrefer to this problem as the All-Ones Problem.A m o m e n t ' s reflection will show that pressing abutton twice has the same effect as not pressing it atall. Thus a solution to our problem can be described bya subset of all squares (namely a set of squares whosebuttons w h e n pressed in an arbitrary order will renderall lights on) rather than a sequence. In fact a set X ofsquares is a solution to the All-Ones Problem if andonly if for every square s the number of squares in Xadjacent to or equal to s is odd. Consequently, we willcall such a set an odd-parity cover.Trial and error in conjunction with a pad of graphpaper will readily produce solutions for n 4. A littlemore experimentation shows that an odd-parity cover- - s h o u l d one exist--is difficult to construct even for n 5or6.The brute-force approach to the problem, namelyexhaustive search over all subsets of {1. . . . n} x{1. . . . n}, presents 2n2 candidates, and the search becomes infeasible for moderate values of n even withthe help of a computer. A less brute-force methodwould be to try to solve the system(A I ) . X terpreted as a matrix over GF(2)) and 1 is the vectorwith all components equal to 1. This method, whichinvolves n 2 equations, again becomes unwieldy forsmall values of n. For a similar approach to a gamerelated to the All-Ones Problem, see [3]. In any case,Figure 1 shows odd-parity covers for n 4, 5, 8.Several questions come to mind. For which n does asolution to the All-Ones Problem exist? More generally, how m a n y odd-parity covers are there for an n xn board? What happens if the adjacency condition isc h a n g e d - - s a y , to an octal array (where a cell in thecenter has eight neighbors)? Can one replace an n x nrectangular grid by some other arrangement of sitesand still obtain a solution? To answer some of thesequestions, we first rephrase the problem in terms ofcellular automata.Iof linear equations over the field GF(2) {0,1}, whereA is the adjacency matrix of the n x n grid graph (inTHE MATHEMATICAL INTELLIGENCER VOL. 11, NO. 2 9 1989 Springer-Verlag New York49
2. Cellular Automata on GraphsA cellular automaton is a discrete dynamical system thatconsists of an a r r a n g e m e n t of basic c o m p o n e n t s calledcells together with a transition rule. Every cell can assume a finite n u m b e r of possible states; the collectionof possible states is called the alphabet of the automaton. We will here restrict our attention to the casewhere the set of possible states is {off, on}, which werepresent by {0,1}. The transition rule of a cellular automaton is local in the,sense that the state of cell x attime t 1 d e p e n d s only on the states of the neighboring cells (including cell x itself) at time t. Traditionally the cells are arranged on a finite or infinite, one- ort w o - d i m e n s i o n a l grid. With a view t o w a r d the AllOnes Problem, however, we will allow arbitrary adjacencies b e t w e e n the sites of our cellular automata.More precisely, let G be a locally finite graph, i.e., agraph such that every vertex v in G is adjacent to onlyfinitely m a n y vertices in G. Let V denote the set ofvertices of the graph G, and for any vertex v define theclosed neighborhood N v of v byN : { u E V I u adjacent to v } U {v}.le10I##I # I##0e010##00 #e #D#I#olo#O#oeleoJOlFigure 1. Solutions to the All-Ones Problem for square gridsof size 4 x 4, 5 x 5, and 8 x 8. Note that a solution for the 6x 6 grid is contained in the center part of the 8 x 8 solution.A pattern of G is a functionX : V--* {0,1}from the collection of all vertices V to the alphabet{0,1}. We let Cc denote the collection of all patterns ofG and identify a pattern X : V--- {0,1} with a subset ofthe vertex set V, namely the collection of all cells vwith X(v) 1.N o w let v be a vertex of G. A local pattern at v on Gis a functionX : N ---* {0,1}.Clearly, a n y pattern X : V-- {0,1} determines a localpattern X at v, for each vertex v, by settingXdu) : X(u)3millIIIInCIlmOc3mml(1)for all u in N . A local rule p associates every localpattern at v with a state: the state of cell v in the nextg e n e r a t i o n . G i v e n a c o l l e c t i o n of l o c a l r u l e s(pv : v E V) the c o r r e s p o n d i n g global rule p is obtained by applying the local rules s i m u l t a n e o u s l y - - o rin parallel, to use a m o d e r n t e r m - - t o all the local patterns:p : Cc Ccmetric difference of X and Y. The singletons {v}, v EV, provide a standard basis for Cc in the case of a finitegraph G. To keep notation simple we will write v instead of {v}, so that in particular if u # v, then v ustands for the pattern {u,v}. We will write 1 for the"All-Ones" pattern: l(v) 1 for all v in V. Similarly, 0denotes the e m p t y set as an element of Co. A n y pattern Z such that p(Z) X is called a predecessor of Xu n d e r the global rule p. A pattern that fails to have a n ypredecessors is frequently called a Garden-of-Eden:once "lost" it remains inaccessible forever; see [1], [2].To tackle our chessboard problem, define a globalrule (y b y d e f i n i n g a collection (yv of local rules asfollows:rrv(Xv) : card(Xv) m o d 2.In other words, (y(X)(v) 1 iff card(Xv) is odd. Ag r a p h t o g e t h e r w i t h rule or will be called a (y-automaton. The predecessors of 1 in a (y-automaton areexactly the solutions of the All-Ones Problem, whichcan n o w be restated as follows:Given an n x n grid graph G, is I a Garden-of-Edenunder rule (y in G? (X)(v) : .v(x )where X is defined by (1).Algebraically, the collection of all patterns forms avector space over {0,1} construed as the two-elementfield GF(2). This vector space will be called the patternspace. The vector s u m of X and Y in C c is the sym 0THE MATHEMATICALINTELLIGENCERVOL. 11, NO. 2, 1989Before we answer the above question, let us digressbriefly. The rule (y is a typical member of the class of"linear rules," which means that (y is linear as a m a pfrom the pattern space Ca to itself. In fact, (Y(X) (A /) 9 X, where pattern X is construed as a columnvector a n d the adjacency matrix A of G is construed as
."i,,.,.r ,.'.,.- .%.,',",,.,.-"-,,.,.I .,.," I-.,I ;-.,d::"., ,,,Table 1. Irreversible n x n grid automata, n 100.Here d, denotes the dimension of Kp.,.,(r.,:x.,,,. -'.,' ,. ,.".'.: .".,. .'.,.':.r",.,:."%. . . : : . . . . .:. ;,, ,r ., .,"-'. ,-" I-.,,.: I.-I ;.-; -',, .,'-';.,.,," ',,,.'I ;%,.," ".,,.,.";.,r ;,.,r .,,; ",, .-'. -'.,,,,,; :,, .,'. :,.,,p,, ,.: :.,,-',,,,r.,,,',,,,,: ,, ,,,,",',,., ,':.,,.,,,',,,. ".'.-".".-";.,":,, ,," ,.--" ,.;' . I,.r,'-"-'. ,. , ."-'."-'.".A'Lddd L-,'h,d L, d LL.a L.a L dL 1 L d ' L JhdLd L d l d Ld I Ld L', :1",- -,'1: :I',d' 'L.r 'Ld :1:::I'Ld 020.,. -'. ,d I,,d L dIbd LdLhd hld I - d IBFigure 2A. The first 70 steps in the evolution of pattern (0) inP with rule or-. B. The first 70 steps in the evolution ofpattern (0) in P with rule .a matrix over the field {0,1}. Another rule very closelyrelated to r is obtained by excluding the vertex v fromits o w n neighborhood: or-v(Xv) : card(X v - v) m o d2. Thus o'-(X) A 9 X. A n y rule p that is composed oflinear local rules Pv is called a linear rule.Despite the simplicity of linear rules like or a n d or-,the cellular automata obtained from t h e m s h o w quitecomplicated behavior. A classic example is the twosided infinite path graph P (the vertices of P are theintegers, and v is adjacent to u if a n d only if lu - v I 1). Figure 2 shows the evolution of the seed pattern {0}on P using various linear rules. The two-dimensionalpatterns generated in this fashion have non-integerfractal dimension a n d display such complicated geometric properties as self-similarity. The fractal dimension of the pattern asymptotically generated by rule oris log2(1 X/5), whereas rule or- generates a patternof dimension log23.A wealth of information about these and other cellular automata rules as well as m a n y fascinating pictures can be f o u n d in [5] through [8] (rules or a n d orare called rule 150 a n d 90, respectively, in [5]).3. F i n i t e ( r - A u t o m a t aO n e of the basic questions of the theory of cellular automata concerns the global reversibility of the transition rule: can pattern X be reconstructed from p(X)?4622016Locally irreversible s y s t e m s are i n t e r e s t i n g from at h e r m o d y n a m i c point of view: unlike locally reversiblesystems, t h e y m a y evolve from u n o r d e r e d to orderedstates. Linear rules are locally irreversible in the sensethat different patterns can lead to the same state inone particular cell in the next generation. Globallylinear rules m a y well be reversible, however.Let us a s s u m e from n o w on that G is a finite graph.For linear rules the situation is simple: rule p is injective if a n d only if it is surjective. Let Ka,p C CG be thekernel of rule p on G and set d(G,p) : dirn(KG, p) log2(card(Kc, p)). Then the a u t o m a t o n G with rule p isreversible if a n d only if it has no Garden-of-Eden ifa n d o n l y if d(G,p) 0. In particular, the All-OnesProblem can be solved in a n y finite reversible automaton. For rule or the 3 x 3 grid is an example for areversible automaton; indeed, all (2i - 1) x (2i - 1)square grids are reversible. A polyhedron gives rise toa graph that has the corners of the polyhedron as vertices a n d an edge joining two vertices if and only if anedge of the polyhedron joins the two correspondingcorners. Of the five graphs obtained in this fashionfrom the Platonic solids, only the octahedron is reversible; whereas the tetrahedron, the cube, the dodecahedron, a n d the icosahedron are irreversible. The d-dimensional hypercube 2d is the graph with vertex set{0,1}a a n d there is an edge between v and u if and onlyif v a n d u have H a m m i n g distance one (i.e., they disagree in exactly one component). The hypercube 2a isTHE MATHEMATICAL INTELLIGENCER VOL. 11, NO. 2, 1989 1
t o m a t o n Ps- Notice that Ps is irreversible but nonetheless pattern 1 has a predecessor. For arbitrary n, it iseasy to determine all odd-parity covers for P,:2 4 5 1 "" 1 2 2 4. . 4 5 3 2 3 49l O1 2 3 5 3 4 , 2 5 2 3--1 4 11 3 4 5/" 1 3 )r 1 3 42 3 4 5/ 2 51 5 1 2 4 5 3 4 5 --.92§Figure 3. The transition diagram GPs"reversible if and only if d is even; for a proof of theseresults see [4].Let us agree on some notation for graphs: Pm (Cm)will d e n o t e t h e p a t h (cycle) g r a p h o n m p o i n t s{1. . . . m} a n d Pm,, the rectangular m x n grid graph.Table 1 shows the dimension dn of Kp, n, for all irreversible n x n grid automata, n 1001 Note that dim e n s i o n appears to be even for any square grid (it isn o t even in general for rectangular grids). Observethat d2n l 2 " d, 8,, where 8, {0,2}. Indeed, thetable suggests 82, 1 8,. We are not aware of a prooffor a n y of these conjectures.N o w s u p p o s e p a t t e r n X has p r e d e c e s s o r Y. Bylinear algebra the collection of all predecessors of X isthe affine s u b s p a c e O-I(X) Y KG,p; t h u s then u m b e r of predecessors of X is either 0 or 2d(G,"). Thetable provides an explanation for the extra difficulty ofconstructing an odd-parity cover for the 5 x 5 or 6 x 6grid compared to the 4 x 4 grid: there are 16 solutionsfor 4 x 4 grid, 4 for the 5 x 5 grid, but only one forthe 6 x 6 grid. O n e can s h o w that in the 4 x 4 boardone can pick an arbitrary pattern in the first row andalways expand it to an odd-parity cover of the wholegrid.The predecessor relation is best expressed graphically by m e a n s of the transition diagram Go, p of G.Formally C,p is a directed graph that has as verticesthe patterns of G a n d an edge from X to Y if a n d only if,(X) Y. For a linear rule p the in-degree of everypoint in GG,pis either 0 or 2d(G,p). The out-degree is 1, ofcourse, so the connected components of G,p are allunicyclic. I n d e e d , t h e y consist of one cycle a n d an u m b e r of 2d(c,P)-ary trees a n c h o r e d on that cycle.Clearly, rule p is reversible on G if a n d only if the conn e c t e d c o m p o n e n t s of G,p are cycles. The orbit{ I i I 0} of a n y pattern X forms a one-generatedmonoid.Figure 3 shows the transition diagram for the or-au52THE MATHEMATICALINTELLIGENCER VOL. 11, NO. 2, 1989nn 0(mod3)n l(mod3)n 2(mod3)2 51 41 4and2 odd-parity covers. . (n - 4) (n - 1)7 . . (n - 3) n7 . . ( n - 4) (n - 1)5 8 . . ( n - 3) n.The corresponding pictures m a y be more convincingt h a n algebra; see Figure 4.So Pn is reversible if and only if n 2 (mod 3). For n 2 (mod 3) there exists exactly one predecessor of 0(other t h a n 0 itself), namely I 2 4 5 . . (n- 1) n; thus d(Pn,or) 1. Similarly, for the cycle Cnone has the following situation:nn 0(mod3)n 0(mod3)odd-parity covers11 , 1 4 . . (n - 2),2 5 . .( n - 1),3 6 . . n.Thus 1 is a fixed point u n d e r or in C, and d(C,,,or) 2for n 0 (mod 3).F i n d i n g o d d - p a r i t y covers for each of the laddergraphs Pn,2, n / 2 is still straightforward. For evenlarger grids the search becomes hopeless, as patientreaders m a y readily convince themselves. It is n o tclear that an odd-parity cover should exist for arbitrarygrids.As we have seen, reversibility is a sufficient but byno m e a n s necessary condition for 1 to have a predecessor. Indeed, we will s h o w that an arbitrary finiteg r a p h G possesses an o d d - p a r i t y cover, or, equivalently, the All-Ones Problem has a solution. We do notk n o w of a n y purely geometric (read: graph theoretic)a r g u m e n t to prove this. We will present an algebraicproof.* To this end let v 1. . . . v n be the standard baseof the pattern space Ca a n d let C*c be the dual spaceequipped with the dual base Vl*. . . . vn*. Every vectorX - i V i in Ca gives rise to a linear functional X* : E ivi* in C'G; define(z,x): x (z).C G is finite dimensional and therefore isomorphic toC*c u n d e r the m a p X X*; we will identify b o t hspaces to keep notation manageable. Z is said to beperpendicular to X, in symbols Z 3 X, if (Z,X) 0.Hence Z a n d X are perpendicular if and only if theirintersection has even cardinality. Z is perpendicular toa subspace W of C a if and only if Z 3 X for all X E W.Define the orthogonal c o m p l e m e n t W" of the subspace W by W {Z E CG [ Z 3 W}. Using the notionof orthogonal complement one can n o w characterize* R. TindeUpointed out that there is a purely graph theoretic prooffor trees (connected acyclicgraphs). See pages 31-32.
I lel I I# I lel I .,-IIolllelliellllelllelllolll. , ,I lolllelllel I I01 II llell]oiI lolllolllell.-I IIolllelFigure 4. Odd-parity covers for P,.Figure 5. A basis for K ,.,.the patterns that lie in the range of or.3.1 THEOREM: Let G be an arbitrary finite graph and letp be one of the rules or or cr-. Then pattern X has a predecessor in G under rule p if and only if X is perpendicular tothe kernel of p.Proof: The n e i g h b o r h o o d (and adjacency) matrix of agraph is symmetric. Thus p is selfadjoint and p(x),Y x,p(Y) .for a n y two patterns, X,Y. Also note that ( . , .) is nondegenerate in the sense thatX Oiff(Z,X) O f o r a l l Z i n C c.N o w let W be the range of p. We getY E W rrrfor all X in C c (p(X),Y) 0for all X in Cc (X,p(Y)) 0p(Y) 0,i.e., W Ka,,. By a well-known theorem of algebraW " W. Hence W Ka, p" and the proof is complete. 93.2 THEOREM: The All-Ones Problem has a solution inany finite graph.Proof: The key observation is that any pattern X suchthat or(X) 0 m u s t have even cardinality. To see this,first note that every vertex x in X has o d d degree in thes u b g r a p h G w i t h vertex set X. Second, recall theh a n d s h a k i n g t h e o r e m : the n u m b e r of o d d - d e g r e epoints in a n y finite graph is even. Now, (X,1) is thecardinality of X m o d u l o 2, so (X,1) 0. Hence 1 isp e r p e n d i c u l a r to Kc,,,, a n d has a predecessor u n d e rrule or by Theorem 3.1. 9Thus I fails to be a Garden-of-Eden u n d e r rule or ina n y finite graph. We note in passing that Theorem 3.2can be generalized to locally finite graphs. For finitegraphs one can c o m p u t e a basis for the affine subspaceof all odd-parity covers in polynomial time, i.e., in an u m b e r of steps polynomial in the n u m b e r of points ofthe graph. Surprisingly, the problem of determiningan odd-parity cover of minimal cardinality turns out tobe computationally difficult: the corresponding optimization problem is NP-hard; see [4]. Thus it is unlikely that a n y efficient (read: deterministic polynomialtime) algorithm exists to construct an odd-parity coverof minimal size for a given graph.For certain simple graphs like P4,4, where the kernelof or is k n o w n explicitly, T h e o r e m 3.1 provides aneasy test of w h e t h e r a given pattern has a predecessor.Figure 5 s h o w s a basis for the kernel of o- on P4,4. It iseasy to check that no singleton can have a predecessor. Or consider the path ion, where n - 2 (mod 3)and n 2. Then in Pn exactly the patterns of the formX X0 U X 1 , w h e r e X 0 i s a s u b s e t o f l 2 4 5 . . (n - 1) n of even cardinality a n d X1 is asubset of 3 6 . . (n - 2), have a predecessoru n d e r rule or. Hence exactly half the patterns have apredecessor, a n d the other half are Gardens-of-Eden.References1. E. F. Moore, Machine models of self-reproduction, in:A. W. Burks, Essays on Cellular Automata, University ofl]linois Press, 1970.2. J. Myhill, The converse of Moore's Garden-of-EdenTheorem, in: A. W. Burks, Essays on Cellular Automata,University of Illinois Press, 1970.3. D. H. Pelletier, Merlin's magic square, Amer. Math.Monthly 94 (1987), 145-130.4. K. Sutner, Linear automata on graphs, to appear.5. S. Wolfram, Statistical mechanics and cellular automata,Rev. Modern Physics 55 (1983), 601-644.6. S. Wolfram, Computation theory of cellular automata,Comm. Math. Physics 96 (1984), 15-57.7. S. Wolfram, Geometry of binomial coefficients, Amer.Math. Monthly 91 (1984), 566-571.8. S. Wolfram, Computer software in science and mathematics, Scientific American 251 (1984), 188-203.Department of Computer ScienceStevens Institute of TechnologyHoboken, NJ 07030 USATHE MATHEMATICALINTELLIGENCERVOL. 11, NO. 2, 1989 5 3
THE MATHEMATICAL INTELLIGENCER VOL. 11, NO. 2 9 1989 Springer-Verlag New York 49 . 2. Cellular Automata on Graphs A cellular automaton is a discrete dynamical system that consists of an arran
