Chapter 6: Starting from Randomness

Section 7: The Notion of Attractors

Spacetime patches [in cellular automata]

One can imagine defining entropies and dimensions associated with regions of any shape in the spacetime history of a cellular automaton. As an example, one can consider patches that extend x cells across in space and t cells down in time. If the color of every cell in such a patch could be chosen independently then there would be k^(t x) possible configurations of the complete patch. But in fact, having just specified a block of length x + 2 r t in the initial conditions, the cellular automaton rule then uniquely determines the color of every cell in the patch, allowing a total of at most s[t,x] = k^(x + 2 r t) configurations. One can define a topological spacetime entropy htx as

Limit[Limit[1/t Log[k,s[t, x]] , t -> Infinity], x -> Infinity]

and a measure spacetime entropy hμtx by replacing s with p Log[p]. In general, ht <= htx <= 2 λ hx and h <= 2 r ht. For additive rules like rule 90 and rule 150 every possible configuration of the initial block leads to a different configuration for the patch, so that htx = 2r = 2. But for other rules many different configurations of the initial block can lead to the same configuration for the patch, yielding potentially much smaller values of htx. Just as for most other entropies, when a cellular automaton shows complicated behavior it tends to be difficult to find much more than upper bounds for htx. For rule 30, hμtx < 1.155, and there is some evidence that its true value may actually be 1. For rule 18 it appears that hμtx = 1, while for rule 22, hμtx < 0.915 and for rule 54 hμtx < 0.25.

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