Entropies and dimensions [in cellular automata]

There are 2^{n} 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, Subscript[s, n] turns out to be Fibonacci[n+3], so that for large n it is approximately GoldenRatio^{n}. For any rule, Subscript[s, n] for large n will behave like κ^{n}, where κ is the largest eigenvalue of m. For rule 126 after 1 step, the characteristic polynomial for m is x^{3} - 2 x^{2} + x - 1, giving κ≃1.755. After 2 steps, the polynomial is

x^{13} - 4 x^{12} + 6 x^{11} - 5 x^{10} + 3 x^{9} - 3 x^{8} + 5 x^{7} - 3 x^{6} - x^{5} + 4 x^{4} - 2 x^{3} + x^{2} - 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.