Cellular automaton rules as formulas

The value a[t, i] for a cell on step t at position i in any of the cellular automata in this chapter can be obtained from the definition

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

Different rules correspond to different choices of the function f. For example, rule 90 on page 25 corresponds to

f[1, _, 1] = 0; f[0, _, 1] = 1; f[1, _, 0] =1; f[0, _, 0] = 0

One can specify initial conditions for example by

a[0, 0] = 1; a[0, _] = 0

(the cell on step 0 at position 0 has value 1, but all other cells on that step have value 0). Then just asking for a[4, 0] one will immediately get the value after 4 steps of the cell at position 0. (For efficiency, the main definition should in practice be given as

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

so that all intermediate values which are computed are automatically stored.)

The definition of the function f for rule 90 that we gave above is essentially just a look-up table. But it is also possible to define this function in an algebraic way

f[p_, q_, r_] := Mod[p + r, 2]

Algebraic definitions can also be given for other rules:

• Rule 254 (page 24): 1 - (1 - p)(1 - q)(1 - r)

• Rule 250 (page 25): p + r - p r

• Rule 30 (page 27): Mod[p + q + r + q r, 2]

• Rule 110 (page 32): Mod[(1 + p) q r + q + r, 2]

In these definitions, we represent the values of cells by the numbers 1 or 0. If values +1 and -1 are used instead, different formulas are obtained; rule 90, for example, corresponds to p r. It is also possible to represent values of cells as True and False. And in this case cellular automaton rules become logic expressions:

• Rule 254: Or[p, q, r]

• Rule 250: Or[p, r]

• Rule 90: Xor[p, r]

• Rule 30: Xor[p, Or[q, r]]

• Rule 110: Xor[Or[p, q], And[p, q, r]]

(Note that Not[p] corresponds to 1 - p, And[p, q] to p q, Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2].)

Given either the algebraic or logical form of a cellular automaton rule, it is possible at least in principle to generate symbolic formulas for the results of cellular automaton evolution. Thus, for example, one can use initial conditions

a[0, -1] = p; a[0, 0] = q; a[0, 1] = r; a[0, _] = 0

to generate a formula for the value of a cell that holds for any choice of values for the three initial center cells. In practice, however, most such formulas rapidly become very complicated, as discussed on page 618.