On the face of it, elementary cellular
automata are extremely simple.

Each cell is either black or white.

Each cell communicates only with two 
neighbors.

The system is completely deterministic,

and a rule is specified by only 8 values,

that is the values of these update states
for the center cell.

But what makes cellular automata so 
interesting and so surprising in a way,

is the degree of complexity that this
incredibly simple system can produce.

So for example, suppose we extended to 
this lattice to 200 cells and

ran this same rule on this lattice with 
some random initial configuration

for a long number of iterations.

Here's what it would look like.

So here, at the top here, we see the
one-dimensional lattice with a

random initial configuration and 
time is going down the vertical.

Here the individual cells are very tiny.
You can barely see an individual cell.

You can just kind of see an overview of
black and white

on this much bigger cellular automaton 
lattice.

And you can see that we don't get just
random looking behavior,

we get some very structured looking 
behavior that is hard to describe.

So it seems like there's some regularities
here, but they're hard to describe.

And that in a sense, is a definition of 
complexity.

We'll see later on that this particular
cellular automaton

defined by the rule I just showed you

actually is one of the more complex
cellular automata

in the whole collection of 256 elementary
cellular automata

and has some very special properties.

Stephen Wolfram is a British mathematician
and physicist

who has studied cellular automata
in great depth, and in particular

he's studied these elementary cellular
automata.

He's written a number of books and 
articles on this subject.

His most recent, called 
"A New Kind of Science",

is a 1200 page discussion of how science
itself could be rethought in terms of

simple systems such as cellular automata

that produce highly complex behavior.

In this subunit and the next one,
we'll talk about some of the results that

Stephen Wolfram found on the class of
elementary cellular automata.

As I said before, to define an elementary 
cellular automaton, or ECA,

we have to list all the neighborhoods and
fill in the right side of the arrows with

black and white boxes to 
define the update state

for the center cell at the next time step.

We can notice that since each cell 
can be either black or white,

that there's two possibilities at each one
of these positions.

This could be either black or white, 
black or white, and so on.

And so the total number of possibilities 
is two times two times two, etc.,

two raised to the eighth power,
which is equal to 256.

So there's 256 possible elementary 
cellular automata - not so many -

and in fact Wolfram looked in great
detail at the behavior of all of them.

In order to do a complete survey of 
these 256 possible cellular automata,

Wolfram came up with a way of giving each
one a unique numerical code.

These codes are called Wolfram numbers
and here's how they work.

Suppose that this is the rule that I'm 
going to encode.

What I would do is for each of the update
states over here,

if a box is white, I give it a zero,

if it's black, I give it a one.

Now I take that series of 
ones and zeros,

I'm going to flip it over, like this, and 
then I'm going to turn the numbers upright

and what I would now do is interpret 
this as an integer in base two.

And the way to do that is to notice
that this corresponds to the ones place,

this corresponds to the twos place,
the fours place,

the eights, sixteen, thirty two, 
sixty four, one twenty eight, etc.

OK so here we have zero times two to the
seventh, one times two to the sixth,

and so on. So this is just the normal way 
in which you would encode a string of

ones and zeros as an integer in base two
and if you multiply that out,

you get that this is a hundred and ten 
in decimal

and Wolfram would call this rule 110.

Let's do one more example, just to 
make sure that you got it.

So here's my new rule.

I assign ones and zeros to the update
state.

I turn it on its side by flipping it 
over like this.

And so I get one one zero zero zero zero
zero one

Now I interpret this as a integer 
in base two.

So this is one times two to the seventh
plus one times two to the sixth

plus zero times everything else
plus one times two to the zero

which is just one

so we get 128 + 64 + 1 = 193.

So this would be Rule 193.

Now let's have another little quiz

just to test your understanding of
Wolfram numbering.