Elementary Cellular Automata

Simple rules can often give rise to very complex behaviour.

applet

Applet built using Processing, Wolfram CA code example used as base. Source code available upon request. If this applet fails to load or screws up in any other way, please leave a comment with your browser version and operating system – thanks!

What is this?

Imagine we have a line running left to right made up of squares, and these squares can be either white or black. We then want to draw another line directly below this – but how do we do it? What rules should we use?

Well, we could use a very simple rule and just copy it directly.

eca-duplicate

But that gets pretty boring. Maybe we could use a slightly more complicated rule and say if a cell used to be black, it’s now white, and vice versa.

eca-invert

Well, it’s a bit more interesting, but not by much. What is a simple set of rules we can use that will produce more interesting behaviour? Perhaps instead of having a square rely just on the previous one, let’s have the rules depend on the previous square and its neighbors.

eca-concept

This means we’re looking at three squares that can either be black or white. There are eight total possible combinations, shown below.

eca-generic_rules

And we can decide what we want to happen when any of these situations occur. Lets try this set of rules:

eca-example_ruleset

And see what happens when we start with a single black cell.

eca-example

Could be interesting! It’d be a lot easier if we had more lines and squares for us to see a bigger picture of the structure produced by these rules though…

So that’s exactly what the application at the top of the post does. You can select whatever rules you want for the eight possible states, and toggle between a single point and random data to start by clicking on the circle in the top right.

Some Interesting Rule Sets

Since there are eight possible combinations that we can choose to either result in a black or a white square, there are a total of 28 = 256 possible rule combinations. A lot of these rules end up producing patterns that become very similar, and it was found that there are 88 unique rules, depending on your definition of unique. Here are a few interesting ones.

Rule 110

random initial conditions
rule-1
How complex can the behaviour be from these simple rules? Well, you can use this ruleset to simulate a computer. You’ve got to set up the initial line of black and white squares very carefully, and it’s equally hard to read the results, but the logic ends up being exactly the same. If you had a lot of time, you could do some interesting things…

Rule 90

single point initial condition
rule-2
This ruleset produces a fractal – the Sierpinski Triangle – when a single point is used to start.

Rule 30

single point initial condition
rule-3
If you’re wondering if these things have any real world application, this rule set displays chaotic properties and is used as the random number generator for large integers in Mathematica, used by millions worldwide.

Rule 169

random initial conditions
rule-5
I couldn’t find any information online about this, but it certainly stands out visually.

Rule 184

random initial conditions
rule-6
This rule set can be used to model traffic flow, or deposition of particles onto an irregular surface.

2 thoughts on “Elementary Cellular Automata

  1. sir,
    you are doing wonderful work on cellular automata.
    please apply to detect diseases. it will be a real contribution. i am also working on it.
    regards
    n.gururajan

  2. Geoff,

    I love this CA applet, and would like to use this to demonstrate concepts like emergence to classes I teach. Can you please send the applet and source code? I need to move this onto another network, and we need to scan it for vulnerabilities to get it approved. Thank you so much.

    Josh

Leave a Reply

Your email address will not be published. Required fields are marked *