So in the first section you had
a brief introduction to cellular automata

there's a lot more to say about it,

but I at least got a chance
to give you a taste for

the different kinds of patterns

that each of the different
kinds of rules can produce

and I even gave you a little bit of a sense

of the magic of Rule 110
and 110 will come back a little bit later.

For now though what I'm
going to talk about is

how we can think about
coarse-graining a cellular automata.

And when we go from the Markov chains
of the previous section

to the cellular automata here

there's going to be one important change

and that change is going to affect

how we think about the renormalization process,

so if we go back to

the finite state machines,

to the Markov chain models,

if you have a system that you observe
every let's say one second time step,

and then

you decimate that system down,
you coarse-grain it

and so you now observe the system
every two time steps.

The original model in order to get from
t+1 to t+2,

you needed to know your position among the N states,

you need to know which state you were in,
and once you knew which state you're in

you could figure out
which state you were in at time t+2.

And similarly

to go from time t to t+1

you just had to know which state you were in at time t.

It's a Markov chain and so what that means is that
you have a finite and fixed number of states over time.

When we came to coarse-grain that model

we could still keep the same relationship.

In order to know where you were at time t+2

all you had to do was know your position

among all of the N states of the
new updated model at time t.

What that meant was that we stayed
within the same model class

when we dropped some of the time information.

We could produce a N-state Markov chain

that skipped every step

if we had an N-state Markov chain at the finer-grained timescale.

This changes completely

when we come to the cellular automata.

So if we take that grid
evolution algorithm

that we introduced you to,

what you saw was that to know what this

the state of the system here is at time t

at time t+1,

you needed to know the state
of these three grid squares just above it.

And then to know the state

of that point at time t+2

again, you only needed three pieces of information.

But imagine that we dropped,
we coarse-grained, we decimated out the t+1 data.

What do you have to know about this

or what do you have to know about the state of the system here
to know the value of this point here?

And as in

???, one of the people I learned this technique from

once said this is sort of like

what a physicist would call a light cone

because as you go further back in time

in order to know the state of this point here
you need to know the state of this point here,

but in order to know the state at this point here

you have to know the state of the system at

these three points here.

And similarly to know the state of
the system at this point here, you have to know

the state of the system here and here as well.

And so as you go further and further
back in time, as you drop

this chunk of data here

if you were to naively trying to do
the same trick we did with the Markov chain

which is just come up with a model that work
just as well to go from t to t+2

you would find that instead of having
a rule that looked like f of x, y and z

your rule would now have to include a, b, c, d and e.

You'd have to in fact have five
inputs to your function.

When you coarse-grain a cellular automata
only along the time dimension,

you no longer stay within the same model class.

If you said, okay, produce a model
that can get you from here to here

that model would not fall
in one of the 256 cellular automata

that we introduced you to
in the first section of this module.

So, what do we do? Well, this is a trick

that was introduced
by a pair of scientists

Israeli and Goldenfeld

and then I learned how to make it work

in person from ????? and ????? here
at the Santa Fe institute.

But here's one story about how to solve this problem.

If you coarse-grained in time

you don't stay within the same model class

Well, what Nigel [Goldenfeld] and his collaborators did?

What Goldenfeld and Israeli did

was ask you to think not about
individual grid points

at this later time point,
but pairs of grid points.

And then to look
at the backwards light cone,

the space of influence that this pair is
subject to.

So, one step back, it's pretty easy.
I just have to add one more point here.

So this is

the set of

grid points that I have to know in order

to predict the state of
this pair of grid points at time t+2

and then if I zoom one step further back

what you can see is that

I just have to include an additional grid
point here on the far left edge.

So these two grid points at time t+2

are influenced by all of these six grid points at time t.

What Goldenfeld and Israeli
then asked us to do

was to consider this supercell here
as a unit

call this let's say

a hat and these six cells here,
to group them

into three supercell units x hat, y hat and z hat.

If you write it this way,

then the logic of
the fine-grained simulation

means that in fact the state

of the a hat grid cell

is now equal to something, we'll call it f hat,

x hat, y hat and

z hat.

So the state of this pair here,

whether they're both on,

this one's on and this one's off,

this one's off and this one's on or they're both on,

that state of that grid cell or that supercell here

depends upon the state
of these three supercells up here

and this law here

is given

in the same form as this law here
with one change.

The original evolution law
for the cellular automata

takes binary variables, ones and zeros.

This evolution law here
takes pairs of ones and zeroes

instead of there being two possible states
for each supercell there are four.

And while this one here
outputs one or zero

this function here
outputs 00, 01, 10 or 11.

So we're part of the way there
to coarse-graining the cellular automata.

We're only part of the way,
we have something that depends,

we have a function that depends

upon three arguments and spits out one.
That's an improvement

over what we wanted to do before

where we had a function that takes in five arguments.

The problem is is that these arguments

are now no longer binary variables.

So, what do we do? Well,

instead of coarse-graining just in time

we can also
coarse-grain in space.

And what they introduced was
a projection operator p.

And so what p does is it takes a supercell,
it takes the state of a supercell

and maps it to a binary
variable 0 or 1.

So explicitly there are four
possible states the supercell can be in,

and what the projection operator does
is it maps some of them

to let's say the "1" state

and it maps the rest of them
to the "0" state.

You can think of this
projection operator here

as something very similar
to what we did in the introduction

to this module altogether

where I showed you how you
could coarse-grain an image

in that case the image of
Alice and Dinah, her kitten.

In this case here for example,

we could imagine
doing a spatial decimation

where we take only
the value of the first

entry in the supercell.
That kind of spatial decimation

would lead to
a projection operator

where both of these terms
were mapped to 0

and both of these terms
were mapped to one.