Entropies and dimensions [in cellular automata]

There are 2ⁿ sequences possible for n cells that are each either black or white. But as we have seen, in most cellular automata not all these sequences can occur except in the initial conditions. The number of sequences s_n of length n that can actually occur is given by

Apply[Plus, Flatten[MatrixPower[m, n]]]

where the adjacency matrix m is given by

MapAt[(1 + #) &, Table[0, {Length[net]}, {Length[net]}], Flatten[MapIndexed[{First[#2], Last[#1]} &, net, {2}], 1]]

For rule 32, for example, s_n turns out to be Fibonacci[n + 3], so that for large n it is approximately GoldenRatioⁿ. For any rule, s_n for large n will behave like κⁿ, where κ is the largest eigenvalue of m. For rule 126 after 1 step, the characteristic polynomial for m is x³ - 2 x² + x - 1, giving κ ≃ 1.755. After 2 steps, the polynomial is

x¹³ - 4 x¹² + 6 x¹¹ - 5 x¹⁰ + 3 x⁹ - 3 x⁸ + 5 x⁷ - 3 x⁶ - x⁵ + 4 x⁴ - 2 x³ + x² - x + 1

giving κ ≃ 1.732. Note that κ is always an algebraic number—or strictly a so-called Perron number, obtained from a polynomial with leading coefficient 1. (Note that any possible Perron number can be obtained for example from some finite complement language.)

It is often convenient to fit s_n for large n to the form 2^{h n}, where h is the so-called spatial (topological) entropy (see page 1084), given by Log[2, κ]. The value of this for successive t never increases; for the first 3 steps in rule 126 it is for example approximately 1, 0.811, 0.793. The exact value of h after more steps tends to be very difficult to find, and indeed the question of whether its limiting value after infinitely many steps satisfies a given bound—say even being nonzero—is in general undecidable (see page 1138).

If one associates with each possible sequence of length n a number Sum[a_i 2^-i, {i, n}], then the set of sequences that actually occur at a given step form a Cantor set (see note below), whose Hausdorff dimension turns out to be exactly h.