[Cryptographic] properties of rule 30

Rule 30 can be written in the form p ⊻ (q ∨ r) (see page 869) and thus exhibits a kind of one-sided additivity on the left. This leads to some features that are desirable for cryptography (such as long repetition periods) and to some that are not (such as the sideways evolution of page 601). It implies that every block of length m that occurs at a particular step has exactly 4 immediate predecessor blocks of length m + 2 (see page 960). It also implies that all 2^t possible single columns of t cells can be generated from some initial condition. Not all 4^t pairs of adjacent columns can occur, however. There seems to be no simple characterization, say in terms of paths through networks, of which can, but for successive t the total numbers are

{4, 12, 32, 80, 200, 496, 1208, 2916, 6964, 16476, 38616, 89844, 207544, 476596, 1089000, 2477236, 5615036}

or roughly 2.25^t.

Given two complete adjacent columns page 601 shows how all columns any distance to the left can be found. It turns out that this can be done even if the right-hand one of the two adjacent columns is not complete. So for example whenever there is a black cell in the left column it is irrelevant what appears in the right column. Note that the configuration of relevant cells can be repetitive only if the initial conditions were repetitive (see page 871).

In a cellular automaton of limited size n, any column must eventually repeat. There could be 2ⁿ distinct possible columns; in practice, for successive n there are {2, 3, 7, 14, 30, 60, 101, 245, 497, 972, 1997, 3997}—within 2% of 2ⁿ already for n = 12. This means that for the initial conditions to be determined uniquely, the number of cells that must be given in a column is almost exactly n, as illustrated in the pictures below. Many distinct columns correspond to starting at different points on a single cycle of states. The length of the longest cycle grows roughly like 2^{0.63 n} (see page 260). The complete cycle structure is illustrated on page 962. Most of the 2ⁿ possible states have unique predecessors; for large n, about 2^{0.76 n} or Root[#³ - #² - 2 &, 1]ⁿ instead have 0 or 2 predecessors. The predecessors of a given state can be found from

Cases[Map[Fold[Prepend[#1, If[#2  1 ⊻, Take[#1, 2]  {0, 0}], 0, 1]] &, #, Reverse[list]] &, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}], {a_, b_, c___, a_, b_}  {b, c, a}]