The Mandelbrot set

The Mandelbrot set is often held up as an example of how amazing complexity can be generated from a simple dynamical system.  In comments to my previous posts on the information content or Kolmogorov complexity of the brain, it was brought up as an example of how the brain could be very complex yet still be fully specified by the genome.  While, I agree with this premise, the Mandelbrot set is not the best example to show this.   Now, the Mandelbrot set is a beautiful example of how you can generate incredibly complex fractal landscapes using a simple algorithm.  However, it takes an uncountably infinite amount of information to specify it.

Let’s be more precise.  Consider the iterative map .  Pick any complex number for and iterate the map starting at .  The ensuing iterates or orbit will either go to infinity or stay bounded.  The Mandelbrot set is the set of all points that you use for that stay bounded.  In essence, it consists of all complex numbers such that the series , , stays bounded.  You can immediately rule out some numbers.  You know that zero will always stay bounded and you also know that any number with absolute magnitude greater than 2 will also go to infinity.  In fact, to compute the Mandelbrot set, you just have to see if any iterate exceeds 2 because after that you know it is gone.  The question then is what happens in between and it turns out that the boundary of the Mandelbrot set is this beautiful fractal shape that looks like sea horses within sea horses and so forth.

The question then is how much information do you need to construct the Mandelbrot set.  The answer as proved by Blum, Cucker, Shub, and Smale (see their book Complexity and Real Computation), is that the Mandelbrot set is undecidable.  There is no algorithm to obtain the boundaries of the Mandelbrot set.  In other words, you would need an uncountable amount of information to specify it.  The beautiful pictures we see, as shown above, are only approximations to the set.

However, I am not hostile to the idea that simple things can generate complexity.  One could say that my career is based on this idea.  It is what chaos theory is all about.  I use the argument all the time.  I’m just saying that the Mandelbrot set is not a great example.  Perhaps, a better example is to say let’s consider the logistic map on real numbers .  If r is between zero and one, then all orbits will eventually go to zero but as you increase r, the nature of the orbits will change and eventually you’ll reach a periodic doubling cascade to chaos. If you choose an r that is slightly bigger than 3.57 then you’ll get chaos.  This implies that small changes to the initial conditions will give you completely different results and also that if you just plot the iterates coming out of the map, they will seem to have no apparent pattern.  If you were to naively estimate the complexity or information content of the orbit, you could be led to believe that it has high information content even though the Kolmogorov complexity is actually quite small and is given by the logistic map and the initial condition.  However, this may also not be the greatest example because there are ways to deduce that the orbit came from a low dimensional chaotic system rather than a high dimensional system.