Notes

Chapter 2: The Crucial Experiment

Section 1: How Do Simple Programs Behave?


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.


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