Welcome back.
In this video we'll try and explore how to computationally
encode implements of the elementary CA we were just
talking about.
So I'll go to a notebook that I'll be sharing with the group
and we'll want to have some functions
that decode and run cellular automata.
I will be leveraging the binary representation
that I talked about in the introduction video.
So if you're not familiar with binary numbers,
I invite you to pause this video
and make sure to watch this week's bonus video
on binary number.
I'll give one example, this rule 130 function right here,
which implements the CA in sort of a naive way
so that we make the rules as explicit as possible.
So let's start with this one.
So I've written here the rules of the CA,
so the current pattern of the index cell
and its neighborhood, which can be 1 1 1,
1 1 0, 1 0 1, and so on.
And the state of that index cell a step into the future.
So 0 0 0 for the first three rules.
This is rule 30, right, so remember that this 0 0 0
1 1 1 1 0, is the binary representation of rule 30.
Right, so I have 2 plus 4 plus 8 plus 16
plus 0 0 0 equals 30.
And so what this rule says is that if I have 30,
I know what my rule set is
and I'll define this three dimensional array
to help me know, well what are my neighbor to the left
is 0 or 1, 0, I'm 0 or 1,
my neighbor to the right is 0 or 1,
it's a three dimensional array
with only two cells in each dimension.
So really this cube that's gonna give me the new state
of an index cell in a given state.
Or in a given neighborhood, I should say.
And so what we're gonna do is run this one dimensional CA
but use a second dimension to encode time.
Right, so think about a big matrix
where the first row of that matrix
represents your initial conditions,
and the second row represent the update
of those initial conditions
and then the update of that update,
the update of that update,
and so time unfolds and unrolls as you look down the matrix,
right, and it's just an easier way to represent CA
than updating a vector in your face in real time.
So what this code is gonna do
is go over every time step that I'm asking it to do,
so how many rows do I want in my matrix.
For each of these rows it's gonna go over every cell,
and it's gonna check the state of that cell
and the state of its neighborhood.
So who's to your left?
Well, to the left of J is J - 1,
right, to the left of index cell J is cell J - 1.
I'm gonna have this module of function
because if I'm looking to the left of cell 0,
and I hit the minus one, I want to loop back around
to the cell to the right.
So what I'm saying is that I need to specify
how I'm dealing with my boundaries,
and we're gonna see that in the textbook,
there are a lot of ways to do that.
You could fix the state of those boundary cell,
you could have special rules for those boundary cells,
or in this case you could have periodic boundaries.
So really we're saying that our vector is a ring
on which our CA is updating.
The center cell, it's easy,
I don't really need a module here, it's simply index cell J.
And then to the right is J + 1,
I do need a modular operation here again,
because my neighbor to the right
could be the very first neighbor
on the other side of the ring
if I'm the last cell, if J is the last cell.
And then we'll just apply the rule.
So at rule I + 1, next generation for index cell J,
we're gonna apply rule
based on the state of neighbors to the left,
the index cell in the center and neighbor to the right.
Okay, so that's rule 30, I said,
so rule 30 specifies the sequence of 0 or 1,
the rules, the size of the rule set,
and the rules themselves are set,
it's just the outcome that is specified by number 30.
So I'm gonna define that,
and I'll scroll down now to this main code that runs the CA.
So there are a few things,
few parameters we still need to specify, right,
rule is gonna be 30.
And we need specify the size of our ring.
So it's gonna be 64 cells.
The code is a little more general
and I invite you to play with it.
You could specify the number of states,
you could specify the number of neighbors.
So the size of the cardinality of every rule.
So here it's three because you need
to specify the index cell in two neighbors.
And then how many steps will the model run for?
So here's 16.
Initial conditions and we'll see
that especially in two dimensions.
But initial conditions are critical in the case of CA
because really we don't have a lot of parameters.
The rule set is pretty simple, it's deterministic
but different initial condition will lead
to a different time series.
It is a deterministic model that's specified completely
by its rules and initial conditions.
So in this case, we'll keep it super simple.
Every cell is off for generation one or
for our initial conditions
and we'll initialize on cell in the middle of our ring.
So at n divided by two.
If you haven't seen this double division symbol before,
it's a division followed
by a floor operation to make sure it's an integer.
So if n was equal to 1,
I would get 5.5425, right?
Okay, and then I'll run my rule 30
over that tape that's gonna give me this tape subject
which is a matrix and I'll simply plot it
in time to let it update.
16 times steps, right?
And I could go back here
and ask for a little more generations
and I slowly see rule 30 unfolding, right?
And rule 30 I showed you a screenshot
in introduction is a surprisingly interesting rule.
So what's gonna be interesting is to
go explore the other rules and see
whether interesting behavior is the exception or the norm
of these elementary CA.
When you play with this, I invite you to look
at this function at the bottom, which lets you
visualize whatever rule you might be interested in.
So you just specify the number.
If you're interested only in rule 30,
these are the rules we just implemented
as you want to try different numbers,
it might be interesting to be like,
what was the set of rule 18 again?
And just visualize them as you go
because it can be quite hard just from the number to
like decode binary in your head and figure out the rules.
So visualizing them is always useful.
These rule set are essentially, you know, the box
and arrow diagrams of dynamical system.
They specify from this state and neighborhood where
do you go in a very deterministic way, but the box
and arrow representation is still useful as a map
of the system.
Okay, so instead of running this run rule 30 function,
I'm gonna run this general cellular automata cell
auto function, which will allow me to go explore any rule
that I'm interested in.
And so what does this function look like?
Well first of all, this run cell auto is going
to need the rule set for a given number, right?
So I simply give it a number and I say, run the rule set
with number 20, right?
Well, so I have this decode rule function here
and this decode rule function is passed to run cell auto
as a rule set.
I got a little confused 'cause I thought I was defining that
on another line, but it's the argument here.
And so with this decode auto, this decode rule
is gonna do is simply use this list of rules.
So we need an order, we need to specify what is the order
in which we're specifying rules when we're saying
that the numbers to the right here
some to run to number 30, okay?
So the way that's gonna work is using the divide
by two algorithm that you might be familiar with.
So if you don't know what I'm talking about,
I invite you to pause this,
go watch the binary number video.
But essentially it's an algorithm
that takes a number, right?
113 and decomposes it in its binary sequence.
The key to the algorithm
if you don't wanna watch the video is that the final digit
of a binary number essentially encodes plus 0 plus 1.
So it encodes whether you're even or odd number
because all the other binary numbers are powers of 2.
So they have to be even.
And so what the divide
by 2 rule said is are you currently odd or even?
If you're odd, I know the final digit is a plus 1
then it does this divide
by 2 and 4 to go see whether you were
in the bottom or or second half
of the sequence and then repeats the operation iteratively.
And that's how you can create your sequence
of zeros and ones.
So what this decode rule function is doing is simply filling
up these rules by sequence of zeros and one using the divide
by 2 algorithm.
Great, so when I call my run cell auto
with the decode rule, I give it the rule set automatically,
really through the divide by 2 algorithm
for a given rule number.
Then what I need to do in this run cell auto function
right here is the same thing as in the previous version.
For every time step that I'm interested in, for every cell
at every time step, I need to apply the rules.
Well, now the tricky thing is the way I encoded these rules,
I need to know essentially whether 1 0 0 is rule number one
or rule number four in this case, right?
I need to remember the hierarchy of that number.
Well, so these are also encoded from 0 to 8
by their binary sequence, right?
1 1 1 is rule eight, 0 0 0 is rule zero
or I should say this is rule seven and this is rule zero.
So index at zero.
And so all we have to do is ask what is the sequence
of state of your neighborhoods?
The neighbors to the left encodes, whether you know, 2
to the 0 1, 2 to the 2 2 is included.
So that's a four.
If it's on middle neighbor, your own cell
in the cell of interest J, that's a plus 2.
If it's on neighbor to the right,
that's a plus 1 if it's on.
So by looking at the on and off state of neighbors
to the left cells of interest
and neighbors to the right, we can recreate and ask
for rule four in the rule set or rule zero in the rule set.
If you don't know what I was just referring
to by saying like, you know, two to the zero,
two to the one, two to the two,
that's the encoding rule for binary numbers.
And again, that's all in the bonus video for this week.
And so once you have that, this is telling you
whether given a certain neighborhood, cell J
at generation i plus 1 should go to 0 or 2 1.
And so let's run that and we can
run a rule number one, in this case.
We get this cyclic behavior, right?
So we had really interesting behavior
for rule 30 cyclic behavior.
Now, really the classification that we did
in module one for dynamical system,
the idea of time series can be monotonic, cyclic,
asymptotic, chaotic, chaos is a weird concept here
in discrete space, but like, let's call it complexity.
This classification will still apply.
And so we can play with different rules
and here we have a variation of what we just saw
but with a drift to the right.
So sort of a combination of cyclic and monotonic behavior.
Some of the rules that are, whoops, some of the rules
that are known to be interested, for example
are rule 110, which creates a very regular pattern
that you might recognize and that will bring us to the topic
of fractals later this week.
And I have the rules set here and other rules
of interest could be 90, 184.
So let's go check those out.
That was a note to myself.
Again, it's not too surprising
to see these really interesting patterns emerge.
And I say not too surprising, when you look at the rules,
you have no idea what's gonna happen.
This is no doubt emergent behavior, but this pattern
of Sierpiński triangle really, well, it's not too surprising
to sit emerge in a way because we're iteratively
applying the same rules again and again and again.
So there is this potential for self-similar patterns
and you know, I don't wanna, maybe I've been looking at them
for too long.
This is still crazy to me.
It's crazy to me that very simple rules
like these can give rise to interesting behavior like that.
And I say it in all videos this week.
If anything, that's the main story behind CA.
A rule 110 that we just saw
for those interested can actually be shown,
that rule set can be shown to be a touring machine.
There's enough in the rule set, you know,
to give you a default behavior of reading, obviously
but you can also specify conditional statements
and for loops and you know, stopping conditions.
And so you can do computation
with the CA if you have enough memory.
And where's the memory for these weird computers?
It's all in the initial condition, all in the tape.
And so we'll explore that at the very end of this week.
We have to be careful when we play with them
if they're meant to be a model of reality
to test different initial conditions, right?
You don't want to put all your eggs in one basket.
So the same way we have to play
with parameters and dynamical systems,
here we have to play with initial conditions quite a bit.
But we also wanna make sure to
distinguish the power of the rules
with that of the rule set.
So the behavior is set by both
by the rules and the initial conditions.
And the outcome is really set by everything here.
So the analysis of these should go
beyond just saying that this is an incredibly surprising
and interesting pattern.
And so we'll do that slowly over the next few weeks.
But for now, I think that's enough.
I invite you to play with this code
and I'll see you in the next one.