First some background for those not yet in the know about
celluar automata, they're a mathematical system for constructing graphs of cells. A
cell is
the smallest element of the graph, like a
pixel is of an
image. Cells can have only
two values, ON (M in my illustration) or OFF (space). The
graphing process starts at the top row and progresses row by row downward. At each row you start at the left and move to the right, determining the state
of each cell in that row in turn. You make the determination based on the states of the three neighboring cells from the previous row.
The first row has to be seeded to start the process going, (usually the middle cell of the row is turned ON, or the entire row is randomized).
Here is a diagram of physical correlation of the input and output cells:
X X X
Y
X represents an input cell, and Y represents an output cell. The "rule" determines what set of inputs corresponds to what set of outputs.
Here is Rule 30's correspondence of input to output:
1 indicates an ON cell, 0 indicates an OFF cell.
111 110 101 100 011 010 001 000
--- --- --- --- --- --- --- ---
0 0 0 1 1 1 1 0
The rule number comes from collecting the set of outputs as a binary number, and then converting it to decimal. As I have shown in the previous diagram,
rule 30 is 00011110. If you convert 00011110 to decimal, you get 30. The rule has to have an output for every different set of inputs. Since there are 3
binary inputs to this rule, there are 8 possible input cases. So the rule has to have 8 bits to describe the output for each of those cases, one for each.
With only 3 input cells, this only amounts to 256 possible rules. But with 4 and 5, there are a huge amount. These concepts are more thoroughly explained at
cellular automaton,
one-dimensional cellular automaton, and
Wolfram's classes of cellular automata, and with a greater mathematical bias.
So without further adieu, here's rule 30 in all its glory, one of the 256 3bit rules. If you look at the large white gaps, they form
triangles, which are
common in
CA. This
CA is valued for its chaotic nature (on the columns) and therefore has applications in
random number generation. Besides mathematical value, they're very interesting to look at (preferably in
pixels, not
ascii). I seeded it with
one set cell in the middle of the first row. The number in the left column indicates the iteration count.
00 M
MMM
MM M
MM MMMM
MM M M
05 MM MMMM MMM
MM M M M
MM MMMM MMMMMM
MM M MMM M
MM MMMM MM M MMM
10 MM M M MMMM MM M
MM MMMM MM M M MMMM
MM M MMM MM MM M M
MM MMMM MM MMM MMM MM MMM
MM M M MMM M MMM M M
15 MM MMMM MM M M MMMMM MMMMMMM
MM M MMM MMMM M MMM M
MM MMMM MM MMM MM MM M MMM
MM M M MMM M MM MMM MMMM MM M
MM MMMM MM M MMMMMM M M MMM MMMM
20 MM M MMM MMMM MMMM MMM MM M M
MM MMMM MM MMM M MM M M M MMM MMM
MM M M MMM M MMM MM M MMM MM M M M M
MM MMMM MM M MMM M M MMMM M M MM MMMMMM
MM M MMM MMMM MM MMMMM M MMMMM M M M
25 MM MMMM MM MMM M MM M M MM M MMMMM MMM
MM M M MMM M MM M MMMM MM M MM MM M MM M
MM MMMM MM M MMM M M M MMM MMMM M MM M MM M MMMM
MM M MMM MMMM MMMM MM MM MMM M M MMMM M M M
MM MMMM MM MMM M MM M M MMM M MM MMMM MMM MM MMM
30 MM M M MMM M MM M M MMMMM M MMMMMM M M MM M M M
MM MMMM MM M MMM M M MMMM MMMM MMMM MM M M MMMMMMMMM
MM M MMM MMMM MMMM M M MM M MM M M M M M
MM MMMM MM MMM M MM MM MMM MM M MMM MM M MMMMM M MM MMM
MM M M MMM M MM M M MM M M M M M MMMM M M M MM M
35 MM MMMM MM M MMM M M MMMM MMMM MMMMM MM MMMMM M MM M MM MM MMMM