Automata
:javascript:CSJune 3rd, 2017
JavaScript is required to view the demos in this post.
Please enable JavaScript.
Cellular Automata
Cellular automata are a simple class of automata consisting of a grid of cells where each cell represents some state that is updated every iteration. While notnecessarily particularly useful, some cellular automata display fascinating repetitive patterns or are even Turingcomplete. It is also worth noting that some patterns in nature have been observed that appear to be generated by natural cellular automata. In particular the Conus textile sea snail’s shells display pigment patterns similar to a cellular automaton.
Below are some examples of cellular automata with live JavaScript demos using HTML5 Canvas.
Conway’s Game of Life
Conway’s Game of Life is a cellular automata created by John Conway where all cells are live
or dead
. Conway’s Game of Life updates with the following rules:
 A
live
cell with less than twolive
neighbours dies (as if by loneliness)  A
live
cell with two or threelive
neighbours stayslive
 A
live
cell with more than threelive
neighbours dies (as if by overpopulation)  A
dead
cell with threelive
neighbours becomes alive
cell (as if by reproduction)
This is probably the most famous of all cellular automata. Additionally, the pulsar from the beginning of this post is an example, though the demo’s colors are reversed.
In the top right of the demo we have a beacon and blinker, both stable patterns (oscillators) that will repeat endlessly between their two states. Below these you there is a monogram (another oscillator). In the bottom left is a pentadecathlon. Across the top starting from the top left you can see the Gosper’s Glider Gun a particularly interesting pattern that generates gliders, small repetitve patterns that ‘glide’ across the grid.
NOTE: The colors in this demo are inverted from the standard style for aesthetic purposes.
Wireworld
Wireworld is a cellular automata created by Brian Silverman. While relatively simple, it is easy to construct logic circuits in and is Turingcomplete. Wireworld has the following states:
Empty
(Black)Conductor
(Yellow)Electron Head
(Blue)Electron Tail
(Red)
These states update with the following rules:
 An
Empty
staysEmpty
 An
Electron Head
becomes anElectron Tail
 An
Electron Tail
becomes aConductor
 A
Conductor
becomes anElectron Head
if one or two neighbors areElectron Head
, otherwise it stays aConductor
At the top left and just below are two clocks, circles of Conductor
around
each of which a single ‘electron’ (made of an Electron Tail
and an Electron head
) continuously circle. More Conductor
cells coming off
of these circles allow ‘electrons’ to flow to a series of
gates and
diodes. Some indepth
overviews of logic elements in Wireworld can be found at:
www.quinalpalus.com,
www.heise.ws,
and karlscherer.com.
Rule 110
Rule 110 is an
elementary cellular automata, meaning that it is a onedimensional / singlerow ceullar automata. With only two states (0
and 1
) and eight rules, this simple automata is interesting because it because it produces intricate patterns and is the only Turingcomplete elementary cellular automata. Cells in Rule 110 update based on their current value and that of their left and right neighbors according to the following rules:
If left neighbor, current value, right neighbor are …
1
1
1
, then the next value is0
1
1
0
, then the next value is1
1
0
1
, then the next value is1
1
0
0
, then the next value is0
0
1
1
, then the next value is1
0
1
0
, then the next value is1
0
0
1
, then the next value is1
0
0
0
, then the next value is0
NOTE: the colors in this demo are inverted from the standard style for aesthetic purposes, and a typical Rule 110 automata implementation has an infinitely wide row. Since this demo uses a fixedwidth row for the current state I’ve wrapped the left and right edges around to be neighbors instead.
For more on elementary cellular automata visit The Wolfram Mathworld Entry.
Other Automata
There are many, many other automata – There are 256 elementary cellular automata alone (!)
Some other notable automata include:

Finite State Machines: Useful for describing many forms of computation

Pushdown Automata: More powerful than Finite State Machines, these have a Stack

Turing Machines: The most powerful Automata, a nice example is the Google Doodle for Alan Turing’s 100th Birthday

Minecraft’s Redstone logic: Essentially a 3D cellular automata