Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
(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}$. –  Andrej Bauer Oct 12 '10 at 13:23
    
@Andrej Bauer: Yes, (1) is a good restatement of the inequality above. (2) is also true but only because of (1). –  Bjørn Kjos-Hanssen Oct 12 '10 at 19:43
    
@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. –  Andrej Bauer Oct 13 '10 at 4:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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