0:00

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.

Â