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.