Cellular Automata 2017-11-07
Overview of Cellular Automata
Cellular automata can use simple rules to produce very interesting patterns. First discovered in the 1940's, cellular automation (CA) has had a number of applications, including simulating some biological and chemical processes.
Cellular automata takes a grid of tiles which can be alive (on) or dead (off). In a two-dimensional CA, each tile in the grid has 8 total neighbors (shown in red) - 4 on each side and 4 in the corners. CA takes a set of rules and applies them, in what's called a generation. Also, to start there is an initial state of one or more cells that are alive.
Conway's Game of Life
Probably the most famous cellular automation is Conway's Game of Life. It has only 4 basic rules, listed below.
- Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overpopulation.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
From these simple rules, all kinds of cool things can come about, for example this "glider gun" shooting "gliders" (see Conway's Game of Life):
Similarities with the Universe
One thing I find particularly interesting is that along with biology and chemistry, CA may also have applications in physics. Particles like atoms behave in very consistent ways. In fact, they behave so consistently, that physicists have labeled their behavior as laws since they have never been observed to be broken. For instance the laws of thermodynamics or special relativity.
There are a lot of parallels between our physical reality and CA. Currently there are 22 physical constants, for example the speed of light. These could be the result of the rules set upon our universe. For instance, the speed of light could be like the maximum speed of 1 tile per generation. A glider could be like a photon moving at the speed of light.
Elementary Cellular Automata
Even simpler than 2-dimensional cellular automata like Conway's Game of Life, there are 1-dimensional CAs. These take a single row of tiles, each with 2 neighbors - one to the left and right. Each generation takes into account the current state of the tile along with its neighbors. For instance, if a tile was dead and so was the neighbor to the left, but the neighbor on the right was alive, it would be represented as 001. 0 = dead, 1 = alive, and the three digits representing left, center, and right tiles.
There are 8 possible states, ranging from 000 to 111. Given one of these states, the resulting state will either be alive (1) or dead (0) depending on the rules. With 8 states and 2 possible outcomes for each state, there 256 possible rule sets (8^2). These are called elementary cellular automata.
The rule sets are represented as an 8 bit number, each bit representing one of the 8 states. For example, the binary representation of the decimal number 110 is 01101110, so rule 110 is:
| 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
This means if all tiles are alive (left, center, and right) then the result is a dead tile (111 = 0). If left and center are alive, but right is dead, then the tile stays alive (110 = 1). And so on.
Generator of Elementary CA
1-dimensional cellular automata can be represented in a single image, with each row being a generation. The first row could be a single living tile in the center. The next row would apply the rules to determine which tiles will be alive. For example, with rule 110, the second row would include 2 living tiles (one for 010 and one for 001). The third row is the third generation and has 3 living tiles. The fourth row also has 3 living tiles, but with a gap. From here rule 110 evolves into a very interesting pattern. Rule 110 has been proven to be turing complete.
I built this Javascript generator to better understand cellular automata. It can be used to generate a couple thousand generations of the elementary automata. You can also check out the code if you want to experiment with it (e.g. different starting states).
Some other interesting rules: 30, 57, 60, 73, 82, 86, 101, 102, 105, 118, 150, 153, 169
| 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |