11
$\begingroup$

Braverman & Yampolsky have shown that there exist noncomputable Julia sets, i.e., there exist $c \in \mathbb{C}$ such that the Julia set of $f(z) = c + z^2$ is not computable. "A set is computable, if, roughly speaking, its image can be generated by a computer with an arbitrary precision."

Braverman, Mark, and Michael Yampolsky. "Non-computable Julia sets." Journal of the American Mathematical Society (2006): 551-578. (PDF download.)

My questions are:

Q. Is an explicit such $c$ known? A computable $c$?

It seems likely these questions are answered, perhaps in the cited paper. If anyone is familiar enough with this line of work to answer, I'd appreciate it.


Answered. The question is answered in the paper Igor identified, particularly in its full version:

Braverman, Mark, and Michael Yampolsky. "Computability of Julia sets." arXiv link. 2007.

They prove there exist computable $c \in \mathbb{C}$ such that the Julia set of $c + z^2$ is not algorithmically computable, and provide an algorithm for computing such a $c$. Under the assumption of a complex dynamics conjecture (due to Buff & Chéritat), they obtain a polynomial-time algorithm for computing such a $c$, i.e., $n$ bits of $c$ can be computed in time polynomial in $n$.

No explicit $c$ is known, as far as I can tell. (Their algorithms would not be easy to implement.)

$\endgroup$
7
$\begingroup$

Constructing such polynomials is the topic of a follow-up paper by Braverman and Yampolsky. (which, apparently, appeared in STOC '07). They don't give an explicit example, but give an algorithm to construct (arbitrarily close) approximations thereto.

$\endgroup$
  • $\begingroup$ Thanks, Igor! The full, arXiv version contains the details. $\endgroup$ – Joseph O'Rourke Jul 7 '15 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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