A fractal

Now let's try to do something more interesting. Begin with a straight segment (command ``F''). Now remove the middle third of the segment, and replace it with the top two sides of an equilateral triangle. Since the overall figure produced by the turtle is always rescaled to unit size, we can represent the latter with the command ``F LFRRFL F'', where the part LFRRFL describes the bump we added. Of course, we have to set the angle the turtle turns to be 60, and we need the RR in the middle to make a 120 turn.

> 
  SetTurtleAngle(60);
  plots[display](array([TurtleCmd(`F`), TurtleCmd(`FLFRRFLF`)]));

Now let's put a bump on each segment in the second figure. This is the same as replacing each F in the second command with ``FLFRRFLF'', giving us

> 
  TurtleCmd(`FLFRRFLF L FLFRRFLF RR FLFRRFLF L FLFRRFLF`);

Putting bumps on each segment of that figure, and then adding smaller bumps to each segment of that figure, and then doing it yet again, gives us a very wiggly curve:

Notice that the width of each bump added is 1/3 of the one added previously, so by the time we have done this five times (as in the previous figure), the bumps are 1/3⁵ the size of the whole figure. If we continue much more, the changes become smaller than we can discern. It should be clear that there is a well defined ``curve'' which corresponds to the limit of doing this process infinitely often. We shall try to make this statement a little more precise now.

Let $\Cal{K}_0$ be the figure at the 0-th stage, that is, the straight segment, and let $\Cal{K}_1$ be the curve after we have added one bump. In general, let $\Cal{K}_n$ be the curve after the n-th step. We claim that there is a well-defined limit curve $\Cal{K}_\infty = \lim_{n\rightarrow\infty} \Cal{K}_n$.

To make sense of this statement, we need a way to measure how far apart two sets in the plane are. That is, if S₁ and S₂ are two sets of points, we shall define the ``Hausdorff distance'' between S₁ and S₂ as follows. First, define the distance from a point x to a set S as the distance between x and the closest point in S, that is

d (x, S) = $$\inf_{y\in S}^{}$$d (x, y).

Then let the Hausdorff distance between S₁ and S₂ be the greatest of all such distances, as x moves through each set.

d (S₁, S₂) = max$$\set$$$$\sup_{x\in S_1}^{}$$d (x, S₂),    $$\sup_{x\in S_2}^{}$$d (x, S₁)

Once you have absorbed that, it should be simple to see that that we now need only show that for any $\epsilon$ > 0, we can always find N sufficiently large so that d ($\Cal{K}_N, \Cal{K}_n) < \epsilon$ for all n > N. This follows from the fact that the size of the bumps goes down by a factor of 1/3 at each stage. Thus, d ($\Cal{K}_n, \Cal{K}_{n+1}) < 1/3^{n+1}$, and

d ($$\Cal{K}_N, \Cal{K}_n) < \sum_{j=N}^n 1/3^j < \frac{1}{2\cdot 3^{N-1}}.$$

This means that the sets $\Cal{K}_n$ form a Cauchy sequence, and so there is a well-defined limit set $\Cal{K}_\infty$.^5.3

Now, this ``curve'' $\Cal{K}_\infty$ has some interesting properties. First, notice that the distance in the plane from one end to the other is 1, but the ``curve'' itself is infinitely long. In fact, the length of any small part of the curve is infinite, as well. We can see that by examining how the lengths of each $\Cal{K}_n$ varies with n:

curve	# segments	segment length	total length
$\Cal{K}_0$	1	1	1
$\Cal{K}_1$	4	1/3	4/3
$\Cal{K}_2$	16	1/9	16/9
$\Cal{K}_3$	64	1/27	64/27
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$\Cal{K}_n$	4n	1/3n	4n/3n

At each stage, every segment is replaced by four segments 1/3 as long. Thus, the overall length grows by a factor of 4/3 at each step. For any finite length $\ell$ we choose, we can find an n so that the length of $\Cal{K}_n$ is greater than $\ell$.

Note also that $\Cal{K}_\infty$ is nowhere differentiable: it has corners densely throughout it. Finally, note that $\Cal{K}_\infty$ is ``self-similar''. By this we mean that if you take any small piece of it, no matter how small, there is a small copy of the whole $\Cal{K}_\infty$ within it.

The curve $\Cal{K}_\infty$ is an example of a fractal.^5.4 This particular example is called the von Koch curve, and was discovered by H. von Koch in the late nineteenth century. This curve, and others like it, caused quite a stir in the mathematics community at the time because of its peculiar properties. We will explore additional fractals and some of their properties in the remainder of this chapter.

The particular way we generated the Koch curve is called an ``L-system'' or a ``Lindenmeyer system''. In an L-system, one begins with an initial figure (called the initiator), and a set of rules for modifying any figure to obtain the next in the sequence. In our example above, the initiatior was a straight segment (F) and the recursion rule was F $\mapsto$ FLFRRFLF.

Footnotes

....^5.3

In order to completely finish this argument, we need to know that the collection of all compact sets forms a complete metric space if we use the Hausdorff distance as our metric. Without this fact, we don't know that the limiting object $\Cal{K}_\infty$ is also a compact set in the plane. Although this isn't difficult to prove (and is nearly self-evident), we will skip over this detail.

... fractal.^5.4

The term ``fractal'' was coined by Benoit Mandelbrot in the late 1970s. Unfortunately, there is no universally accepted definition for this term. Some definitions require that a fractal be a self-similar object, but this excludes one of the most well-known examples of a fractal, the Mandelbrot set, which is only approximately self-similar. We shall take it to mean any set whose Hausdorff dimension exceeds its topological dimension (we will see what this means in section 5).