Cellular Automata

May 15, 2009

A cellular automaton is a collection of cells arranged in an infinite grid, controlled by a clock, with each cell coloring itself at each tick of the clock based on the state of its neighboring cells. A linear cellular automaton has all the cells of the grid arranged in a single line. A time-lapse picture of a linear cellular automaton shows a two-dimensional grid with the automaton as a horizontal line, the state of the automaton at each clock tick flowing down the page.

For the elementary cellular automata that we will study, each cell may be either of two colors, black or white, and a cell’s neighborhood consists of itself and the two cells on either side. With two colors and three neighbors, there are 23=8 states and 28=256 possible rules for advancing from one state to the next.

Rules are specified using a kind of binary notation; for each of the eight states 111, 110, 101, 100, 011, 010, 001, and 000, where 1 is black and 0 is white and the neighbors are arranged left-to-right on the line. Then the rule is specified by the binary number corresponding to the eight successor states of each of the eight neighbors, so for instance rule 30 = 000111102 maps 111 to 0, 110 to 0, 101 to 0, 100 to 1, 011 to 1, 010 to 1, 001 to 1, and 000 to 0.

For example, the first 12 rows of the rule 158 automaton applied to a row containing a single black cell are shown below:

                        X
                      X X X
                    X X X   X
                  X X X     X X
                X X X   X X X   X
              X X X     X X     X X
            X X X   X X X   X X X   X
          X X X     X X     X X     X X
        X X X   X X X   X X X   X X X   X
      X X X     X X     X X     X X     X X
    X X X   X X X   X X X   X X X   X X X   X
  X X X     X X     X X     X X     X X     X X
X X X   X X X   X X X   X X X   X X X   X X X   X

You can see more examples at http://mathworld.wolfram.com/ElementaryCellularAutomaton.html.

Your task is to write a function that draws the result of applying a given rule to a given number of rows, starting from a row with a single black cell. When you are finished, you are welcome to read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
9 Comments »