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?"