6
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ (1) The distance function is a Lipshitz map with Lipshitz constant 1, so it has a very easy modulus of continuity. (2) It does not matter whether we consider $\mathbb{Q}[i]$ or $\mathbb{C}$ as the domain of the distance function, since the former is computably dense in the latter. In other words, if we could compute the distance for points in $\mathbb{Q}[i]$ then a straightforward computable limit would give us the distance for points in $\mathbb{C}$. $\endgroup$ Oct 12, 2010 at 13:23
  • $\begingroup$ @Andrej Bauer: Yes, (1) is a good restatement of the inequality above. (2) is also true but only because of (1). $\endgroup$ Oct 12, 2010 at 19:43
  • $\begingroup$ @Bjørn: "only because of (1)", well the general reason why you can extend computable maps from computably dense subsets is not the Lipshitz condition but computable pointwise continuity (actually, computable sequential continuity will do the job too), and that's a weaker condition. $\endgroup$ Oct 13, 2010 at 4:47
5
$\begingroup$

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.

$\endgroup$

Your Answer

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