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 h_{tx} 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, h_{t}tx <= 2 λ h_{x} and h <= 2 r h_{t}. 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 h_{tx} = 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 h_{tx}. 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 h_{tx}. 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.