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.