Is the distance function from a point to the Mandelbrot set computable?

Question

There is at least one result saying that the Mandelbrot set is undecidable, and there might be more, but I think it (or they all) use real computation rather than Turing machines. This makes some sense, as $\mathbb{C}$ is connected, so the only decidable subsets of it are $\{\}$ and $\mathbb{C}$ itself. However, I've been reading about reverse mathematics, and I was wondering if the set is computable in the representations used. The Mandelbrot set is easily seen to be the complement of an effectively open set, and I'd guess asking whether it is separably closed would run into the open problem of are the hyperbolic components dense. This still leaves located closed, so the question follows:

Let $f : \mathbb{Q}[i] \to \mathbb{R} \hspace{.05 in}$ be given by $f(q) := \operatorname{min}(\{d(q,z) : z\in (\operatorname{Mandelbrot set})\})$. Is $f$ computable?

Answer 1

Following [Giusto and Simpson, Located sets and reverse mathematics, J. Symbolic Logic Volume 65, Issue 3 (2000), 1451-1480], the Mandelbrot set $M$ is located if the distance function $f:\mathbb C\rightarrow\mathbb R$, $f(x)=d(x,M)$, exists in the model under consideration, which I assume you take to be the model containing only computable objects.

Such locatedness seems to be the same as Conjecture 4 of [Hertling, Is the Mandelbrot set computable?, Math. Logic Quarterly, 51(1):5-18, 2005]: The function $f:\mathbb C\rightarrow \mathbb R$ is computable.

(Here $f$ is computable if you can compute the value $f(x)$ with any desired precision (in terms of the distance $d$) when you know $x$ with sufficient precision. More precisely, the algorithm that computes $f$ might promise to output a rational interval of length at most $2^{-n}$ containing $f(x)$ once it is told an interval of length $2^{-{g(n)}}$ containing $x$, where $g$ is a computable function on $\mathbb N$ of the algorithm's choosing.)

Now, what happens if we replace $\mathbb C$ by $\mathbb Q[i]$? Could there be a way to compute $f(q)$ using a representation of $q$ as a rational, but nevertheless no way to approximate $f(x)$ given an arbitrary $x$, due to a lack of a useful modulus of continuity in $x\mapsto d(x,M)$?

No, because $|d(x,M)-d(q,M)|\le d(q,x)$.

Conclusion

The question is equivalent to a known-to-be-open question.

Answer 2

I just want to add one small piece of information to Bjørn's answer. The distance function for the Mandelbrot set $M$ is not known to be computable as a map into the reals, but it is computable as a map into the upper reals. This means that we can calculate upper bounds for the distance: given $z \in \mathbb{C}$, the set of all rational upper bounds for $d(x,M)$ is computably enumerable. In many cases (such as drawing algorithms) this is already quite useful.