So, the picture that emerges
is that simple, iterated rules are
capable of producing
surprisingly intricate
and interesting fractals.
Take a line, replace it
with a bent line.
Take those lines,
replace them with
bent lines
and so on,
and you can produce
a really wide array
of fractals.
In the next subunit,
we'll start experimenting
with putting randomness
into these fractal-generating
rules. But before I do that,
I want to say a little
bit more about the
processes that the computer
was doing for us.
So far, I've been describing
these fractal-making processes
in qualitative terms.
Take a line, bend it like this,
do that again and again.
But at some point,
we need to formalize this
a little bit so that we can
write down what we're
actually doing and
do math with it and maybe
prove some results
in experiment.
Or, we need to come up
with some way to
instruct a computer to
do this work for us.
In both cases, this requires a
little bit more formalization.
Now, there are two related
ways that this formalization
is often done.
One is called iterated function systems
and the other is L-systems
or Lindenmayer systems.
And in what follows,
I want to say a little bit
about each.
We're not going
to go into
either of them
in any detail. They are not
a key part of
the course.
But I want to introduce
them so that you know
what they are, because if you
read more about fractals
you're likely to find them--
find these terms used,
these ideas used.
And to give you enough
of a background so that
you could read further about
these topics on your own,
if you wish.
So, let's get started
by looking at
iterated function systems.
So, a very short description
of iterated function systems,
often abbreviated IFS.
So, an iterated function system
is an iterated, or repeated,
geometric transformation.
So, the basic geometric transformation
is to start with a rectangle,
make four small copies
of the rectangle,
and arrange them like this.
So, this is actually
four geometric transformations
in one. I take a rectangle,
and I shrink it, put it here...
A rectangle, and I shrink it,
and put it here...
These two rectangles
are shrunk but also rotated
60 degrees this way,
60 degrees that way.
Each of these geometric
transformations can be
described mathematically.
It would be some sort of
a matrix operation.
You would contract
a certain amount
in this direction,
a certain amount
in this direction,
and then translate
and, if necessary,
rotate. So, we aren't
going to go into the math
at all. It's well beyond
this course, but you can
write down matrices
that do these geometric
transformations. So, then,
once you've written that
process down, you just
repeat it. You
take what you have
from the first step
use that as input
to get the second step.
So here, we again do
the exact same transformation.
We take four copies,
shrunk down. One, two,
there. And these two copies
get rotated. And then
we do that again,
and again, and again.
And we're left with
our old friend,
the Koch curve.
So, this is one example of
an iterated function
system. And let's take a
look at one other that
has a somewhat more interesting
and certainly less
familiar outcome.
Here's another example.
So, we start with a square
indicated here, and we do
two transformations to the
square. We take the
square and we shrink it down.
So, this big square becomes
this dark square. And
then we also
take this square,
shrink it down a little
bit less, rotate it,
and move it here.
So, we start with the
initial square, we end up
with these two dark squares,
we add them together.
So, this "U" is a
union function--thinking of
this in terms of sets.
So, we start with a square
and then we do
these two transformations
and combine them to
get this shape.
So, that's our function.
Again, it would be described
with a couple of matrices
that do this rotation and
the shrinking and
translation. Then we would
take that shape and repeat.
So, we'll take this shape
and we'll do two things.
We'll make a smaller copy
and slide it up to the
left. There's that
smaller copy.
And then we
take this copy and
we do what we
did here. We make it smaller
and rotate it like that.
So, we take this shape,
make it smaller,
rotate it like that
and we get that.
Doesn't look like much.
In this example,
you can see
right away--
partly because we've
been looking at the
Koch curve forever,
you can say, "All right,
I know what this
is going to be."
But here, I probably should
have just shown you
this. Build the
suspense up. It's not
so obvious what's
going to happen.
Well, it turns out--
so this is step one, two,
three, and then they
jump ahead, I think, to
five or six in this figure--
one gets this really
interesting sort of
spiral.
So, this type of mathematical
system is known as an
iterated function system,
and it's a combination
of a series of geometric
transformations
usually written down
in some sort of
matrix form. And you can
then write down what
happens when you iterate that
and that's a well-posed
mathematical system.
There's some theorems
about this that say
that there's a unique
and I think a stable
attractor. So, kind of
any shape
you start with
is going to end
up with this spiral.
And then one
can do
different sorts of
mathematical analysis
in this. So, the main point
of this is to say yes,
one can mathematize
these processes
that I've been describing
just with words and
pictures and my hands.
And there's a pretty
rich set of mathematics
that is used for this.
I don't think that
iterated function systems
have a lot of
direct bearing on
complex systems,
so we won't cover
them too much in
the course,
but they are
fun things to
play around with.
Lots and lots has
been written about
them. I have a couple
references in the
additional resources section
for this chapter, this
unit, if you want
to read more. And,
of course, you can
always explore
on your own. So,
those are
iterated function systems.
Another way to
formalize this idea
of building fractals
is through something
known as L-systems.
L-systems, as we'll see,
is an algorithmic
way of generating
a fractal. So, I think of
iterated function
systems as being
algebraic and
geometric. The
algebra is from the
matrices that are
used to encode the
geometric transformations.
L-systems are algorithmic,
things that you could
maybe more easily
tell a computer to do.
So, this is a little
bit abstract. Again,
we're not going to go
into this a ton in this
course, but I thought
it's worth maybe
doing one example
so you know what
this is about.
Because you might
encounter these
ideas elsewhere.
And this can be a start
if you want to pursue
this further.
So, I'll illustrate
L-systems with an example.
So, one starts
with a starting point--
--what else would
one start with?--
and that's called
an axiom. And I'll denote
"F" for this.
And then there's
something called a
production rule,
and that's a
transformation from
one symbol to another
symbol or a bunch
of symbols.
And, in this case, we
do the following.
So the rule is
F gets transformed to
F plus F minus minus F plus F
(F + F - - F + F)
And this isn't something
you would do arithmetic to
but this is a series of
instructions, as I'll
explain in a moment.
There's some other production
rules that we need.
This says that plus gets turned
into plus (+ → +)
and minus gets turned
into minus (- → -).
And then there would be
a parameter,
which in this case
would be 60 degrees.
All right, so what in the world
is all this stuff?
Let me try a drawing
to illustrate this.
So, we start with our
axiom, F.
So, this would be n=0.
And then we replace
F with this.
And you can probably see
this coming. It's this
shape again. So F
gets replaced with
F plus F minus minus
F plus F (F + F - - F + F).
And what's going
on here is as follows:
F means draw a line segment
plus means turns to
the left 60 degrees
that's where this parameter
comes in,
then F means draw a
line segment. Minus
means turn to the right
60 degrees. So
you're heading this way,
you turn to the
right 60 degrees.
Then there's another
minus. Turn to the right
60 degrees again.
Now you're heading that way,
draw a line segment,
you do a plus, turning to
the left 60 degrees
and then another
F. So this is
a sequence of instructions
that tells you how to
go from this line segment
to this line segment.
So, those are the rules
that get us from
here to here.
Now, we would apply
those rules again.
Every line segment F
gets replaced by this shape.
And that's exactly what
this production rule
does. So, I take this
sequence of symbols
F plus F
every time I see an F
I would replace it
with this long thing
every time I see a plus
I would leave it alone.
F gets replaced with this,
minus minus is left alone,
and so on. So,
let's write that out.
So, this F
gets replaced
with F plus F minus minus F plus F
(F + F - - F + F)
That plus stays put.
This F gets replaced
by this whole expression.
F plus F minus minus F plus F
(F + F - - F + F)
minus minus stay alone
and then F plus F,
that's going to be the same
as this. So that's
F plus F minus minus F plus
F plus F plus F minus minus
F plus F. So, this long
set of instructions would
give us the next step in
the Koch curve. So, we could
do that and in this
form of an L-system,
the shape would get
larger every time.
I'm going to scale it
down so that it fits on
top of this. So, F
plus, turn up to the left,
plus, two turns to the right,
draw another F, plus, turn
to the left, and so on.
So, these are L-systems.
It's a way specifying
symbolically this process
that we've been doing
all along of taking a line
segment, replacing it
with a bent line segment.
So, those sort of instructions
I think are pretty good
for people because we
know when I say "Take a
line segment, replace it with
a bent line segment," you know
what I mean, and you
do this drawing and repeat.
But if we need to
specify it axiomatically for
a computer, this is way to
do it. So, those are L-systems.
And I should conclude
by mentioning that L-systems are
of interest not only because
they tell us how we would
tell a computer to do this
but they also give
some clue for maybe
how the set of rules to produce
a fractal can be encoded
in some natural system.
Maybe in some developmental
process that makes a tree
or in some genetic code or
something. So, the basic
lesson is similar
to iterated function systems.
Again, we have a simple
rule, just taking F
and replacing it with this
funny expression, and
if we apply that iteratively,
we can make a fractal.
So, L-systems, you can represent
as L-systems all sorts of
fractals, pretty much
any of the mathematical
fractals we've been
working with so far
can be written as L-systems.
And one can prove a bunch
of properties of these
sorts of systems. Again, we
won't do that in this course.
That's a little too far afield,
but there's lots of resources if
you want to read more.
Okay, so the bottom line
is simple geometric processes
iterated make fractals. You
can mathematize those
with IFSs or with L-systems.
And, in the next
subunit, we're going to look at
what happens if we take
these nice, deterministic systems
and add a little bit of randomness
or noise to them.