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.

(49 lines omitted)

Snapshot 1: The 160 binary bits needed to represent all 32-digit sequences of a , rule space can be collapsed to just a 27-digit sequence.
Snapshot 2: The 1215 base-3 digits of a , rule space can be collapsed to just 238 digits.
Snapshot 3: The 5120 base-4 digits of a , rule space can be collapsed to just 1019 digits.
Snapshot 4: On the border of intelligibility, these 3129 digits were formatted trivially using Mathematica's new Pane graphics.
Use the slider to convince yourself that all the digit sequences from 0 to are represented in these patterns. Other digit sequences can be explored with Mathematica's DeBruijnSequence function from the Combinatorica add-on package. In general, the length of a de Bruijn sequence for a -digit alphabet with -length subsequences is simply . These sequences are not unique, but rather have permutations.
comments
 
Powered by Wolfram Mathematica
Give us your feedback
Give us your feedback

Source page:




 often  occasionally  never

Note: Please do not include anything you consider confidential or proprietary. Your message and contact information may be shared with the author of any specific Demonstration for which you give feedback, but will not otherwise be published or distributed.
Privacy Policy »

Note: To run this Demonstration you need the free
Mathematica Player
or Mathematica 7+
Download or upgrade to Mathematica Player 7
I already have Mathematica Player or Mathematica 7+