Nonlinear feedback shift registers
Linear feedback shift registers of the kind discussed on page 974 can be generalized to allow any function f (note the slight analogy with cyclic tag systems):
NLFSRStep[f_, taps_, list_] := Append[Rest[list], f[list〚taps〛]]
With the choice f=IntegerDigits[s, 2, 8]〚8 - # . {4, 2, 1}〛 & and taps = {1, 2, 3} this is essentially a rule s elementary cellular automaton. With a list of length n, Nest[NLFSRStep[f, taps, #] &, list, n] gives one step in the evolution of the cellular automaton in a register of width n, with a certain kind of spiral boundary condition. The case analogous to rule 30 yields some of the longest repetition periods—usually remarkably close to the absolute maximum of 2n - 1 (for n = 21 the result is 1999864, 95% of the maximum).
Nonlinear feedback shift registers were apparently studied in the context of military cryptography in the 1950s, but very little about them has made its way into the open literature (see page 878). An empirical investigation of repetition periods in such systems was made by Solomon Golomb in 1959. The main conclusion drawn from extensive data was that nothing like the linear theory applies. One set of computations concerned functions
f[{w_, x_, y_, z_}] := Mod[w + y + z + x y + x z + y z, 2]
(apparently chosen to have balance between 0's and 1's that would minimize correlations). Tap positions {1, 2, 3, 4} were among those studied, but nothing like the pictures below were apparently ever explicitly generated—and nearly three decades passed before I noticed the remarkable behavior of the rule 30 cellular automaton.
Sequences of states in any shift register must correspond to paths through a network of the kind shown on page 941. And as noted by Nicolaas de Bruijn in 1946 there are 22n - 1-n such paths with length 2n, and thus this number of functions f out of the 22n possible must yield sequences of maximal length. (For k colors, the number of paths is k!kn - 1/kn.)