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.