Alternative rules [for cryptography]

Among elementary rules, rule 45 is the only plausible alternative to rule 30. It usually yields longer repetition periods (see page 260), but shows slightly slower responses to changes in the key. (Changes expand about 1.24 cells per step in rule 30, and about 1.17 in rule 45.) Rule 45 shares with rule 30 the property of one-sided additivity. With the occasional exception of the additive rule 60, elementary rules not equivalent to 30 or 45 tend to exhibit vastly shorter repetition periods. (The completely non-additive rule with largest typical repetition period is rule 110.) (See page 951.)

If one considers rules that depend on 4 rather than 3 cells, then the results turn out to be surprisingly similar: out of all 65536 possible such rules the ones with longest periods essentially always seem to be variants of rules 45, 30 or 60. In a region of size 15, for example, the longest period is 20460, and this is achieved by rule 13251, which is just rule 45 applied to the first three cells in the neighborhood. (Rule 45 itself has period 6820 in this case.) After a few rules with long periods, the periods obtained drop off rapidly. (In general the number of rules with a given period seems to decrease roughly exponentially with period.) For size 15, the 33 rules with the longest periods are all additive with respect to one position. The pictures below show the first rules that are not additive with respect to any position.

Among the 4,294,967,296 r = 2 rules which depend on 5 cells, there are again just a few that give long periods, but now only a small fraction of these seem directly related to rules 45 and 30, and perhaps half are not additive with respect to any position. The pictures below show the rules with longest periods for size 15; these same rules also yield the longest periods for many other sizes. The first two are additive with respect to one position, but do not appear to be directly related to rules 45 or 30; the last two are not additive with respect to any position. Formulas for the rules are respectively:

p ⊻ (¬ q ∨ r ∨ s ∧ ¬ t)

r ⊻ (¬ p ∨ q ∨ s ∧ ¬ t)

u = ¬ p ∧ ¬ q ∨ q ∧ t; ¬ r ∧ u ∨ q ∧ ¬ s ∧ (p ∨ ¬ r) ∨ r ∧ s ∧ ¬u

s ∧ (q ∧ ¬ r ∨ p ∧ ¬ q ∧ t) ∨ ¬ (s ∨ (p ∨ q) ∧ (r ⊻ (q ∨ t)))

Note that for size 15 the maximum possible period is 32730 (see page 950).