In the previous lecture we looked at the game of life which was a particular site or automaton model and in it we saw how we could get just an amazing phenomena, right, how simple rules can aggregate to produce really sort of complex, novel outcomes. What we want to do in this lecture is look at an even simpler class of cellular automaton models, and actually the original cellular automaton models, and to try and figure out what has to be true about the model in order for it to produce different types of outcomes. Number one of our core questions was what kind of outcomes is the system going to produce, is it going to go to equilibrium, is it going to produce patterns, is it going to be complex, is it going to be chaotic. And what we want to do is we want to try and understand which of those things is going to happen. And we're not going to get a definitive answer but again by using a toy model we are going to get some understanding of what leads to complex outcomes. Alright, so. First some history. Cellular automata were developed by a guy named John von Neumann, who is just a brilliant man. Von Neumann built one of the first computers known as the [inaudible] or the [inaudible]. He also came up with, was one of the founders of game theory and of growth theory in economics. So just a brilliant, brilliant mathematical mind. One of the things he came up with, and this was working with a guy named Stanislaw Ulam, who's a mathematician, was really the simplest moment he could think of in computation which is what's going to be called the cellular automata model. His vision, the cellular automata have been, sort of, studied in gory detail including a recent book by a guy named Stephen Wolfram who is the developer of Mathamatica called the New Kind of Science. And in this book, Wolfram explores to really to unbelievable depth. This is a thousand page book with hundreds and hundreds of illustrations. How these cellular automata model works. And Wolfram refers to this as a new kind of science because he is arguing for a computational inductive way of looking at the world. Okay, so what are these models, what are cellular automaton models? Well, again, they are exactly what we looked at in the game of life, except for here instead of being on a two dimensional grid, things are on a one dimensional line. So you can imagine as before we've had a bunch of cells and they can either be off, which would be clear, or they can be on. Right, so what we can do is we can the just then sorta say, okay, how do these things evolve over time. Now the difference between this and what we did before is that now If I have a cell here, right, sitting in the center, we are going to assume it only has two neighbors. So before in the grid world each cell had eight neighbors, now its only got two. Now the advantage of doing things with only two neighbors is well it's simpler for one thing, and it also means that we can exhaustively study and that's why Wolfman's book is so thick. We can study every single one of these rules. So we can write down every single rule and then ask how do the different rules work. What behaviors do they produce and that sort of stuff. The other big advantage is that it's going to be much easier to display these worlds than the other worlds because we can let time move along this axis. So what I can do is I can have this, here's the cell at this moment in time, maybe it's filled in, and then I can say what happens to it at the next period maybe it's off, and then I can say what happens to it at the next period and maybe it's on. So I can represent time as sort of moving vertically down the page. Right. So that's the model. Now I've got to decide, okay, what can the rules look like? Well Here's an example, so let's think about what a rule would have to look like. So if I think of this cell X, right, right here, this is the cell X. Now there is, and it's got two neighbors, right? So neighbor one, neighbor two, or we could call these left and right, if we want. We can ask what are the possible states those things can be in? W ell, it's possible that all of them could be off. And it's possible all of them could be on. Or it's possible only the one to the right is on, or only the cell itself is on, right? So we can think through and there's basically eight different possibilities. So what would a rule be? A rule just says �hat do I do in each one of those states?' So it could say, well, if I'm in the state where we're all currently off, then I'm going to stay off. And if we're in a state where we're all currently on, then I'm going to go on. And it could say, these two of us are on I'm also gonna go on. And then what you do is you think about, okay, here is the cell, we start out with some initial configuration. We got a Whole bunch of cells and some of hem are colored in and some of them are not. And then what they do is , each cell says well what are my, what does my configuration look like? If I'm this cell right here, I notice that all three of my neighbors are on, so I go to the look up table, see all three numbers are on and say I am going to be on next period. Okay, so all you do is for each cell, so like this cell right here. [inaudible] cell right here, it's got its on but its two neighbors are off so I go up to the look up table and say okay this is the configuration we are in right here and it might say in that situation go off [inaudible] in the next period it would stay off. So that's it. Time moves horizontally and we have these rules that look. Right? Now, one of these that Wolfman does in his book is he says okay look if you look across all these different rules you can get all four of these classes of behaviors, right? So you can get, we talked about this before, you can get fixed points, you can get alternation, you can get randomness and you can get complexity. And what we want to understand is why? Why do you get these things? What's true about the rules in order for this to be true? Okay, in order to get these different types of outcomes. Okay? Now before we go any further, okay, there's a lot of rules, how do we make ... Sense of them. How do we keep track of the rules setter. [inaudible] had an ingenious way of numbering these. So let's think about it. So if I am in this state here: all off. Well, there are two possibilities here, right? We can be off. Or we could be on and if I didn't give up this state there could be two possibilities as well We can be off or we can be on and that's true for every one of these. Two, two, two, two, two. So there's two different things I can put for each of these things. So that means there's two to the eighth. Possibilities which means that there are 256 different rules. So now we think holy cow the whole universe of these rules is of sized 256. There are 256 things that we have to explore. That is why work from this book runs to one thousand pages. We just give four pages to each rule you suddenly, you know, used up a thousand pages. Now, Wolfman also comes up with an ingenious way of numbering this rules. What he does is he says let's just get used to numbers one, two, four, eight, sixteen, thirty-two, sixty-four, one twenty eight. And then what he says is, if it's on Right? Then so let's suppose that our rule, now let me do this a different way. So, suppose that if it's, this is our rule right here. These three are on. So then [inaudible] we'll call this rule two, eight, one twenty eight and we'll just add up those numbers to give us 138. So that will be rule 138. So what we have is the first number with one, the next one with two, the next one with four, the next one with eight, and so on. And this enables him to give every rule a unique number between zero and 255. So the rule everything's off is rule zero the rule where everything is on, we just add up all these numbers and get 255. So, this is going to give us a numbering system for the rules. So let's look now at some rules that create some interesting phenomena. This is rule #30, right, so you have two plus four plus eight plus sixteen and this rule says if you are currently, if all three of you are off you stay off i f the one to the right is on or the one to the left is on, right, these two things you go on. If you are currently on you stay on. And here's a little bit of an asymmetry, if the one to the right is on you stay on Right. But if you [inaudible] your left is on over here you go off. So let's think about what happened here. These, this one, and this one, all have three. All are in this state, right, with all three up. So they are going to stay up. This one has one to the right on so it is going to come to life. Right? This one right here, this next one, is currently on with its two neighbors off, so it's going to stay on. Right? This one right here has the one to the left on, so it looks like that, so it's going to stay on and the other ones are all gonna die off. So what we get, we get these three states. Are now on these three [inaudible]. What happens with the next trade? Well, let's get start, again the ones to the left are going to stay dead, but this one right here because it's got one neighbor to the right on is going to come to life, this one because it has one neighbor to the right on is going to come to life. But this one which is in the center has three in a row so it is going to die off, so we are going to get something that looks like that. So what we get is, we get this sort of pattern spreading out, well again, we are doing this by hand, let's try this... In a more serious way, using that logo. Okay, so we're going to set this up where there's one cell that's alive in the center and then we're gonna let it go and we'll see if we can get those three, right? And now we see is this really interesting pattern evolving as I move down. And notice how this is creating now we see these different structures alright we see smaller triangles, bigger triangles and so on. Right? And one of the things that's been proven about this rule which is sort of interesting is if I drew a line right down the center like if I picked a particular cell and drew a line right down the center of its path over time it's going to be a random sequence of ons and offs so you wouldn't be able to tell, you wouldn't be able to predict, What's gonna happen next but if you knew what happened the period before. So, what this is, this is an example rule 30 is an example of a rule that produces perfect randomness. Alright? Here's the next rule, this is rule 110. So remember we get the rule the two's on the four's on the eight's on the thirty-two is on the sixty four is on, so we add those all up we get 110. So think about this one again, we have three cells over here to the left and these three cells over here to the right all have no neighbors on so they're all going to stay off. Now this one has a neighbor to the right on and so it's going to come on. This one, right here, right? Is currently on but no neighbors on, so it's gonna stay on. And this cell right here has a neighbor to the left on, right? But notice how it's gonna then stay off, unlike in the previous case. Well now if I go along this one is gonna stay off, this one's gonna stay off, but this one, because it's got a neighbor to the right It's on is in this configuration so it's going to come to life. This one has two neighbors in a, it has its on and its neighbor to the right on so it's in this configuration so it's going to stay on, right. But this cell, right here, the original cell that was on is in this configuration it's on and the one to it's right is on so it's going to say on as well And then finally, This cell right here is under configuration as in before where it's neighbor to the left is on so it stays off and so now we get something that looks like this where we sort of give this increasing triangle. Now we could, could ask what happens to rule 110 as we let it run and what we get is we get, this is a map from Wolfram, we get this really interesting pattern, and this is gonna be sort of complex we see these particles that sort of move through space and this rule 110 is classified, is class four by [inaudible] complex rule. Rigth, so what we got, here is a bette r picture if I start with a random configuration, here is rule 110. And again we see all these sort of interesting particles moving through space, we see lines moving through, we see things like this interacting and then causing bigger things, we see all sorts of crunchy interesting stuff. This is complex, right, is very hard to make sense of. So, what we've seen then which is interesting, with the simple one dimensional automaton model. It's easy to make rules where everything just dies. It's easy to make rules where everything gives blinks. There are some rules where things appear to be random and you actually prove that they are random, like rule 30. And then there's rules... Like rule 110, right, to create this complexity. So, what we can do then, is we can ask okay, here's an interesting question. Why? Right. Why are some rules, why do some rules go to steady state, some rules blink, some rules random, some rules umm complex. Before we get to that question of Why, what creates complexity, what creates chaos, what creates order? Let's just stop for a second and think about how profound these results are. These are really simple models, much simpler than the game of life and they can give us anything. And this has led some physicists and mathematicians to, to suggest: this may be how the world works in some sense. That everything may come from very simple rules. So all the complex things that we see out there in the real world, come from very simple binary interactions. So, this has led to the phrase by the physicist John Wheeler, "It from bid". Now let me quote Wheeler here because it is really sort of profound. He says it from bit, otherwise every it, every particle, every field of force, even the space time continuum itself, derives its function, its meaning, its very existence entirely, even if in some contexts indirectly, from the apparatus solicited answers, to yes or no questions, binary choices. Bits, It from bit, symbolizes the idea that every item of the physical world has at its bottom, a very deep bottom in most i nstances, an immaterial source of explanation that which we call reality arises in the last analysis from the posing of yes no questions. And the registering of equipment evoked responses. In short, that all things physical are information theoretic in origin and that this is a participatory universe. Okay, that is Wheeler in 1990. So what Wheeler is basically saying is that it from bit idea is the, you can actually explain anything... Right by just simple yes from no questions at the core and so the very, very deep bottom of reality could just be binary switches. So, it, us, the universe, everything, could literally come from bits. Now that's a bit of a, you know, that's a big leap from the simple one dimensional cellular automata model. But you know, the cellular automata model is capable of producing pretty much anything, so its interesting. Alright, so, let's get to this question of how does it produce anything. What's going on? Well, Chris Langton, who is a researcher at the Santa Fe institute, he got his PHD at Michigan, studying these cellular atomaton, you know, came up with something he calls Langton's Lambda. And what lamda does is it tells us sort of what the outcomes look like. So, let me explain what I mean. So, remember the Wolfran number digitals from one to 256. Langton takes a much simpler approach, he just says look how many things go on? In this case there's three. So if you think of Langton's lamda as three or as 3/8ths, either way, it's the percentage of the number of switches that are on. Right? So this rule would have a, a alpha, a lambda, I'm sorry, of zero or zero over eight. And this one would have a rule of one over eight. So the, Langton's lambda tells us the percentage of bits that are on. And this one, remember this was rule thirty. Right? Would have a Lambda of four over eight. Well, let's go back and look at these again. This one has a lambda of four over of zero over eight. What's going to happen? Nothing. Right. Everything is just going to die. Nothing interesting is going to happe N. What's going to happen to this one that has a one over eight. Well initially a lot of stuff is going to die off, but then once everything dies off everything is going to go on but then once everything's on it's all going to die off. So this thing is going to blink, right? What about rule thirty which has the lambda four or four over eight? Well, remember this thing was chaotic, right? This was completely random. And what about rule one ten, right? This was rule one ten. This has a lambda of five over eight and this thing was complex. Now, what you can think of then is if you think [inaudible] the bigger lambda gets the more likely we are to get something interesting. Well that is not quite true because think about when lambda eight, right, when lambda is eight then everything automatically goes on. So that is not going to be interesting either. So what is going to be interesting, it what seem to be, is sort of this in between region, right, this region where you got sort of either two, three, four, five ,six things go on, well let's look at it, so here's all the rules... In the, the one dimensional cellular automata with two neighbors, and if I sum this up I'd get two hundred fifty six. If I want to know how many class three members this sort of chaos or random and in that class there's thirty two of them, right. And if we look, Twenty of them have a lambda equal to four. And they're all in this region between two and six. Class four is the complex rules, right? And the complex rules, there's only six of them. And those all happen between three and five, lambda between three and five. So, here's what's really interesting. Now we want to ask, what causes chaos and complexity, well Its this region right here. Intermediate levels of interdependence. Right? So a rule like this which has a lambda of 7/8s or seven ... Right? Nothing interesting is going to happen. It's just pretty much going to go to everything being on and then once everything's on, right, it's going to stay on, so it's going to be stable. S o it's these intermediate levels where we see the complexity. So if you look at something like, this is the Nikkei index, where you see these incredibly complex patterns What you'd expect is that these rules have substantial interdependence. Right? Because that middle level means that whether I am on or off depends a lot on what other people are doing. So if there are lot of interdependence in the rules you are going to see complex patterns like these things. Right? Well what happens in a market. People's rules depend a lot on what other people are doing. So there is a lot of interdependence and therefore you get these complex patterns. If there weren't interdependence, interdependence, right? Then you'd also go on or always go off and nothing interesting would be happening. So what do we learn from this very, very simple [inaudible]. First, there again the simple rules can define to [inaudible] just about anything Incredibly simple rules, second we get the sort of Profound idea of it from bid and third we get the complexity and randomness its acquired some intermediate level of interdependency, right? So you can't have a digit like I always go on or I always go off. You need interdependency in the actions in order create complex phenomena. Okay, so that's cellular, that's one dimension of cellular automata. It's a toy model but it gives us a deep insight. And the deep insight is if we see complexity out there in the world its likely because people's behavior or the rules that things are following, are interdependent. Okay, thank you.
