Cellular Automata are simple agents that take a fixed number of binary inputs to generate a binary output.
You can think of them as simple lookup tables: The same inputs will generate the same output.
Cellular automata are usually shown on a grid. The most popular example is the Game of Life.
Imagine a grid that has black and white cells. You can see the black cell as 1 and the white cell as 0.
Now imagine the inputs of the cells to be the neighboring cells.
The setup i want to discuss here is like this:
We start out with a grid that has one black dot at the top.
The cellular automata move from the top downwards, taking the three neighboring cells above them as input, and leaving their output state on the grid (making the cells black or white).
We havew a whole bunch of cellular automata: One per column.
The automata will leave a structure on the grid.
One iteration can be presented like this:
Now let's look at a second iteration:
The lookup table of this automaton says to put black when the left or right neighbor is black, white otherwise.
It is clear that this lookup table will generate a regular pattern.
Now assume the lookup table generates black when one of the neighbors is black, but not both.
This lookup table generates a Sierpinski triangle.
In fact, depending on the lookup table, 4 different types of structures can emerge:
- repetitive patterns
- self containing patterns (like the Sierpinski triangle)
- more complicated fractal patterns
- structures that seem random
Every automaton itself is very simple.
But the interaction between identical automata yields complexity and self organization.