In this sub-unit, we'll start off with a little bit of history, and then we'll talk in depth about the
simplest possible cellular automata, called "Elementary Cellular Automata."
The idea of cellular automata was invented in the 1940s by two mathematicians, Stanislaw Ulam
and John von Neumann. You may know the name John von Neumann as one of the pioneers of the
idea of computers, and programmable computers in particular. von Neumann was particularly
interested in how to build machines that could have biological or lifelike properties. He was
especially interested in the idea of self-reproduction by machines, which at the time,
many people thought was impossible. In thinking about this, von Neumann discussed the problem
with his colleague, Ulam, who suggested that von Neumann look at the problem using the notion
of a cellular space, very much like the cellular automata that we have talked about, and will talk
about in this unit. I'm not going to go into details on von Neumann's work, but it's quite fascinating, and
he actually had a whole book on this subject called "Theory of Self-Reproducing Automata,"
which was actually completed after von Neumann's death by Arthur Burkes. This book is
rather technical, but it was a milestone in the connection between the nascent field of computing
and biology. Before I start talking about elementary cellular automata, let me just mention some of
the applications of cellular automata. There have been many applications in Computer Science.
Cellular automata is a model architecture for massively parallel computing, and also for
molecular-scale computing. In complex systems, cellular automata have been used widely as a
tool for modeling processes in Physics, Geology, Chemistry and so on, across many, many
disciplines. It's also been used as a tool for studying abstract notions of self-organization
and emergent computation in complex systems. And that's really what we'll be focusing on in this
unit. And I should point out that it's important for people studying complex systems to know
something about cellular automata, because they are among the most common modeling tools in
the field. Let's talk about the very simplest kind of cellular automata, which are called "elementary
cellular automata." So these are one-dimensional. Notice that the game of Life was two-dimensional.
We had a two-dimensional grid. But here, we only have a line of cells, and only two states, like the
game of Life. Cells are either black or white.
And each cell looks at
its nearest neighborhood
in its line. So, the neighborhood
of this white cell is itself and
these two black cells, and so on.
And here the whole can be circular,
where the neighborhood of
this black cell on the left-hand side
is the right-most white cell itself and
its neighbor on the right side.
The whole thing wraps around
like a circle. I've listed here
all of the possible neighborhoods
that a cell could find itself in.
And you can verify for yourself
that there aren't any other
possibilities. Now, to specify
the cellular automaton, we have to
specify what each center cell will
change to, depending on its neighborhood.
So this whole table here is called a "rule"
for the cellular automaton, and this says,
for example, if a cell is white, and has two
white neighbors, it turns white. If a cell is
white and has a left white neighbor and
a right black neighbor, it turns black.
And so on. So here, we have to specify
every possible neighborhood and its update state.
And this is just one particular way of specifying
the update state for the central cell.
Let's see how that works.
Every cell looks at its neighbors at each
time step and updates, and all the cells
update simultaneously. So let's
do that. This top one was time step zero.
Here's the next time step where, for example,
we have black, white, black. This cell looked that
up in the table -- black, white, black -- and said that
it had to turn black at the next time step.
And you can verify that the other cells follow
their rules as well. Okay, so now you could
do this again for the next time step,
and again, and again, and so on.
So guess what? It's time for a quiz.
The quiz gives you a rule, the same rule
we were looking at before, and says, "after
time step three, from this state of the lattice,
what will the lattice be at time step four?"