Chapter 3: The World of Simple Programs

Section 2: More Cellular Automata

[Cellular automaton] rules based on algebraic systems

If the values of cells are taken to be elements of some finite algebraic system, then one can set up a cellular automaton with rule

a[t_, i_] := f[a[t-1,i-1], a[t-1,i]]

where f is the analog of multiplication for the system (see also page 1094). The pattern obtained after t steps is then given by

NestList[f[RotateRight[#], #]&, init, t]

The pictures below show results with f being Times, and cells having values (a) {1,-1}, (b) the unit complex numbers {1,I,-1,-I}, (c) the unit quaternions.

[Cellular automaton] rules based on algebraic systems image 1

In general, with n elements f can be specified by an n × n "multiplication table". For n=2, the patterns obtained are at most nested. Pictures (a) and (b) below however correspond to the n=3 multiplication tables {{1,1,3},{3,3,2},{2,2,1}} and {{3,1,3},{1,3,1},{3,1,2}}. Note that for (b) the table is symmetric, corresponding to a commutative multiplication operation.

If f is associative (flat), so that f[f[i,j],k]==f[i,f[j,k]], then the algebraic system is known as a semigroup. (See also page 805.) With a single cell seed, no pattern more complicated than nested can be obtained in such a system. And with any seed, it appears to require a semigroup with at least six elements to obtain a more complicated pattern.

If f has an identity element, so that f[1,i]==i for all i, and has inverses, so that f[i,j]==1 for some j, then the system is a group. (See page 945.) If the group is Abelian, so that f[i,j]==f[j,i], then only nested patterns are ever produced (see page 955). But it turns out that the very simplest possible non-Abelian group yields the pattern in (c) above. The group used is S3, which has six elements and multiplication table

{{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}}

The initial condition contains {5,6} surrounded by 1's.

From Stephen Wolfram: A New Kind of Science [citation]