Welcome back.
This video is gonna have somewhat of a different flavor
from the last one.
I thought it'd be a good idea
to explore the concept of fractals,
which has popped up quite a bit in the videos,
if only because rule 30, 110, 90
gave us really interesting spatial structure,
which have this self-similar structure.
So we saw, you know, triangles in those cases,
repeating at all scale.
And I use the word fractal
because I know much like chaos in week five,
it is a word that we hear quite a bit
and that not all of us are familiar
with the formal definition, right?
So chaos is often used to mean something random,
and that's not what it is.
We saw in week five that chaos
implied a deterministic system
and mainly sensitivity to initial conditions
and ergodicity.
And then we saw that there are ways to measure chaos.
It's not just this black box of madness.
We could quantify how chaotic a system was
using the Lyapunov exponent.
So the exponential rate of separation
of two initial conditions that start very close together.
Well, what is something similar for fractality
if we wanna measure how interesting
the outcome of rule 9110 were
in comparison to the outcome of rule two or three
or some of the more boring ones?
Well, it's kind of interesting to think of
these different approaches,
including the one we're gonna see now
as measures of complexities,
measures of complexity, right?
The Lyapunov exponent or measure of complexity
and sensitivity in time of deterministic dynamical system.
And right now, what I wanna explore,
and I'll switch to my board,
is the fractal dimension of an object,
which you could argue is a measure of complexity
in space of that object, right?
With standard one-dimensional, two-dimensional objects,
three-dimensional objects being simple
and everything else being more interesting, complex, right?
And it's kind of a nice turn of event
that when you think of dimensionality as a spectrum,
one, two, three are the exception
and everything in between those fractal dimensions,
we're gonna call more interesting, right?
So if anything, remember that fractal structure
implies a fractal dimension
and that its dimensionality of that object
is 1.5 or 0.5 or 2.15, right?
Just a non-integer dimension.
Really what it refers to
is the way that objects occupy space.
And so we're gonna measure
the way an object occupy the space
using an algorithm or a method called box counting.
And so let's start with very simple objects.
For example,
a grid, right?
So this could be the floor of your room,
if you have a tile floor or whatever it is.
And we wanna measure the dimensionality of an object.
And so what we're gonna do
is cover that object in boxes.
And just to help myself here,
I'm gonna add one row and one column
to my small object to make it fit more nicely in boxes.
And so we could start by covering it
with boxes of size three.
I say size three
because they occupy three rows and columns
in the grid of the paper I'm working with, right?
I'm gonna call that R equal three
for the length of the size of my boxes.
And so here I would need four boxes
to cover my object, to cover my floor.
So what we're gonna be interested in
is splitting the number of boxes needed
as a function of the size of these boxes.
So for boxes of size three, I needed four of them.
Let me switch color here.
We could use boxes of size two.
It's getting a little messy.
It's gonna get messier.
And I needed nine boxes of size two.
So that was R equal two.
And I needed nine of them.
Then we could get even smaller.
I could get boxes of size one.
And here really the point is
we don't even need to do the math.
We sort of know that these green boxes of size one,
well, I can fit four of them in my red boxes of size two.
And I can fit nine of them
in my orange boxes of size three.
And so I know that for each of the nine red boxes,
I now have four green boxes.
So I have nine times four or 36 way up there.
And we sort of know that there is now
this like squared relationship, right?
How many boxes of size two can I fit in boxes of size four?
You can do the math and do two dimension
and get this relationship
where you expect N to go as R to the minus two.
Because if you shrink your boxes by half,
you're gonna need four times more boxes
to cover the same two-dimensional space.
Here's an even simpler object
where that behavior should be easier
or more intuitive to interpret.
One dimensional object.
And we're gonna play the same game.
So if I think boxes of size three
and I made them too big vertically,
but that doesn't matter.
And this is actually a good example.
If there's some object,
some piece of the object remaining
in the box counting method,
you cover it anyway with the box.
So I needed four boxes
of size three,
just like my previous object.
So just like the floor,
four boxes of size three to cover my line.
Now I move to the boxes of size two,
three, four, five.
So five instead of nine.
And for the previous object,
four boxes of size two.
And then I moved to boxes of size one,
one, two, three, four.
Hopefully I'm doing this right.
Five, six, seven, eight, nine, and 10.
Look at that.
Is that surprising?
Let's double it, 10.
Is that surprising?
If I needed five boxes of size two
that I now need the 10 boxes of size one?
No, because I'm covering a line.
So if I shrink my boxes by half,
I should need only twice as many boxes.
In two dimension, I say only twice as many.
Because in two dimension,
it was shrink them by half,
you need four times more
because you need twice as many in both dimensions.
And so really the intuition that I want you to have
is that you can think of these relationships
as a way to measure how an object occupies space.
And so this N going as a radius of the box to the minus one,
really that's saying like dimension one.
And R to the minus two was saying dimension two.
Right, the relationship.
And I'm sorry, some of this might be covered by my video,
mystery of online recording.
But the key notion is that the number of boxes needed
should go as the size of that box
minus the dimensionality of that object.
That's not gonna be perfect.
If the boxes are too big, right?
How many boxes of size 1 million
do I need to cover the line?
One, of size 1,000, one.
Right, so if the boxes are too big,
that relationship doesn't apply.
If the boxes are too small and my object is pixelized,
likewise, it's not gonna quite work.
But there is a regime where that should capture
how that object occupies space.
And that regime hopefully can be expressed
as a power law relationship of this form,
number of boxes falling as a power law
of the size of those boxes.
And when I say size, I mean the side,
the length of the side of those boxes
and the dimensionality should come into play.
Note that for the object in one dimension,
you don't need to think of boxes.
Those can just be like pieces of length
that you put on your object.
And if we were dealing with a three-dimensional object,
we would be like covering it with cubes or actual boxes.
The key part is that because those both dimension one
and two are embedded in two dimensions,
I was able to use like square boxes to cover it up.
But that's a small detail really.
We'll be dealing mostly with two-dimensional objects
and you can think of covering them over pixels.
So saying like, is my object within a box
that starts at this point and end at this other point?
Yes or no, do I keep that box?
That should be the algorithmic view
that you have the box counting method.
So let's put that into action just as an example.
So I showed you this picture before
in the introduction to this week.
This is an outcome of rule 30.
It looks absolutely beautiful.
And we might be interested in measuring
its fractal dimension.
And so we could play the same game and say,
I'm gonna start with sides of dimension three.
That's like one, two, three, one, two, three.
And the game we would play is we start in a corner,
we cover the entire space in these boxes.
And I'm not gonna do the entire space.
And then we go over every box and we ask our code,
is the box in the bottom left corner
necessary to cover my object?
Yes, you keep it.
Is the box above it necessary in covering my object?
No, you remove it.
So I keep the box in the corner, I don't need it.
Is the box above it necessary?
No, I remove that one as well.
And so I end up only keeping the box
that touch or cover my object, right?
And so in this case, it's pretty simple.
You keep everything underneath it
and I'm just gonna do half of my object.
Well, that one was a little too ambitious.
One, two, three.
Look at that,
that one as well.
Going a little fast, playing loose.
You would have very regular box
if you were doing this with code.
Okay, that doesn't look right, but you get the idea.
And we've getting rid of all the boxes
that don't cover the space.
Now, the important part is,
as we make them much and much smaller,
there will come a point where R will be equal,
like three was like based on my grid,
but the pixel size of my image is actually much smaller.
So I could go to that, you know, 0.1.
And then I'd be zooming in here,
going for example in this box,
and I would be covering this with 10 boxes.
And it's not even close to 10 boxes.
So like pretty small boxes.
And you can imagine that you can end up
with boxes that don't cover some of the inner details.
If I move around, like find a big triangle
and like you have a box that fits like this,
it's not needed.
So as you get smaller and smaller boxes,
you're gonna start rejecting some of the inner boxes
that's gonna let you capture the holes
in the structure you're creating.
And so we would like reject this one
and we would end up maybe with boxes like this,
like this, that like go around the object.
So the way you should think of this really,
I like the one example case a little better
because I think they're more intuitive,
is think of it and we'll do that reading as well.
Think of it as measuring the coast of a country, right?
And that comes from a great paper
by Benoit Mandelbeau from the '60s.
How long is the coast of Great Britain?
Well, if you're measuring the coast of a country
with sticks that are a mile long,
well, as you go into bays,
you'll only be able to capture so many details.
Whereas when you make your stick smaller and smaller,
you will be able to measure the coast and go into rivers.
And so the answer you're gonna get is getting excited,
but it's gonna depend on the measuring stick that you have.
And here it depends on the boxes.
And so for the coast, just like for this crazy objects,
we expect that the number of measuring sticks
or boxes that we need to cover an object
should go as a certain power.
And here it could be, it could be minus 1.5.
This object, and I'll let you explore that on its own,
but could have a fractal dimension
which exists between dimension one and two, right?
I know it's less than two because I can represent it
and embed it in 2D,
but I also know it probably less than two
because you have some of these finer details
where I'm gonna be rejecting more boxes
than I would if it was a solid 2D objects.
The question is, is it 1.5 or is it 1.99?
You know, any object that you run on,
like binarize a picture of your cat or your dog
and run box covering method,
you might find a fractal dimension.
The question is whether it's robustly fractal
and whether it's like 1.99 with a bunch of noise,
depending on the size of the boxes.
So it really all boils down to these pictures
of how many boxes are needed
and then trying to represent that as a power law.
I don't wanna go into too much detail.
I think it's an intuitive method
and it's best if you just start implementing it on your own.
And regardless of what you code in space,
it's interesting to think about the dimensionality
of traffic jams or forests
or schools of fish,
whatever it is that you use CA to represent in nature,
you'll be able to think about the dimensionality
of these subjects.
Something we were just not able to do in module one.
And I think that's really interesting.
And so I'll let you play with this box counting method
as you go and play around with creating some CA of your own.
So see you in the next one.