Automata

:javascript:CS

June 3rd, 2017

I am fascinated by automation, both mechanical and software. A particularly interesting form of automation is 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 repetitive 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:

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 cellular 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 1, then the next value is 0
2. 1 1 0, then the next value is 1
3. 1 0 1, then the next value is 1
4. 1 0 0, then the next value is 0
5. 0 1 1, then the next value is 1
6. 0 1 0, then the next value is 1
7. 0 0 1, then the next value is 1
8. 0 0 0, then the next value is 0

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