21
$\begingroup$

The Mandelbrot set is a beautiful creature in Mathematics.

There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense.

However, what concerns me is the fact that it is not even recursively enumerable - simply because the set is uncountable. This could be resolved by requiring some sort of finite representation of the points.

Furthermore, although we know for sure that a lot of points belong to the set and others do not, there are also a lot of points whose membership in the set we don't know. All the images we've seen so far may include a lot of points that "up to n iterations kept in bound," but those points may not actually belong to the set.

So, for a given point with a finite presentation, the problem "Does this point belong to the set?" has not been proved to be decidable yet, if I am right.

Now, in what sense (by which definition) can we say the Mandelbrot set is "computable"?

Improve this question
$\endgroup$
1
  • 10
    $\begingroup$ "However, what concerns me is the fact that it is not even recursively enumerable - simply because the set is uncountable." - that probably shouldn't be what concerns you. After all, tons of really simple sets of points in $\mathbb R^2$ are uncountable. $\mathbb R^2$, for example. $\endgroup$
    – user2357112
    May 18, 2015 at 7:18

2 Answers 2

Reset to default
17
$\begingroup$

There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine similar to a RAM machine, whose access to real numbers is restricted to basic arithmetic and comparisons. Blum and Smale showed that the Mandelbrot set is uncomputable in this model, though its complement can be recursively enumerated using the traditional algorithm used for drawing them.

Another model is computable analysis, in which the Mandelbrot set is probably computable, as shown by Hertling (conditional on a widely believed conjecture, the hyperbolicity conjecture). In this model, computing the Mandelbrot set means being able to compute an approximation to the Mandelbrot set, within any desired accuracy (for the exact definition, see the reference on computable analysis).

Why is it, then, that the computer seems to be able to draw the Mandelbrot set? The main difficulty in showing that the traditional algorithm works is that it is difficult to tell in advance how many iterations to run before we decide that the point belongs to the set. Hertling shows that if the widely believed hyperbolicity conjecture holds, then there is a reasonable such bound. Presumably, the programs simply wait long enough; or they don't wait long enough, but only get a small fraction of the points wrong.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I had a look at both models, but both are not good enough for me... Since the best thing next to finite is compact, and Mandelbrot set is compact, I think there should be a model that claim it is "computable compact" somehow. For sets like $R$ we can say "computable locally compact". $\endgroup$
    – Earth Engine
    May 19, 2015 at 2:12
  • $\begingroup$ @EarthEngine I am not sure what you mean, but the notion of computability from computable analysis seems to give exactly what one should mean by "computably compact": You can compute finite open covers of the set that approximate it arbitrarily closely (with respect to Hausdorff distance). If the hyperbolicity conjecture holds, then this is true for the Mandelbrot set. $\endgroup$
    – Lasse Rempe
    Jan 5 at 1:00
11
$\begingroup$

Basically, the Mandelbrot set is not computable (as far as we know). The fact that you see images does not mean it is computable. Those images are computing using an approximation: if the process runs longer than a set threshold, as a heuristic, the code assumes that it will never terminate. This heuristic can be wrong, and as a result those images might not be 100% accurate. In other words, those pictures are not an image of "the" Mandelbrot set; they are of an approximation to the Mandelbrot set.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The fact that we compute only approximations is not the problem, I would think. The issue would be more whether these approximations converge to some limit that is the Mandelbrot set if you increase computation time. Do I misunderstand you? $\endgroup$
    – babou
    May 18, 2015 at 12:04
  • 1
    $\begingroup$ @babou, why would that be the issue? I can give you an algorithm that is an approximation to the Halting problem, i.e., it converges in the limit to the correct solution to the Halting problem -- but that's not enough that we'd consider the Halting problem to be computable. I don't think you misunderstand me. $\endgroup$
    – D.W. ♦
    May 18, 2015 at 15:22
  • 1
    $\begingroup$ I must be confused somewhere. I was under the impression that infinite objects can be considered computable if they are the limit of an infinite sequence of computable ones, with some specific conditions on how convergence to the limit must behave. There seems to be a hole in my understanding. $\endgroup$
    – babou
    May 18, 2015 at 17:01
  • $\begingroup$ @babou, OK. I don't doubt your memory/understanding. I hadn't heard of that notion of computability, but I believe you. $\endgroup$
    – D.W. ♦
    May 18, 2015 at 18:09
  • $\begingroup$ First, you should always doubt my memory/understanding. Much of what is discussed here is not in my area of (former) expertise. Actually my understanding relies on what little I read on computable real, which I understood as being computable with any required precision in a uniform way. Then there is my older semantic understanding of infinite structures as limits of finite structures in partially ordered sets, though I am not sure how the two are connected. $\endgroup$
    – babou
    May 19, 2015 at 0:08

Your Answer

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

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