Is the Mandelbrot set computable?

Question

This is a weakened version of Is the measure induced by the Mandelbrot set computable on rational rectangles? ;

Given a (computable, or rational) rectangle in the complex plane, is it computable whether:

1. The rectangle is contained within the Mandelbrot set?
2. The rectangle is disjoint from the Mandelbrot set?
3. other

The above-referenced question asked whether the measure of the intersection of a (computable) rectangle and the Mandelbrot set is computable.

Given a (computable) complex number, it is probably computable whether that number is in the Mandelbrot set, but I'm not even sure of that. If that is insoluble, it does not necessarily make my question (for an open rectangle) insoluble.

Answer 1

Given a (computable) complex number, it is probably computable whether that number is in the Mandelbrot set, but I'm not even sure of that. If that is insoluble, it does not necessarily make my question (for an open rectangle) insoluble.

You are wrong about that. (In a pedantic way that tells you nothing about the Mandelbrot set.)

A computable real number is any number such that there exists a Turing machine that takes in n and returns the n'th digit.

The only reasonable way to take in an arbitrary computable number is as such a Turing machine. 0.25 is in the Mandelbrot set. But 0.25+e isn't for any e>0. So imagine a Turing machine that returns 0.25000... The n'th digit (n>2) is computed by simulating an arbitrary Turing machine for n steps, and returning 0 if it hasn't halted yet.

The argument is the same on a closed unit disk.

The Mandelbrot set might be computable over rational or algebraic points for all I know.

Answer 2

As already mentioned, it makes no real sense to ask whether one can decide whether an arbitrary (say computable) number is in the Mandelbrot set or not, unless you allow infinite-precision operations (see below).

The only really sensible notion for computability of the Mandelbrot set is that of computable analysis. Essentially, this means we ask: given a small number $\varepsilon$, can we draw a picture of the Mandelbrot that is accurate up to scale $\varepsilon$? Equivalently, given a complex number, can we estimate its distance to the Mandelbrot set up to a desired error?

In terms of your question, this means you should not ask whether for a given rectangle you can decide about its intersection with the Mandelbrot set, but rather ask the following: Given a closed rectangle $R_1$ and a (slightly) larger open rectangle $R_2$ that contains it, can I find an algorithm that always halts and always outputs $0$ when $R_2$ does not intersect the Mandelbrot set and always outputs $1$ when $R_1$ does intersect the Mandelbrot set (without prescribing what happens in the remaining case)?

This would allow us to compute either the distance function to the Mandelbrot set up to any accuracy, or equivalently to compute an accurate (up to a given $\varepsilon$) computer image thereof.

As far as I know, the best answer to this question is given by Hertling ("Is the Mandelbrot set computable", 2004). He shows that the answer is positive assuming the famous "density of hyperbolicity" conjecture, which says that parameters for which there is an attracting periodic orbit are dense in the Mandelbrot set.

The proof then is relatively straightforward, and can be explained as follows. Firstly, if we are given a point in the complement of the Mandelbrot set, then we can tell that this is so only knowing the coordinates up to some finite precision, and in particular we get a lower bound on the distance to the Mandelbrot set from this. Moreover, the time this takes and the size of the lower bound only depend on the distance of our parameter to the Mandelbrot set. (This is essentially just a compactness/continuity argument, although better and more elaborate estimates can be done using tools from complex analysis.) What this means is that we can recursively enumerate a collection of open balls whose union is the complement of the Mandelbrot set.

The same is true for the set of hyperbolic parameters, using the fact that one can compute an approximation to the set of roots of a given polynomial (although I think Hertling omits some details here).

Finally, one can recursively enumerate a dense set of parameters in the boundary of the Mandelbrot set (e.g. by enumerating all parameters for which the crtical point is pre-periodic).

Now, suppose that $R_1$ and $R_2$ are as above. Consider an algorithm that, in parallel, enumerates the three sequences above: balls covering the complement of the Mandelbrot set, balls covering the hyperbolic parameters, and a dense subset of the boundary of the Mandelbrot set. If $R_1\cap M = \emptyset$, then at some point the balls in the first sequence will cover all of $\overline{B_1}$, and the algorithm can detect this. Likewise if $R_1$ consists of hyperbolic parameters. On the other hand, if $R_2$ intersects the boundary of the Mandelbrot set, then eventually our algorithm will find out that this is so. In any of these cases, the algorithm will stop and declare this outcome.

If the hyperbolicity conjecture holds, then (at least) one of these three possibilities must hold, and therefore we have found the desired algorithm.

(Note that it is possible that $R_2$ intersects the boundary of the Mandelbrot set, while $R_1$ does not; in this case, we do not know which answer the machine will give, but this does not matter since the machine will still halt, and we did not require it to return a specific answer in this case.)

---

On the other hand, there is a more algebraic model of computation, the Blum-Shub-Smale model, where it is possible to make computations with perfect precision. According to this, the Mandelbrot set is not computable! But also e.g. the graph of the exponential function is not computable, although one can make very good pictures of it. So it does not really say very much about our ability to make accuracte computer pictures.

Of course, you can also ask the following: Given a complex number with rational real and imaginary parts, is it in the Mandelbrot set? This is a decision problem in the usual sense of information theory, and you can ask about its computability. But it is not clear at all that this is a good problem, since it is not clear at all whether you would expect there to be many rational numbers in the boundary of the Mandelbrot set. Since you can do perfect arithmetic with rational numbers, probably the correct version of this question is the Blum-Shub-Smale one above, where the answer is that it is not computable in this sense.