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.