A Catalog of Cellular Automata

By

Jaime Rangel-Mondragón
jrangel@sunserver.uaq.mx

Copyright © December 2000, UAQ, Facultad de Informática

Permission is hereby granted to reproduce part or all of this file for any purpose other than direct profit providing that the source is acknowledged.

Acknowledgements

This work was initiated at Wolfram Research Inc., in Champaign IL, USA, while the author was spending two months as a Visiting Scholar. Their assistance and enthusiastic support is gratefully acknowledged. My thanks are also given for the continuous support received from the University of Queretaro in Mexico, where this work found completion.

"What a relief, to be away from straight lines," a thin man said.

"Um, how so?" Hari said, trying to seem interested.

"Well, of course straight lines don´t exist in nature. They have to be 
put there by humans." He sighed, "I love to be free of straightness!"

Hari instantly thought of pine needles; strata of metamorphic rock; 
the inside edge of a half-moon; spider-woven silk strands; 
the line along the top of a breaking ocean wave; crystal patterns; 
white quartz lines on granite slabs; the far horizon of a vast calm lake; 
the legs of birds; spikes of cactus; the arrow dive of a raptor; 
trunks of young, fast-growing trees; 
wisps of high windblown clouds; ice cracks; 
the two sides of the V of migrating birds; icicles.
"Not so," he said, but no more.

Foundation´s Fear
G. Benford

Cellular automata (CA) comprise rules encapsulating mechanisms of evolution that model highly complex behavior.  Systematic interest in CA has received considerable impetus from the continuous work of Stephen Wolfram since 1983 (who undertook a computer-based search on the properties of one-dimensional CA) up to the worldwide interest on his upcoming book "A New Kind of  Science" [1].

A one-dimensional CA processes in parallel the simultaneous change of state of each individual cell forming a collection arranged in a line. These individual changes are performed in accordance to the states of each one of their neighbors including itself through the application of a local transition rule. It is remarkable the fact that from such a simple mechanism we are able to generate a behavior of profoundly intrincate complexity, all this in contrast to the general impression that effects are always preceded by causes of at least comparable complexity.

In this work we assume only two possible states and the allotted set of states to be Range[0, b-1], where b varies from 2 to 4 calling such CA dyadic, triadic and tetradic respectively. This work comprises the  generation and display of catalogs of families of these CA covering irreducible, totalistic and reversible ones. The following results were obtained after several weeks of computationally-intensive sessions.

CA rules are described by lists:

rule1 = {0, 1, 0, 1, 1, 1, 1, 1};

We interpret this rule as describing a transformation from the set (({0,  1} )^(3 ))to the set {0,1}

Thread[
      Map[StringJoin[ToString   /@  IntegerDigits[#, 2, 3]] &, 
          Range[0, 7]] -> rule1]

That is, a rule of the form axb -> y describes the new value y of a given cell, given its present value x and those of its two neighbors a and b. In the case of dyadic CA, there are (2^((2^3)))=256 possible rules. It is possible to prove that linear CA do not need to have large neighborhoods; in fact, as Albert and Culick showed [2], it is sufficient to have just two cells in a neighborhood.

In drawing the evolution of  CA we indicate state 0 as a white square and a 1 as a black one appearing in a two-dimensional evolution  diagram. Function evolve takes the initial global state of the cellular space cS, along with a rule and the number of steps n of evolution and produces the matrix corresponding to the time diagram of the evolution of the corresponding CA. Note that we keep the end sites of cS quiescent, which might otherwise produce boundary distortions if a rule attempts to activate them; further, function showCA  generates a graphic object corresponding to a selected portion of this matrix to be displayed afterwards.

cellularSpace[n_] := 
      ReplacePart[Table[0, {n}], 
        1, ⌈n/
            2⌉]

evolve[b_, cS_, rule_, gen_] := 
      Module[{t}, 
t = 
          Thread[IntegerDigits[Range[0, (b^3) - 1], b, 3] -> rule];  
        NestList[Join[{0}, Partition[#, 3, 1]   /. t, {0}] &, cS, 
          gen]]

showCA[b_, cS_, rule_, gen_, fromRow_, fromCol_, toCol_, label_:  1] := 
      Module[{e, index}, 
e = 
          Take[evolve[b, cS, rule, gen], {fromRow, 
              gen}];  
e = Take[#, {fromCol, 
                  toCol}] &   /@  e;  
index = 
          StringJoin[
            Which[label == 0, "", label == 1,  
              ToString   /@  rule, label == 2, 
              ToString[
                FromDigits[rule, b]]]]; 
ListDensityPlot[
          Reverse[-e] , FrameTicks -> None, Frame -> False, 
          Mesh -> False, AspectRatio -> Automatic, 
          DisplayFunction -> Identity, 
          PlotLabel -> index]]

Note that the length of the cellular space is chosen to be an odd number so that the final pattern has central symmetry. Wolfram rule number set out the possible sequences of cells in reverse lexicographic order. So our rule 01101000=104 corresponds to Wolfram´s rule 00010110=22.

n = 31;
Show[
        showCA[2, cellularSpace[n], rule1, ⌊n/2⌋, 1, 
          1, n], DisplayFunction -> $DisplayFunction];

rule2 = {0, 1, 0, 1, 1, 0, 1, 0};
n = 61;
Show[
        showCA[2, cellularSpace[n], rule2, ⌊n/2⌋, 1, 
          1, n], DisplayFunction -> $DisplayFunction];

The following one is, in Wolfram´s classification, rule number 105. Note we have to extend the cellular space so that the spurious behavior at the ends does not reach the one produced by the  initial seed.

rule3 = 
        Reverse[IntegerDigits[105, 2, 8]];
n = 201;
Show[
        showCA[2, cellularSpace[n], rule3, ⌊n/4⌋, 
          1, ⌊n/4⌋, n - ⌊n/4⌋], 
        DisplayFunction -> $DisplayFunction];

rule4 = {0, 1, 1, 0, 1, 0, 1, 0};
Show[
        showCA[2, cellularSpace[n], rule4, ⌊n/4⌋, 
          1, ⌊n/4⌋, n - ⌊n/4⌋], 
        DisplayFunction -> $DisplayFunction];

A close up on the previous CA displays a remarkable degree of complexity.

Show[showCA[2, cellularSpace[1001], rule4, 400, 100, 400, 600], 
        DisplayFunction -> $DisplayFunction];

The following comprises our first catalog of all possible dyadic CA:

b = 2;
allRules = 
        IntegerDigits[Range[0, (b^((b^3))) - 1], b, 
          (b^3)];
g = 
        Map[showCA[b, cellularSpace[161], #, 40, 1, 40, 120, 2] &, 
          allRules];
Show[GraphicsArray[Partition[g, 8]], 
        DisplayFunction -> $DisplayFunction];

Rule 95 above corresponds to the OR operation. Rule 5 to the AND, rule 90 to the XOR. Rule 240 to the left NOT and rule 170 to the right NOT.
We mention as a side comment other representations of predicates generated by the author based on the work at [3]. For instance, the following are representations of the function XOR

In generating CA, we have to select those rules such that {0,0,1},{0,1,0},{1,0,0} are not all assigned to 0 or we will not get the automata started. We also need to have at least two of them equal to 1 and at least one of the others equal to 1 or we won´t proliferate. Also,{0,0,0}->0 (quiescent CA) is prefered to avoid the boundary effect and, in doing so, we might miss some interesting behavior as CA number 125 previously showed.
When is a rule equivalent to another? Two rules are equivalent if they include symmetric elements, that is, they are obtained from each other by the transformation 2⟷5, 4⟷7. They correspond to mutual reflections. This can be shortly described by a permutation. For dyadic CA we have that

other[r_] := 
      r[[{1, 5, 3, 7, 2, 6, 4, 
          8}]]

that is, the elements 2nd and 5th are permuted and also elements 4th and 7th. More generally, for arbitrary b we have:

symm[b_] := 1 + FromDigits[Reverse[#], b] &  /@  
        IntegerDigits[Range[0, (b^3) - 1], b, 3]

symm[2]

symm[3]

symm[4]

reflect[b_, r_] := 
      r[[symm[b]]]

reflect[2, Range[8]]

There are 68 out of 256 non-anihilable rules quiescent, proliferating, minimal rules.

b = 2;
allRules = 
        Select[IntegerDigits[Range[0, (b^((b^3) - 1)) - 1], b, 
            (b^3)], #[[{b, 1 + b, 
                  1 + (b^2)}]] ≠ {0, 0, 
                0} &];
s = symm[b];
allRules = 
        Select[allRules, 
          FromDigits[#] ≤ 
              FromDigits[#[[
                  s]]] &];
g = 
        Map[showCA[b, cellularSpace[161], #, 40, 1, 40, 120, 2] &, 
          allRules];
Show[GraphicsArray[Partition[g, 4]], 
        DisplayFunction -> $DisplayFunction];

THE RULE 01001000

Despite their simplicity of description, CA defy analysis except in the simplest of cases. For example, while we can easily prove that the rule 01001000 never produces three consecutive 1´s (proof:  a 1 must have been a 0 in the previous generation. So 111 must came from a 000 previous configuration, but this implies that the middle 0 has to stay 0 #. ) This rule also produces no 11 and between two consecutive 1 there are an odd number of 0´s;  but this facts are not so easy to prove.

The sequence of number of 1´s at each generation starts as:

cS = cellularSpace[321];
m = 
        evolve[2, cS, {0, 1, 0, 0, 1, 0, 0, 0}, 
          80];
(Plus  @@ #) &  /@  m

ListPlot[%, PlotJoined -> True, PlotRange -> All, 
        AspectRatio -> Automatic];

We generate this sequence by writing down 1 and proceeding duplicating the numbers starting from the beginning of the sequence until reaching the last one generated at the previous stage and starting again the whole process from the beginning. Denoting this sequence by u we have that u((2^n))=(2^n). Given n writen in binary, let m be the number obtained by removing n´s first digit 1. Then u(n)=2u(m), u((2^n))=(2^n). For instance, we can compute u(70) through considering the succession 1000110, 110, 10, u(70)=2 u(6)=4 u(2)=8. In other words, given the binary representation of n given as X1(0^k) (ends in k zeroes), then u(n)=\(TraditionalForm\`2\^\(number\ of\ 1  ´s\ in\ X + k\)\)

u[n_] := 
      v[IntegerDigits[n, 2]]

v[{x___, 1, y___}] := 
      (2^(Plus  @@  {x} + Length[{y}]))  /;  
        Plus  @@  {y} == 0

Table[u[n], {n, 30}]

IRREDUCIBLE CA

We can monitor all rules used so far and eliminate those that are not actually used to obtain the equivalent canonical rule generating the CA. The question of how many generations to go through in order to be able to be sure no other rules will be used is still unknown and we choose 40 steps in the following.

b = 2;
cS = cellularSpace[161];
allRules = 
        Select[IntegerDigits[Range[0, (b^((b^3) - 1)) - 1], b, 
            (b^3)], #[[{b, 1 + b, 
                  1 + (b^2)}]] ≠ {0, 0, 
                0} &];
s = symm[b];
allRules = 
        Select[allRules, 
          FromDigits[#] ≤ 
              FromDigits[#[[
                  s]]] &];

ans = {};
Map[
(r = #; 
m = 
              evolve[b, cS, r, 40]; 
pat = 
              IntegerDigits[
                Complement[Range[(b^3)], Flatten[Position[r, 0]]] - 1, b, 
                3]; 
p = 
              Union[Flatten[
                  Map[(j = Partition[#, 3, 1];  
                        Select[j, MemberQ[pat, #] &]) &, m], 
                  1]]; 
If[p == pat, 
              ans = Flatten[{ans, {r}}, 1]]) &, 
        allRules];

allRules = ans;
g = 
        Map[showCA[b, cS, #, 40, 1, 40, 120, 2] &, 
          allRules];
AppendTo[g, Graphics[{}]];
Show[GraphicsArray[Partition[g, 4]], 
        DisplayFunction -> $DisplayFunction];

We include these definitions on file allRules2. 

Unfortunately, this approach cannot be readily extended to the case b=3. In fact, if we change the definition of b to b=3 in the above, we obtain range overflow errors that prevent us to proceed with an otherwise possible (although unfeasible) computation.

TOTALISTIC RULES

A totalistic rule is one for which the transition depends upon the sum of the states of the neighborhood. Every neighborhood possessing a given sum must necessarily evolve into the same state.

Although totalistic rules form a special class, they are general enough to be representative in the sense that any other rule can be transformed into a totalistic rule, although the new rule may have a considerably larger number of states. Albert and Cullick [2] have demonstrated this fact.

f[li_, val_] := Map[(# -> val) &, li]

totalistic[b_] := 
      Module[{u, v, w, x}, 
u = 
          IntegerDigits[Range[0, (b^3) - 1], b, 3]; 
v = 
          Table[{}, {3 b - 2}]; 
Map[
          AppendTo[
              v[[1 + 
                  Plus  @@  #]], #] &, 
          u]; 
w = 
          IntegerDigits[Range[(b^(3 b - 4)), (b^(3  b - 3)) - 1], b, 
            3  b - 2]; 
x = 
          Map[Flatten[Inner[f, v, #, List]] &, 
            w]; 
Map[(u  /.  #) &, x]]

There are 196608 totalistic tetradic rules

b = 4;
u = 
        IntegerDigits[Range[0, (b^3) - 1], b, 3];
v = Table[{}, {3 b - 2}];
Map[
        AppendTo[
            v[[1 + 
                Plus  @@  #]], #] &, 
        u];
w = 
        IntegerDigits[Range[(b^(3 b - 4)), (b^(3  b - 3)) - 1], b, 
          3  b - 2];
Length[w]

There are only three corresponding to dyadic CA:

b = 2;
cS = cellularSpace[101];
ans = {};
s = symm[b];
allRules = 
        totalistic[b];

Map[
(r = #; 
m = 
              evolve[b, cS, r, 50]; 
pat = 
              IntegerDigits[
                Complement[Range[(b^3)], Flatten[Position[r, 0]]] - 1, b, 
                3]; 
p = 
              Union[Flatten[
                  Map[(j = Partition[#, 3, 1];  
                        Select[j, MemberQ[pat, #] &]) &, m], 
                  1]]; 
If[p == pat, 
              ans = Flatten[{ans, {r}}, 1]]) &, 
        allRules];

allRules = ans;
g = 
        Map[showCA[b, cS, #, 50, 1, 1, 101, 2] &, 
          allRules];
Show[GraphicsArray[g], 
        DisplayFunction -> $DisplayFunction];

We include the data for these rules in file totallistic2

The following comprises a catalog for the first 50 evolutions of all 99 irreducible triadic totalistic CA

b = 3;
cS = cellularSpace[101];
ans = profile = {};
s = symm[b];
allRules = 
        totalistic[b];

Map[
(r = #; 
m = 
              evolve[b, cS, r, 50]; 
pat = 
              IntegerDigits[
                Complement[Range[(b^3)], Flatten[Position[r, 0]]] - 1, b, 
                3]; 
p = 
              Union[Flatten[
                  Map[(j = Partition[#, 3, 1];  
                        Select[j, MemberQ[pat, #] &]) &, m], 
                  1]]; 
profile = 
              Flatten[{profile, {Length[ans]}}, 1]; 
If[
              p == pat, ans = Flatten[{ans, {r}}, 1]]) &, 
        allRules];

allRules = ans;
g = 
        Map[showCA[b, cS, #, 50, 1, 1, 101, 2] &, 
          allRules];
AppendTo[g, Graphics[{}]];
Show[GraphicsArray[Partition[g, 5]], 
        DisplayFunction -> $DisplayFunction];

We include the data for these rules in file totallistic3.

In searching through the data corresponding to the totalistic ones we obtained the following profile.

ListPlot[profile];

Any one of the previous CA can be singled out for processing:

r = IntegerDigits[2201243097206, 3, 27];
Show[showCA[3, cellularSpace[301], r, 150, 1, 1, 301, 0], 
        DisplayFunction -> $DisplayFunction];

A CATALOG OF IRREDUCIBLE TOTALISTIC TETRADIC CA

Of the (4^((4^3))) = 340282366920938463463374607431768211456 tetradic rules, only 196608 are totalistic, which prompt us to attack the problem of generating all irreducible totalistic ones. They turned out to be 21523 and are stored in file totalistic4, a sample of which follows.

b = 4;
cS = cellularSpace[101];
allRules = << totalistic4;
g = 
        Map[showCA[b, cS, #, 50, 1, 1, 101, 0] &, 
          Take[allRules, {100, 20000, 100}]];
Show[GraphicsArray[Partition[g, 5]], 
        DisplayFunction -> $DisplayFunction];

REVERSIBLE AUTOMATA

A pattern having no predecessor under a given rule is called a Garden-of-Eden pattern [4]. Once it is attained, it is never entered into again in all future generations. One of the basic questions on CA concerns the reversibility of the global rule. In the following, we select all reversible dyadic CA up to generation 50:

ancestor[_, {}, _] := {}
ancestor[b_, cS_, r_] := 
      Module[{t, ri, i, le, q}, 
t = 
          Map[Flatten[Position[r, #]] &, 
            cS]; 
t[[1]] = t[[-1]] = {1};  
Do[
ri = Take[
                  IntegerDigits[# - 1, b, 3], -2] &  /@  
              t[[i - 
                  1]]; 
t[[i]] = 
            Select[t[[i]], 
              MemberQ[ri, 
                  Take[IntegerDigits[# - 1, b, 3], 
                    2]] &], 
{i, 2, 
            Length[t] - 
              1}];  
Do[
le = Take[
                  IntegerDigits[# - 1, b, 3], 2] &  /@  
              t[[i + 
                  1]]; 
t[[i]] = 
            Select[t[[i]], 
              MemberQ[le, Take[IntegerDigits[# - 1, b, 3], -2]] &], {i, 
            Length[t] - 1, 2, -1}];  
t = 
          Map[IntegerDigits[# - 1, b, 
                  3][[2]] &, 
            t, {2}]; 
t = Union[#] &  /@  
            t; 
q = 
          And  @@  ((Length[#] == 1) &  /@  
                t); 
If[q, 
          Flatten[t], {0}]]

reversibleQ[b_, cS_, r_, gen_] := 
      Module[{t = 
            Nest[Flatten[ancestor[b, #, r]] &, cS, 
              gen]}, 
((Plus  @@  t) == 
            1)]

allRules = << allRules2;
b = 2;
gen = 50;
cS = cellularSpace[110];
r = 
        Select[allRules, 
(v = 
                evolve[b, cS, #, gen]; 
reversibleQ[b, 
                Last[v], #, gen]) &];
g = 
        Map[showCA[b, cS, #, gen, 1, 1, 110, 2] &, 
          r];
Show[GraphicsArray[Partition[g, 1]], 
        DisplayFunction -> $DisplayFunction];

These CA are included in file reversible2.

As the generations (step) grow, we can see the number of those that are reversible up to that point.

allRules = << allRules2;
b = 2;
cS = cellularSpace[110];
aR = Table[1, {51}];
aR[[1]] = 
        allRules;
Do[
aR[[
            gen + 1]] = 
          Select[aR[[
              gen]], 
(v = 
                  evolve[b, cS, #, gen]; 
reversibleQ[b, 
                  Last[v], #, gen]) &], {gen, 
          50}];
Length[#] &  /@  aR

For triadic CA, however, the following list eliminates all after the 16th generation.

allRules = << totalistic3;
b = 3;
cS = cellularSpace[50];
aR = Table[1, {17}];
aR[[1]] = 
        allRules;
Do[
aR[[
            gen + 1]] = 
          Select[aR[[
              gen]], 
(v = 
                  evolve[b, cS, #, gen]; 
reversibleQ[b, 
                  Last[v], #, gen]) &], {gen, 
          16}];
Length[#] &  /@  aR

And the only one keeping its reversibility condition for as long as possible up to the 15th generation is:

gen = 15;
aR = 
        Select[allRules, 
(v = 
                evolve[b, cS, #, gen]; 
reversibleQ[b, 
                Last[v], #, gen]) &];
g = 
        Map[showCA[b, cS, #, gen, 1, 1, 43, 2] &, 
          aR];
Show[GraphicsArray[Partition[g, 1]], 
        DisplayFunction -> $DisplayFunction];

In the case of tetradic CA, the sequence starts as:

The last three reversible ones are the following:

The above results are stored in file reversible4.

2D-CA: THE ALL-ONES PROBLEM

Suppose that each one of the (n^2) squares forming a chessboard of size n x n can be made to be white or black by just touching it. Every time a square is touched, it changes its present color. Moreover, by touching a square we toggle not only the color of that one but all of the other four edge-adjacent squares as well. The All-Ones problem can be stated as follows: assuming that initially all squares are white, is it possible to choose a subset of squares in such a way that by touching all of them one at a time we are able to eventually set all squares to black? (we identify white with a 0 and black with a 1). In [4] it is shown that this problems has always a solution.
A one-dimensional version of this problem is furnished by rule

Map[
      StringJoin[ToString  /@  IntegerDigits[#, 2, 3], " -> ", 
          ToString  /@  IntegerDigits[7 - #, 2, 3]] &, 
      Range[0, 7]]

which, although not local, can be thought off as changing the state of the cellular space by a local change at a time. In general, the All-Ones problem can be rephrased as finding out whether a cellular space filled with 1´s is a Garden-of-Eden for a given value of n. In other words, whether the All-Ones state is reversible. 

The following comprises a table of the solutions corresponding to the All-Ones problem for chessboards of size n=2 through n=51. Black squares are the subset of squares sought, that is, the squares that, when touching them in any order, solve the problem.

ans = {};
Do[
A = 
          Table[0, {(n^2)}, {(n^2)}]; 
Do[
          i = 1 + ⌊((r - 1)/n)⌋; 
j = r - (i - 1) n; 
neigh = 
            Select[{{i, j - 1}, {i, j}, {i, j + 1}, {i - 1, j}, {i + 1, 
                  j}}, ((0 < First[#] ≤ n) && (0 < 
                        Last[#] ≤ 
                        n)) &]; 
(A[[r, #]] = 
                  1) &  /@  (((First[#] - 1) n + 
                      Last[#]) &  /@  neigh), {r, 
            (n^2)}]; 
X = 
          LinearSolve[A, Table[1, {(n^2)}], 
            Modulus -> 
              2]; 
sol = {i = 
                  1 + ⌊((# - 1)/n)⌋, # - (i - 1) 
                    n} &  /@  
            Flatten[Position[X, 1]]; 
B = 
          Table[0, {n}, {n}]; 
(B[[
                  First[#], Last[#]]] = 1) &  /@  
          sol; 
AppendTo[ans, 
          ListDensityPlot[Reverse[-B] , FrameTicks -> None, 
            Frame -> False, Mesh -> False, 
            AspectRatio -> Automatic, 
            DisplayFunction -> Identity]], {n, 2, 
          51}];
Show[GraphicsArray[Partition[ans, 5]]];

Note that a solution for the 6x6 grid is contained in the solution to the 8x8 grid. Note also that not all display central symmetry or even bilateral symmetry. As expected, some prime number order display this lack of symmetry but other behave in a uniform fashion. We include the data above in file allOnes4.

TOROIDAL DOMAINS

Consider the All-Ones problem on a toroidal boundary. Most of the solutions require touching all squares and are omitted from the graphical output but accounted for in the list allOnes below.

wrap[i_, n_] := 
      Which[i > n, 1, i < 1, n, True, i]

ans4 = {};
allOnes = {};
Do[
A = 
          Table[0, {(n^2)}, {(n^2)}]; 
Do[
          i = 1 + ⌊((r - 1)/n)⌋; 
j = r - (i - 1) n; 
neigh = {{i, wrap[j - 1, n]}, {i, 
                j}, {i, wrap[j + 1, n]}, {wrap[i - 1, n], 
                j}, {wrap[i + 1, n], 
                j}}; 
(A[[
                    r, #]] = 
                  1) &  /@  (((First[#] - 1) n + 
                      Last[#]) &  /@  neigh), {r, 
            (n^2)}]; 

X = 
          LinearSolve[A, Table[1, {(n^2)}], 
            Modulus -> 
              2]; 
sol = {i = 
                  1 + ⌊((# - 1)/n)⌋, # - (i - 1) 
                    n} &  /@  
            Flatten[Position[X, 1]]; 
B = 
          Table[0, {n}, {n}]; 
(B[[
                  First[#], Last[#]]] = 1) &  /@  
          sol; 
If[(Plus  @@  Flatten[B]) == 
            (n^2), AppendTo[allOnes, n], 
AppendTo[ans4, 
            ListDensityPlot[Reverse[-B] , FrameTicks -> None, 
              Frame -> False, Mesh -> False, 
              AspectRatio -> Automatic, 
              DisplayFunction -> Identity, 
              PlotLabel -> ToString[n]]]], {n, 2, 51}];
Length[ans4]
Show[GraphicsArray[Partition[ans4, 5]]];
allOnes

Note the case n=2 overlaps with itself and we have to make some assumptions as to its not simultaneously toggling the neighbors. The values of n not having a solution start as 5, 6, 10, 12, 15, 18, 20, 24, 25, 30,  at first we conjecture that they are equal to those numbers having only two different prime divisors but 28 contradicts it;  25 shows that they are more. 
If we do not include the cell we are toggling we would have that there exists a solution for n even and this solution is quite symmetrical, as the following table shows.

KNIGHTS DOMAINS

If instead of changing the neighbor squares when we touch a square we change those that are at a knight-move of distance, we obtain the following table:

We include the data above in file allOnes5.

TOROIDAL KNIGHT DOMAINS

We include the data above in file allOnes6. Note that the cases n=26 and n=44 have no solution.

Problem: what if we have more than one state , that is, if the first time we press a button it changes color cyclically to one of n available ones?.

POWERS OF INTEGERS

The behavior displayed by a CA also occurs in the representation of the powers of an integer in several bases. This is illustrated below by function pow[n, m, gen] which displays a density  plot of the first gen powers of n written in base m (More fascinating information on the behaviour can be consulted at [5])

pow[n_, m_, gen_] := 
      Module[{i, t, 
          l = Length[IntegerDigits[(n^gen), m]]}, 
t = 
          Table[IntegerDigits[(n^i), m, l], {i, 
              gen}]; 
ListDensityPlot[Reverse[-t] , 
          FrameTicks -> None, Frame -> False, Mesh -> False, 
          AspectRatio -> Automatic]]

pow[3, 2, 50];

pow[2, 3, 50];

pow[10, 7, 50];

pow[20, 11, 100];

REFERENCES

[1] http://www.stephenwolfram.com/

[2] A Simple Universal Cellular Automaton and its One-Way and Totalistic Version
A. Jurgen, K. Culik II
Complex Systems 1, 1-16 (1987)
      
[3] A Fractal Guide to Tic-Tac-Toe
I. Stewart
Scientific American 283, 86-88 (2000)
    
[4] Linear Cellular Automata and the Garden-of-Eden
K. Sutner
The Mathematical Intelligencer 11, 2 49-53 (1989)

[5] Partitions and Sums of Integer Powers
J. Rangel-Mondragon
http://www.mathsource.com/Content/WhatsNew/0211-307