9867

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.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+