9
$\begingroup$

When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be stored somewhere. Then I found that the Mandelbrot is generated by computational processes based upon mathematics in the area of complex numbers.

However, my question still holds, where did the information come from? The nice picture wasn't input when the program was written, where did the information for this picture come from?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ There doesn't need to be an input if the output does not change w.r.t. inputs, you can put all of that inside the program. I guess your question is how a simple rule like the equation over complex numbers for Mandelbrot set can generate a complex picture like Mandelbrot set. Am I right? $\endgroup$
    – Kaveh
    Commented Nov 16, 2010 at 14:45
  • $\begingroup$ btw, perhaps this question is more suitable on Math.SE. Please read the cstheory FAQ. $\endgroup$
    – Kaveh
    Commented Nov 16, 2010 at 14:54

6 Answers 6

Reset to default
21
$\begingroup$

To a large extent, the answer will depend on exactly what you mean by "information". The fractal has very low Kolmogorov complexity, as there is a very simple rule describing how you generate it. So in one sense, it contains very little information. On the other hand, a picture of such a fractal appears very complicated, even though there is a simple rule underlying it. This is not at all uncommon. Many times very simple rules give rise to very complex behavior. Examples of this range from cellular automata and Conway's game of life to things like the apparent complexity in the digits of $\pi$. The fact is that this new representation doesn't contain anything fundamentally new, but is rather a less efficient expression of the same object.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ As pointed out by turkistany, the Mandelbrot set is undecidable over the reals. So although it can be enumerated by a finite program, it can't be decided. One might say it has low "c.e. Kolmogorov complexity," but it's Kolmogorov complexity in some traditional sense (there are of course issues of reals vs bits, etc.) might in fact be quite high. $\endgroup$
    – Joshua Grochow
    Commented Nov 18, 2010 at 3:30
  • 3
    $\begingroup$ @Joshua: Good point. The talk about pictures confuses the matter, since presumable any picture has a finite resolution. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 18, 2010 at 4:03
8
$\begingroup$

As Joe said the answer highly depends on what you mean by information. I guess you don't mean the definition in computer science but are using it as the best word for expressing some intuitive concept.

But if your question is about how a simple rule can generate such a complex structure then the answer is because it is defined recursively, i.e. Mandelbrot Set is a fix-point as mentioned by Turkistany. Recursive definitions can increase the complexity of a set (membership of a point in the set, distance from the set, ...) considerably. The original equation over complex numbers is not very complicated, but recursive use of it (or almost any other equation) can create high complexity sets. So I would say that the complexity of the set is coming from the recursiveness/fixed-point.

I suggest having a look at the dynamical systems, fractals, and (mathematical) chaos theory books.

I would also suggest Mark Braverman's papers on computability/non-computability of Julia sets and his book with Michael Yampolsky: Computability of Julia Sets, Springer 2008.

Improve this answer
$\endgroup$
7
$\begingroup$

The information content of self-similar fractals is a research topic of current interest in computable analysis. In particular, by generalizing Hausdorff dimension to a concept of dimension-relative-to-computational-resource-bounds allows one to talk about the dimension (information content) of individual points, or sets of points, within the fractal, instead of just the overall geometric dimension of the fractal itself.

For example: Dimension of points in self-similar fractals, Lutz and Mayordomo, SIAM Jnl Computing, 2008.

Improve this answer
$\endgroup$
5
$\begingroup$

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number.

Mandelbrot set $M$ is the of set complex numbers $M=${$c |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is bounded}

Equivalently for all $n$, $P^n_c (0)$ has a complex magnitude less than 2.

The information in Mandelbrot set comes from the fact that membership in the set $M$ is undecidable. This means that there is no algorithm that can predict whether a given complex number $c$ is in Mandelbrot set or not. This means that the membership of a given complex number $c$ in $M$ is random to any algorithm over complex numbers and reflects the unpredictability of the evolution of simple rules over complex numbers.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Can you please provide a reference for the fact that the membership relation for $M$ is undecidable? Your reasoning is very fast and loose, and you use words like "random to any algorithm" in unclear ways. $\endgroup$
    – Andrej Bauer
    Commented Nov 16, 2010 at 14:18
  • 1
    $\begingroup$ Check the chapter on Algebraic computation models in Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. Also, my notion of randomness is based on algorithmic unpredictability. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 16, 2010 at 14:23
  • 1
    $\begingroup$ @Andrej: I think this was the topic of Mark Braverman's thesis, it is probably available online on his website. He has also coauthored a book on computability of Julia sets. $\endgroup$
    – Kaveh
    Commented Nov 16, 2010 at 14:28
  • $\begingroup$ Is this how the universe came into existence? $\endgroup$
    – Phil
    Commented Nov 16, 2010 at 14:37
  • $\begingroup$ @Phil: you might want to ask that question on Physics.SE ;) $\endgroup$
    – Kaveh
    Commented Nov 16, 2010 at 14:42
3
$\begingroup$

Although this thread of questions and answers is about 11 years old now, I am prompted to add some additional information, because a student in one of my classes directed my attention to this discussion.

It turns out that the connection between Kolmogorov complexity and fractal dimension (Hausdorff dimension) is much closer than was known when this discussion originally appeared. Lutz and Lutz showed that the Hausdorff dimension of a set can be characterized EXACTLY in terms of the (relativized) Kolmogorov complexity of the (binary sequences representing the) numbers in the set. For a high-level survey of these results, you may wish to read this article: https://arxiv.org/pdf/1912.00284.pdf

Improve this answer
$\endgroup$
0
$\begingroup$

The simplest algorithm for generating a representation of the Mandelbrot set is known as the "escape time" algorithm You will find it here: http://en.wikipedia.org/wiki/Mandelbrot_set#Escape_time_algorithm

The images of the set you have seen is a plot of thousand of points.

It is a recursive function and its definition is: method of defining functions in which the function being defined is applied within its own definition; specifically it is defining an infinite statement using finite components.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.