17
$\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"?

$\endgroup$
  • 9
    $\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 '15 at 7:18
13
$\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.

$\endgroup$
  • $\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 '15 at 2:12
10
$\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.

$\endgroup$
  • $\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 '15 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 '15 at 15:22
  • $\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 '15 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 '15 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 '15 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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