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.