Automata

JavaScriptCSJune 3rd, 2017

JavaScript is required to view the demos in this post.

### Please enable JavaScript.

*Automata*. While the earliest usage of the term referred to mechanical devices, in Computer Science ‘automata’ and automata theory include abstract machines instead of physical devices. Where a physical automaton might be constructed of complex gears and clockwork, an abstract automata is constructed of state and rules that define how state is updated in each iteration or ‘generation’ of the automata. Visualizing Automata and their states produces aesthetically interesting patterns.

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 not-necessarily particularly useful, some cellular automata display fascinating repetitive patterns or are even Turing-complete. 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:

1) A `live`

cell with less than two `live`

neighbours dies (as if by loneliness)

2) A `live`

cell with two or three `live`

neighbours stays `live`

3) A `live`

cell with more than three `live`

neighbours dies (as if by overpopulation)

4) A `dead`

cell with three `live`

neighbours becomes a `live`

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 Turing-complete. Wireworld has the following states (and their colors in the demo below):

1) `Empty`

(Black)

2) `Conductor`

(Yellow)

3) `Electron Head`

(Blue)

4) `Electron Tail`

(Red)

These states update with the following rules:

1) An `Empty`

stays `Empty`

2) An `Electron Head`

becomes an `Electron Tail`

3) An `Electron Tail`

becomes a `Conductor`

4) A `Conductor`

becomes an `Electron Head`

if one or two neighbors are `Electron Head`

, otherwise it stays a `Conductor`

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 in-depth
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 one-dimensional / single-row 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 Turing-complete 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`

, the next value is `0`

`1`

`1`

`0`

, the next value is `1`

`1`

`0`

`1`

, the next value is `1`

`1`

`0`

`0`

, the next value is `0`

`0`

`1`

`1`

, the next value is `1`

`0`

`1`

`0`

, the next value is `1`

`0`

`0`

`1`

, the next value is `1`

`0`

`0`

`0`

, the next value is `0`

`green`

box bounds the current (bottom) row.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 fixed-width 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