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[Log[k, s[t, x]]/t , t  ∞], x  ∞]

and a measure spacetime entropy h^μ_tx by replacing s with p Log[p]. In general, h_t ≤ h_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.