TY - GEN

T1 - Constructing non-computable Julia sets

AU - Braverman, Mark

AU - Yampolsky, Michael

PY - 2007/10/30

Y1 - 2007/10/30

N2 - 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 .

AB - 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 .

UR - http://www.scopus.com/inward/record.url?scp=35448960043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448960043&partnerID=8YFLogxK

U2 - 10.1145/1250790.1250893

DO - 10.1145/1250790.1250893

M3 - Conference contribution

AN - SCOPUS:35448960043

SN - 1595936319

SN - 9781595936318

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 709

EP - 716

BT - STOC'07

T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing

Y2 - 11 June 2007 through 13 June 2007

ER -