I'm going to introduce the notion of cellular
automata by showing you a very simple
two-dimensional cellular automaton called
"The Game of Life." Now, this is a simulation of
the game of Life called "minilife.nlogo," which you
can download from our course materials page.
I'm going to talk in detail about what the game of Life is -- it's actually not a game at all -- but for
now, just to show you the kinds of patterns that can be
created. We have this grid of cells here, where each of these white circles is a cell. The circles
can be turned either white or black, so when I click Randomize, it's going to randomly set 12%
of them to black. Each cell follows a simple rule, the same simple rule, which takes into account
its local environment, that is, the colors of the cells around it, and each time step, all the cells are
going to change color based on the simple rules. So, let's watch this go.
So, it settles down here to some very simple structures after getting rather complex. So let's
turn this all the way up to, let's say, 50%, Setup clears it, Randomize makes 50% of them black,
and now, let's go. We get some complicated behaviors, finally settling down, eventually.
Okay, so let me now turn to the slides and tell you a little bit about what you've just seen.
The game of Life is one example of a broad class of models called 'cellular automata,' which are
idealized models of complex systems. They are large networks of simple components, where the
components here are cells, and the network part is that each cell is connected to its nearest
neighbors, or possibly some farther away neighbors. There's limited communication
among the components. Components can only directly communicate with their neighbors, there's
no central control, there's no cell that's in charge of any other cell, and yet as you could see in the
example of the game of Life, well, you get fairly complicated dynamics from rather simple rules.
And, as we'll see a little bit later, the cellular automata have the capability to do very
sophisticated information processing and computation. They also can be evolved
via genetic algorithms. So what we're going to see is that cellular automata bring together several of
the topics that we've been looking at so far, ranging from dynamics, to information, to genetic
algorithms, and put them all together in one model of complex systems.
Let me briefly comment on the terminology. The singular is "cellular automaton," that is, one of
them, and that's abbreviated "CA." The plural is "cellular automata," that's more than one. That's
sometimes abbreviated "CA" also, but I tend to disambiguate by abbreviating that "CAs," with a
small "s." As far as pronunciation goes, here in America, we call them "cellular auTOmata," but
in some other countries, including often in Great Britain, they're called "cellular autoMAta." Our
British participants can correct me if I'm wrong about that. So the game of Life is probably
the world's most famous cellular automaton. As I said, it's not really a game, but rather it's a
mathematical or computational object. It was published in 1970 by the British mathematician,
John Conway, and it's been very widely publicized, in particular at the beginning via
Martin Gardner's "Mathematical Games" column in Scientific American. The reason John Conway
called it "Life" was that it was inspired by John von Neumann's models of lifelike processes in
cellular automata, which we'll talk about in a little while. In short, what Conway wanted was
a simple system that exhibits emergence and self-organization. The game of Life is what he came
up with. As I showed you before, the game of Life is played, or plays itself out, on a grid of cells.
Here, the cells are represented as black and white circles. A black cell is said to be "alive," and a
white cell is said to be "dead." This is Conway's terminology. Each cell lives in a neighborhood.
The neighborhood of a cell is a cell itself, like the center one, and its 8 neighbors. The world,
as a whole, wraps around at the edges. So, for example, I look at this cell that's on the edge -- its
left neighbor is the cell way over here, on the right. Or if I look at the cell right here, its neighbor to the
south is this cell, right up at the top. So the sides, the bottom and the top wrap around.
Here are the rules that each cell obeys.
The first rule is that a living cell, that is, black cell, remains alive on the next time step, only if two or
three neighbors are alive. Otherwise, it dies. A dead cell becomes alive on the next time step
only if exactly three neighbors are alive. So those are the rules that every cell obeys. All cells are
updated simultaneously, in discrete timesteps. You'll see how that works in a minute.
Here's how that looks in the netlogo model, minilife.nlogo. We see that the green colored cells,
here, are the ones that are going to either stay alive
or come alive at the next time step.
This one in the middle has two black
neighbors that are alive, so it stays
alive. This one is dead, but it has
three black neighbors that are alive
so it's going to come alive at the next
time step. The rest of them do not have
enough living neighbors to either stay
alive, or come alive.
So, here's what happens at the
next time step, in that small square of
nine cells. So let's test your understanding of this with a short quiz. This quiz has three questions.
In each question you get a 5 by 5 game of Life grid. Assume that the grid wraps around the edges,
if youneed to. The question is, what is the state of the center cell, indicated by the red arrow, at the
next time step? So try that out, and watch the answer video after you're done.