Posted to the NKS Forum January 18, 2004
Read Forum Thread

I was recently reminded of a type of cellular automaton that I think might allow some interesting analysis.

On page 886 of the NKS book, I discuss cellular automata in which the colors of cells are viewed as being elements of a finite group, and the new color of each cell is given by

a[t, i] = f[a[t-1, i-1], a[t-1, i]]

where f is the group multiplication operation.

With multiplication table m, one gets after t steps:

NestList[Extract[m, Partition[#, 2, 1, {-1, 1}, 1]] & init, t]

Here element 1 is taken to be the identity in the group, and at each step one pads on both sides with this.

If the initial conditions consist just of a single element {h}, then the pattern one gets is always nested, and in fact is just Pascal’s triangle modulo the order of h. And what’s going on is that the system is effectively just restricted to operating in a cyclic subgroup of whatever the original group was.

But what happens if the initial conditions involve two elements {h1, h2}?

If {h1, h2} generate an Abelian subgroup, then the system will correspond to an additive rule, and one will again get a nested pattern.

To get something non-Abelian, the whole group must be non-Abelian.

The smallest non-Abelian group is S3—the symmetric group on 3 elements.

One can take the elements to be Permutations[Range[3]], or

{{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.

Then the multiplication table for the group is

Outer[Position[elems, #1[[#2]]][[1, 1]] & elems, elems, 1]

or in this case

{{1,2,3,4,5,6},{2,1,5,6,3,4},{3,4,1,2,6,5},{4,3,6,5,1,2},
{5,6,2,1,4,3},{6,5,4,3,2,1}}

Initial conditions like {1,5} or {2,3} then generate Abelian subgroups, and give nested patterns.

But some initial conditions do not generate Abelian subgroups. In the book, I show what happens with {5, 6}.

It’s the same story, for example, with {2, 4}.

One gets a complicated and seemingly random pattern. (See the attachment.)

But the question is: is there computational reducibility in this pattern? Can one use ideas from group theory or anywhere else to shortcut the computation of a given element?

I don’t see how to do it. Though there is one tantalizing clue.

If one ignores (or grays out) all elements except 2, 3 and 6, then one gets just the pattern in greens, yellows and blues. And this is a pattern whose outline is just a simple nested rule 60 pattern.

But still its innards are complicated. Can anyone see a general approach that allows one to work out even these?

By the way, here’s a slightly general evolution function, relevant for permutation groups:

PGCAEvolveList[perms_,init_,t_]:=
  With[{m=Function[g,Outer[Position[g,#1[[#2]]][[1,1]]&g,g,1]][perms]},
    NestList[Extract[m,Partition[#,2,1,{-1,1},1]]&init,t]]

SymmetricPermutations[n_]:=Permutations[Range[n]]

AlternatingPermutations[n_]:=
  Select[Permutations[Range[n]],Signature[#]==1&]