We live in a complex world with diverse people, firms, and governments whose behaviors aggregate to produce novel, unexpected phenomena. We see political uprisings, market crashes, and a never ending array of social trends. How do we make sense of it? Models. Evidence shows that people who think with models consistently outperform those who don't. And, moreover people who think with lots of models outperform people who use only one. Why do models make us better thinkers? Models help us to better organize information - to make sense of that fire hose or hairball of data (choose your metaphor) available on the Internet. Models improve our abilities to make accurate forecasts. They help us make better decisions and adopt more effective strategies. They even can improve our ability to design institutions and procedures. In this class, I present a starter kit of models: I start with models of tipping points. I move on to cover models explain the wisdom of crowds, models that show why some countries are rich and some are poor, and models that help unpack the strategic decisions of firm and politicians. The models covered in this class provide a foundation for future social science classes, whether they be in economics, political science, business, or sociology. Mastering this material will give you a huge leg up in advanced courses. They also help you in life. Here's how the course will work. For each model, I present a short, easily digestible overview lecture. Then, I'll dig deeper. I'll go into the technical details of the model. Those technical lectures won't require calculus but be prepared for some algebra. For all the lectures, I'll offer some questions and we'll have quizzes and even a final exam. If you decide to do the deep dive, and take all the quizzes and the exam, you'll receive a Course Certificate. If you just decide to follow along for the introductory lectures to gain some exposure that's fine too. It's all free. And it's all here to help make you a better thinker!
Cellular Automata
Loading...
From the course by University of Michigan
Model Thinking
1109 ratings
From the lesson
Aggregation & Decision Models
In this section, we explore the mysteries of aggregation, i.e. adding things up. We start by considering how numbers aggregate, focusing on the Central Limit Theorem. We then turn to adding up rules. We consider the Game of Life and one dimensional cellular automata models. Both models show how simple rules can combine to produce interesting phenomena. Last, we consider aggregating preferences. Here we see how individual preferences can be rational, but the aggregates need not be.There exist many great places on the web to read more about the Central Limit Theorem, the Binomial Distribution, Six Sigma, The Game of Life, and so on. I've included some links to get you started. The readings for cellular automata and for diverse preferences are short excerpts from my books Complex Adaptive Social Systems and The Difference Respectively.
Meet the Instructors
Scott E. PageProfessor of Complex Systems, Political Science, and Economics
Center for the Study of Complex Systems
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
