Notes

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, , -1, -}, (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]