Constructing non-computable Julia sets

Mark Braverman, Michael Yampolsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


While most polynomial Julia sets are computable, it has been recently shown [12] that there exist non-computable Julia sets. The proof was non-constructive, and indeed there were doubts as to whether specific examples of parameters with non-computable Julia sets could be constructed. It was also unknown whether the non-computability proof can be extended to the filled Julia sets. In this paper we give an answer to both of these questions, which were the main open problems concerning the computability of polynomial Julia sets. We show how to construct a specific polynomial with a non-computable Julia set. In fact, in the case of Julia sets of quadratic polynomials we give a precise characterization of Julia sets with computable parameters. Moreover, assuming a widely believed conjecture in Complex Dynamics, we give a poly-time algorithm for computing a number c such that the Julia set Jz2+cz is non-computable. In contrast with these results, we show that the filled Julia set of a polynomial is always computabl .

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Number of pages8
StatePublished - 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Software


  • Computability
  • Dynamical systems
  • Julia sets
  • Real computation


Dive into the research topics of 'Constructing non-computable Julia sets'. Together they form a unique fingerprint.

Cite this