Something from Nothing?

The common sense view is that 'nothing comes from nothing'. This intuition seems on face value to make sense - how can something spontaneously appear from out of nowhere? In recent times, this intuition has been shown to be misguided. There are several examples

• Evolution where complex life 'emerges' out of exceptionally simple beginnings

• The Big Bang - the entire universe created from a Singularity

But I want to talk about another type of something from nothing. One which on the surface seems a touch trivial compared to the examples cited above but in reality is in many ways deeper and more universal, namely Cellular Automata.

What is a Cellular Automaton or CA?

To start with, imagine an enormous sheet of graph paper, let's say a million squares by a million squares (or cells, hence the name). At the top row in the middle, let's fill in one of the squares, making it black. Now all a CA does is to define what the next row of squares will look like (i.e. which ones we should fill in) after we apply a few simple rules. For a very simple example, let's define two simple Rules :-

• Rule 1: if a square is currently white (not filled in) then the square below in the next row should be black

• Rule 2: if a square is currently black (filled in) then the square below in the next row should be white.

Now if we applied this small set of rules to Row 1, what would Row 2 look like?

After significant colouring in effort, (better if an Automaton did it) 999,999 squares would be black and the one in the centre would be white? Agreed?

Now let's apply the rules again, this time to 'generate' row 3 from row 2. Now, we've saved some manual effort because 999,999 squares would be white again and the centre square would be back to black. With some imagination, you should see that this will just continue to alternate back and forth over the million rows of our virtual graph paper.

It seems like a lot of colouring in for a very boring pattern.

What's the big deal?

It becomes more interesting when you have certain types of (still simple) Rules to generate the rows. Of the virtually infinite possibilities of CA's, there are a certain class where the pattern generated is not regular at all. In fact, the most interesting CA's are where we seem to be on the cusp of regularity vs randomness.

In particular, one very simple example is called 'Rule 110' (named as such by Stephen Wolfram, one of the pioneers of the field). Note that the name Rule 110 might be more accurately called Ruleset 110 since it consists of a number of rules as we will see below.

In his book, 'A New Kind of Science', Wolfram shows Rule 110 to be in a very interesting class of CA - but more on that shortly.

What is Rule 110?

It has eight rules within it:-

111	110	101	100	011	010	001	000
0	1	1	0	1	1	1	0

(where 1 is our 'black' and 0 is our 'white')

For the geeky-curious: why is Rule 110 named that way? Well if we look at the pattern above - '01101110' - it's 110 in decimal.)

Simply put, when we see a certain pattern of three cells in one row, we fill in the square below the centre of that pattern in the next row. That's it.

For example, Row 'N' below has the pattern '011' so we look '011' up in our table of rules and see that the cell below should be '1'.

	0	1	1
		1

Now, bear with me, the payoff is worth it!

What happens when we 'run' this CA?

Note that 'running this CA' may mean writing a computer program that automates these rules or it may very well mean taking a piece of graph paper and filling in the squares as per the rules - your choice ;)

Either way if we start by putting a solitary '1' in the centre of our (virtual or real) graph paper and then apply the rules to get Row 2, and then repeat this on Row 2 to generate Row 3, then Row 4 etc etc, we would get the pattern below :-

This looks at best, mildly interesting, but we have only run it for 16 rows or generations.

What if we ran this for many thousands of rows? Well, with a computer, this is straightforward. This is what we would see :-

At first glance, the pattern looks mainly regular but if we look a bit closer we can start to see some definitely non-regular activity. Now, other than making some abstract art, what is interesting about this CA?

The first point to make is that from some extremely simple rules, we can generate very interesting behaviour. This CA seems to be on the edge between order and randomness. Other CAs (sets of rules) create different patterns, some of them repeat endlessly, others are seemingly completely random.

So far this may seem like an interesting but rather abstract, academic exercise.

But now, I want you to take the Red Pill..

CA's in Nature

It would seem absurd to think that a CA could spontaneously occur in Nature but in fact something like that does indeed happen.

Take a look at (my own!) shell below :-

Lioconcha hieroglyphica - a naturally occurring 'CA'

There's something rather magical, rather eerie. going on here. If you look it up in Wikipedia, it says :-

"The markings may be the result of a diffusion-mediated chemical cellular automaton"

In other words, CA's are hiding in plain sight in Nature!

But can we go even deeper?

CA as a Computer?!

Yes, the final, big reveal is that Rule 110 is what is called a Turing-complete CA. In plain english, it means this CA can perform any algorithm or calculation that any computer can perform!

This is quite a tricky concept to grasp and it's perhaps first of all important to point out that the previous sentence is true, even if you use a pencil and graph paper to generate the rows of the CA! i.e. The CA itself is a computer.

This was first proved in 2002 by an assistant of Stephen Wolfram called Matthew Cook. Cook's method is very ingenious and wildly complex but the essence is as follows.

Imagine we take our graph paper and make it, say, a trillion times wider and a trillion times longer. And instead of starting with a single '1' in the middle of the first row, we 'prime' the CA by setting an initial pattern. The key point is that this pattern is the data and the algorithm we want to run.

(Knowing precisely how to set up these initial conditions is beyond human understanding but in principle, this is certainly possible.)

These patterns then unfold as per the exact same simple Rule 110 rules but now, due to the exquisitely crafted initial set up, the patterns that emerge are calculations and their results. In essence what happens is that curious structures called gliders (patterns of cells) collide and form new structures and this is how the algorithm does it's work :-

The details of setting this up are beyond the scope of this article (and beyond me..) but for the curious, you can find it here http://www.complex-systems.com/pdf/15-1-1.pdf.

Summary

So, from just a set of incredibly simple rules, we can create a universal computer! That's already pretty deep but we can go even further into the realm of (speculative) digital philosophy and digital physics. Wolfram explains in his book that the whole of fundamental physics so far has rested on the assumption that matter and space are continuous i.e. Ever indivisible. He postulates a new model of fundamental physics where the whole universe at a level far below even the subatomic, is indeed discrete and that the universe unfolds as a form of CA.

It's a pretty deep thought – you can create an entire universe from a sheet of graph paper and a pencil.

Get colouring!