My attempt at explaining cellular automata. Aimed at someone who has no real knowledge of how CAs work.
If you look at some online definitions of CAs you will see explanations like this and this. You can try and understand them, but probably be still left confused.
1D Cellular Automata
OK, let’s start at the simplest form of cellular automata, the one dimensional cellular automata.
A one dimensional CA consists of a line of row of cells. Each cell can be alive (on) or dead (off).
The first row of the image above is how this cellular automaton begins. It has 1 single centered alive (black) cell surrounded by dead (white) cells.
1D CA Rules
Cellular automata change states and evolve based on simple rules. The rules apply to every cell in the CA at the same time each step.
For the above image, the rules are as follows;
This shows the 8 possible rules for this CA. Each new cell state depends on itself and it’s 2 neighbors in the previous state.
The first rule (with the 3 black squares above a single white square) means that if the current cell and its two neighbors are black that cell will become a white cell the next step of the CA.
The second rule means that if a cell and its left neighbor are black but its right neighbor is white, the cell will be white in the next step.
The rest of the 6 rules are the same principal and cover all possible combinations of white and black cells.
You apply these rules to every cell in the CA each step. Here is a nice animation courtesy of Wikipedia showing how the rules are applied to a row of cells and the next step of the CA resulting from the rules.
Once the rules have been applied to all the cells, that step is completed. For 1D CA the easiest way to display them is to show each of the steps under the last in a 2D grid. The first 15 steps are shown in the grid above.
1D CA Rule Numbers
Looking again at the rule for this CA
you will notice that there are a series of 1’s and 0’s under the rules. 0 for if the rule creates a dead (white) cell and 1 if the rule creates an alive (black) cell. This series of 1’s and 0’s can be converted into a binary string that can then be converted into a number. For 8 digit binary numbers the numbers will range from 0 (for 00000000) to 255 (for 11111111).
These 1D CA’s have 256 possible combinations of rules. Rule 30 (shown above) is the conversion of 00011110 binary into digital 30. Being able to refer to each rule as a single number makes it easier to state which rule you are talking about.
More steps
If you follow the above rule repeatedly for more steps it evolves like this
From such simple rules some interesting structures arise within in. This specific rule has been used to generate random numbers (you can keep track of the center pixel going down the image and use it to create random numbers). You can see more info about Rule 30 here.
So what about the other 255 1D CA rules?
You can see the results of all 256 rules here.
An interesting result is rule 22.
Rule 22 results in a structure of triangles within triangles. This is a famous fractal pattern called the Sierpinski Triangle and it tends to pop up all over the place in cellular automata and fractals.
The End – for now
Hopefully by now you have a basic understanding of cellular automata. The main points to know are;
1. CAs are based on a grid of cells that are alive or dead.
2. The CA runs/updates/steps by running a set of rules on all the cells at the same time.
3. The same rules are then applied to the new cells and the process repeats itself.
The one dimensional cellular automata are kind of bland and once you seen the possible 256 rules there isn’t much excitement, but understanding 1D first makes the transition into higher dimensions and more complex rules easier to grasp.
If you want to experiment with these 1D CAs yourself, you can download Visions of Chaos. Open the 1D CA mode dialog and suddenly the options should be more clear to you now.
There is even an option that takes the CA steps and maps them into music. You can also print a catalog of all the 256 rules with more details.
If any of the above is not clear, please comment and let me know.
Jason.
Softology's Blog 