De Bruijn Sequences Provide Compact Initial Conditions

A de Bruijn sequence is the shortest sequence of numbers from a given alphabet that contains all possible subsequences of length . As such, it becomes the perfect initial condition for a cellular automaton (CA) where it is desirable to insure that all possible neighborhoods are explored.

For the elementary cellular automata, the alphabet is {0,1} and =3. The de Bruijn sequence is {00011101}. Since the initial condition is typically specified as surrounded by a sea of zeros, the initial condition can be specified as just the five digits (11101). This is a far cry from the 24 bits that you would think are required to specify the eight possible three-digit neighborhoods: 000, 001, 011, 111, 110, 101, 010, 100.

So, what are the similar bit patterns for CA rules with more than two colors and/or more than range=1 neighborhoods? Use the slider at the top to prove to yourself that every pattern from 0 to appears somewhere in the cleverly constructed de Bruijn digit sequence.