From Cells to Systems

An explorable explanation of cellular automata.

Written by @SpacieCat for #ExplorablesJam 2018.

Introduction

NOTE: Please use this site in landscape mode, portrait mode won't work properly!

Hi there, thanks for checking out my first explorable thing! This was made for a jam event during exams, so there might be a few spelling errors.

Part 1 : Cells

So, you want to simulate a universe? Great! What is the simplest interesting universe we can create?

Our quest to create the simplest non-trivial universe simulation will follow in the footsteps of Stephen Wolfram, and his work on the elementary cellular automata (ECA).

Interactive: Life and death

A cellular automaton (automata is plural), is a function that takes in a set of cells on a grid, and performs some simple computations to produce a new grid of cells. An ECA is a specific type of cellular automata, one that only exists in one dimension, with cells that have two possible states.

Each cell in an ECA can either be dead (shown with a light background) or alive (shown with a black background and later on in this article with coloured backgrounds).

Each cell's neighbours are the other cells within a certain distance. Because an ECA is the most basic cellular automata, each cell only has one neighbour to each side. A cell's neighbourhood is made up of the left neighbour, the cell itself, and the right neighbour:

Interactive: Neighbourhoods

Make sure you play with the above interactive a little bit to get a feel of how neighbours and neighbourhoods work, especially at the edge of the simulation (if we can't see a cell we'll assume its dead).

It's important to remember that neighbourhoods don't just impact the cell in the middle, changing a cell will affect the neighbourhoods of those around it too! To get a feel for this, try and solve this little puzzle (or just move on, it's up to you):

Interactive: neighbourhoods puzzle

See? Making changes to a cell can cause others around it to change too.

Alright, now you're ready for the real deal, here's an extremely simple ECA, it looks for cells with a neighbourhood of ◼︎◻︎◼︎ and then outputs a live cell when it sees one (hover over an output cell to see its neighbours in the previous generation):

Interactive: Single neighbourhood rule, one generation

Still, this isn't super exciting... But wait! What if we fed the output through the ECA again? Each pass through the ECA is called a "generation", here's the same ECA as before but with two generations this time:

Interactive: Single neighbourhood rule, two generations

This is more interesting, and we can start to create patterns, but we're only creating a living output cell when we see one specific type of neighbourhood. An ECA has 8 different types of neighbourhoods, they are (in binary order):

◻︎◻︎◻︎, ◻︎◻︎◼︎, ◻︎◼︎◻︎, ◻︎◼︎◼︎, ◼︎◻︎◻︎, ◼︎◻︎◼︎, ◼︎◼︎◻︎, and ◼︎◼︎◼︎

Here are the first 3 generations of an ECA with switches that control neighbourhood evolution each generation:

Interactive: All neighbourhoods, 3 generations

The convention is that the input cells of an ECA usually contain only one living cell in the middle, and that the generations are stacked below it to form a grid that shows its evolution over time.

Here's a playground that follows the conventions and allows you to edit the rules with the buttons or by clicking the cells themselves (clicking a cell will toggle the button that matches its neighbours in the previous generation):

Each ECA has it's own "rule number", that encodes all of the outputs for each type of neighbourhood. This means that you can describe the entire behaviour of an ECA with just this number! The rule number can be found by converting the neighbourhood outputs to a binary number. This is how the rule number is found:

Interactive: Rule number from

Part 2 : Systems

Whilst researching the ECA, Stephen Wolfram came up with 4 different classes that can categorize them:

Let's see some examples of each of these, just like before you can edit each ECA, clicking reset will restore it to the starting rule number so feel free to experiment!

Here's rule 223, it's an example of a class 1 ECA because all of the cells remain constantly alive:

Interactive: Rule number 223

Here's rule 196, it's a class 2 ECA because each cell toggles each generation in a pattern:

Interactive: Rule number 186

Here's rule 30, it's a class 3 ECA because the state of some cells is statistically random after many generations (it's so random that it's used in random number generators):

Interactive: Rule number 30

And here's a class 4, complex, ECA. It's rule 110:

Interactive: Rule number 110

Let's talk about rule 110 for a minute, it's very special, it's Turing complete! This is a computer science term that means "able to perform any computable operation". Rule 110 might look a little different to a regular computer, but by encoding programs and data as life and death on the first row of input cells and letting it run for long enough, it is able to carry out any computation.

So, you now want to simulate a more complex universe? Great! You can run that simulation on rule 110~ 😉

Conclusion

Thank's for reading my first explorable explanation! If you have any feedback I'd love to hear it, feel free to contact me on twitter with any ideas or comments!

Huge thanks to the following people for their suggestions: