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?



Is the distance function from a point to the Mandelbrot set computable?
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.


