<p>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.</p>

<p>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. <a href="http://en.wikipedia.org/wiki/Mandelbrot_set" rel="nofollow">Mandelbrot Set</a> 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. </p>

<p>I suggest having a look at the dynamical systems, <a href="http://en.wikipedia.org/wiki/Fractal" rel="nofollow">fractals</a>, and (mathematical) <a href="http://en.wikipedia.org/wiki/Chaos_theory" rel="nofollow">chaos theory</a> books.</p>

<p>I would also suggest <a href="http://www.cs.toronto.edu/~mbraverm/" rel="nofollow">Mark Braverman</a>'s <a href="http://www.cs.toronto.edu/~mbraverm/Pub-all.html" rel="nofollow">papers</a> on computability/non-computability of <a href="http://en.wikipedia.org/wiki/Julia_set" rel="nofollow">Julia sets</a> and his book with <a href="http://www.math.toronto.edu/yampol/" rel="nofollow">Michael Yampolsky</a>: <a href="http://www.springer.com/math/cse/book/978-3-540-68546-3" rel="nofollow">Computability of Julia Sets</a>, Springer 2008.</p>

CC BY-SA 2.5
2010-11-16T14:21:28.537Z
2010-11-16T14:49:09.533Z
2010-11-16T14:49:09.533Z
Kaveh
<p>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.</p>

<p>For example: <a href="http://www.cs.iastate.edu/~lutz/=PAPERS/dpssf.pdf" rel="nofollow">Dimension of points in self-similar fractals</a>, Lutz and Mayordomo, SIAM Jnl Computing, 2008.</p>

CC BY-SA 2.5
2010-11-17T03:49:59.980Z
2010-11-17T03:49:59.980Z
Aaron Sterling
<p>Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number.</p>

<p>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}</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-16T14:18:42.303Z
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.
Andrej Bauer
CC BY-SA 2.5
2010-11-16T14:23:54.687Z
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.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-16T14:28:11.570Z
@Andrej: I think this was the topic of Mark Braverman's thesis, it is probably available online on his [website](http://www.cs.toronto.edu/~mbraverm/). He has also coauthored a book on [computability of Julia sets](http://www.springer.com/math/cse/book/978-3-540-68546-3).
Kaveh
CC BY-SA 2.5
2010-11-16T14:37:00.717Z
Is this how the universe came into existence?
Phil
CC BY-SA 2.5
2010-11-16T14:42:25.047Z
@Phil: you might want to ask *that question* on Physics.SE ;)
Kaveh
CC BY-SA 2.5
2010-11-16T12:59:27.847Z
2010-11-16T13:05:48.950Z
2010-11-16T13:05:48.950Z
Mohammad Al-Turkistany
<p>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.</p>
<p>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: <a href="https://arxiv.org/pdf/1912.00284.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1912.00284.pdf</a></p>

CC BY-SA 4.0
2021-11-23T22:53:00.353Z
2021-11-23T22:53:00.353Z
Eric Allender
<p>The <strong>simplest algorithm</strong> for generating a representation of the Mandelbrot set is known as the "escape time" algorithm
You will find it here:
<a href="http://en.wikipedia.org/wiki/Mandelbrot_set#Escape_time_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Mandelbrot_set#Escape_time_algorithm</a></p>

<p><strong>The images of the <a href="http://en.wikipedia.org/wiki/Mandelbrot_set" rel="nofollow">set</a> you have seen is a plot of thousand of points.</strong></p>

<p>It is a <a href="http://en.wikipedia.org/wiki/Recursion" rel="nofollow">recursive function</a> 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.</p>

CC BY-SA 2.5
2010-11-16T17:39:37.103Z
2010-11-17T03:21:42.570Z
2010-11-17T03:21:42.570Z
Deyaa
<p>To a large extent, the answer will depend on exactly what you mean by "information". The fractal has very low <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="noreferrer">Kolmogorov complexity</a>, 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 <a href="http://en.wikipedia.org/wiki/Cellular_automata" rel="noreferrer">cellular automata</a> and <a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="noreferrer">Conway's game of life</a> 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.</p>

CC BY-SA 2.5
2010-11-18T03:30:50.787Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-11-18T04:03:05.517Z
@Joshua: Good point. The talk about pictures confuses the matter, since presumable any picture has a finite resolution.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-16T13:22:28.250Z
2010-11-16T13:22:28.250Z
Joe Fitzsimons
<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-11-16T14:45:41.363Z
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?
Kaveh
CC BY-SA 2.5
2010-11-16T14:54:17.933Z
btw, perhaps this question is more suitable on [Math.SE](http://math.stackexchange.com/). Please read the [cstheory FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science).
Kaveh
<it.information-theory><mandelbrot>
Where does the information in a fractal come from?
Phil
# Where does the information in a fractal come from?

(Asked by: username_0 on 2010-11-16)

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?

**Tags:** it.information-theory, mandelbrot

> **Comments:**
> **username_1**: 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?  
> **username_1**: btw, perhaps this question is more suitable on [Math.SE](http://math.stackexchange.com/). Please read the [cstheory FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science).  

---

## 6 answers

### Answer by username_7 on 2010-11-16. Score: 21 | Accepted answer

To a large extent, the answer will depend on exactly what you mean by "information". The fractal has very low [Kolmogorov complexity](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Cellular_automata) and [Conway's game of life](http://en.wikipedia.org/wiki/Conway%27s_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.

> **Comments:**
> **username_8**: 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.  
> **username_7**: @Joshua: Good point. The talk about pictures confuses the matter, since presumable any picture has a finite resolution.  

---

### Answer by username_1 on 2010-11-16. Score: 8

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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Fractal), and (mathematical) [chaos theory](http://en.wikipedia.org/wiki/Chaos_theory) books.

I would also suggest [Mark Braverman](http://www.cs.toronto.edu/~mbraverm/)'s [papers](http://www.cs.toronto.edu/~mbraverm/Pub-all.html) on computability/non-computability of [Julia sets](http://en.wikipedia.org/wiki/Julia_set) and his book with [Michael Yampolsky](http://www.math.toronto.edu/yampol/): [Computability of Julia Sets](http://www.springer.com/math/cse/book/978-3-540-68546-3), Springer 2008.


---

### Answer by username_2 on 2010-11-17. Score: 7

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](http://www.cs.iastate.edu/~lutz/=PAPERS/dpssf.pdf), Lutz and Mayordomo, SIAM Jnl Computing, 2008.


---

### Answer by username_3 on 2010-11-16. Score: 5

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.

> **Comments:**
> **username_4**: 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.  
> **username_3**: 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.  
> **username_1**: @Andrej: I think this was the topic of Mark Braverman's thesis, it is probably available online on his [website](http://www.cs.toronto.edu/~mbraverm/). He has also coauthored a book on [computability of Julia sets](http://www.springer.com/math/cse/book/978-3-540-68546-3).  
> **username_0**: Is this how the universe came into existence?  
> **username_1**: @username_0: you might want to ask *that question* on Physics.SE ;)  

---

### Answer by username_5 on 2021-11-23. Score: 3

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>


---

### Answer by username_6 on 2010-11-16. Score: 0

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](http://en.wikipedia.org/wiki/Mandelbrot_set) you have seen is a plot of thousand of points.**

It is a [recursive function](http://en.wikipedia.org/wiki/Recursion) 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.


---

