That's rule 150.
We can also consider a different rule.
This is for example rule 105.
Of course because there's
256 possible f rules
we're going to run out of them eventually.
There's a numbering system
that people have invented
and so usually when someone says rule 105
you can actually figure out exactly
what that look up table will appear as.
Here's rule 90.
You start to see some of these triangular
patterns are quite familiar,
the ways in which these triangles
interact with each other.
But here's the different one,
this is rule 110
you can see it's sort of asymmetrical.
So even if I begin with the
same initial conditions
as I ??? for rule 150
Instead of getting a triangle that sort of
propagates out evenly in both directions
you kind of have asymmetry here,
so in fact in Rule 110
a triangle propagates
only in one direction
and keeps a hard
boundary on the other.
You can also see here which is kind of fun,
it's quite clear now that rule 110
as the triangle propagates
off the left edge
we have it wrap around
to the right edge.
So the neighbor of a pixel on the far
right-hand side
includes a pixel just up
and to the right
which wraps around
to the far left.
In fact rule 110 is kind of a magical rule.
It's what we call Turing universal.
I just put up the lookup table at the top there.
But the eight possible things that could happen
give it a particular cell that you're
wondering what its state is going to be.
Rule 110 is interesting because it turns out
that it can compute any possible function.
It's actually equivalent to a computer,
to a piece of Python code.
So how does that work, how does that make sense?
Well, one way to think of it is this
If I imagine let's say a piece of Python
code that I want to execute
I can of course just put it into
a laptop and have it run.
But if I'm really clever
what I can do is I can take
that Python code,
turn it into a very long
initial condition for rule 110,
evolve rule 110 forward,
wait for a certain amount of time
and then read out at the bottom
the output of that piece of Python code.
Of course the hard part is figuring out
how to turn that Python code
Into a line of ones and zeros
that form the input to rule 110.
It's not that easy.
But what Matthew Cook was able to do
back in the early 2000s
was show that it is at least
in principle possible to do that.
In fact rule 110 given
sufficiently rich initial conditions
can perform an arbitrary computation.
It is in fact one way to implement
a Turing machine
if you know this language from computational theory.
So how did Matthew do it?
Well, it's kind of a fun way to play
just to get a sense of how you might do it.
Here are two examples
of how rule 110 behaves
given a particular set of initial conditions.
What you can see here,
let's just focus on the left panel,
is all these different structures
that appear
you have what are called gliders.
So if you look at that sort of polka dot points
or that polka dot stripe there
Cook called this an A4 glider,
and when an A4 glider meets
what he calls an Ebar glider
which is a much more complicated pattern
that propagates to the left
the A4 glider and the Ebar glider
depending upon exactly
how they collide with each other
can either be absorbed,
can change the state of the Ebar glider,
and can lead to reemission.
So on the Left-hand side the
A4 glider hits the Ebar glider,
kind of gets stored there for a while
and gets spat out a little bit later
that A4 glider continues unimpeded
but if it had hit the
Ebar glider a little earlier
in its evolution
in that case what we would have seen
is that the Ebar and the A4 glider
return into a stationary object,
into a C2.
And that C2 would stay
stationary over time.
So what Cook was able
to do is show
that in fact all these little sort of
discreet propagating structures
that emerge naturally from rule 110
and there's no magic here in the sense
that all of these patterns are produced
solely by Rule 110.
Playing out the rule for each point
what happened for each point
is the state of each point is defined
by the three units just above it.
It's just playing out that rule
over and over and over again
to produce these lines as they come down the page.
What Matthew Cook was able to do was show
this is essentially enough to produce
what you might now think of
as a set of logic gates
or way a system could
write things to a tape,
read things back from the tape,
do something to the value of that tape
depending upon what it had read,
and what else was happening
elsewhere in the system.
So Rule 110 turns out to be
not just a kind of
playful way to make cool patterns,
but in fact something sufficient to
describe arbitrarily complicated systems.
So this has been a little
introduction to cellular automata.
What I've tried to do is first of all
of course tell you how it works,
tell you what the rules are of this model
and then try to give you a sense of
??? is a great diversity of behaviors
that we can see here.
We saw rule 150 producing these propagating
triangles that overlap with each other.
We saw an example something like Rule 90,
where it also produced that
kind of triangle-like pattern
but the rules of how those
triangles interacted with each other
were slightly different,
so visually it looked different.
Then of course something like Rule 110,
which is even crazier.
Here if you set things up correctly,
not only do you get these propagating objects,
these spreading waves or indeed even
these packets moving around.
But in fact the logic of how
those things interact with each other
is sufficiently complicated that you
can perform an arbitrary computation,
that you can actually for example run
a piece of Python code or C code or BASIC.
So cellular automata are actually much more
complicated than the Markov chains we considered
in part because whereas the Markov chains
the state at one point in time
depends solely upon N states just previous
here in fact if you look far enough back in time
the value of any particular point
is influenced by a huge number
of inputs from arbitrarily far away.
So the cellular automata even
though it has the same forgetfullness
as the Markov chain
and even though the rules
themselves are incredibly simple
the fact that the one-dimensional
line that these rules operate on
can be arbitrarily large
means that we'll have, it will turn out,
a new kind of problem
for how to describe the system
and in particular a new kind of problem
when we come to renormalize the system
because what we're going to do now
is imagine taking
one of these patterns produced
by a cellular automata
Squinting at it in some way,
producing a reduced description
of that pattern
and then trying to figure out
the kinds of rules
that that pattern
could be described by.