Constructing non-computable Julia sets

ABSTRACT

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 Juliasets with computable parameters. Moreover, assuming a widely believed conjecture in Complex Dynamics, we give a poly-time algorithm forcomputing a number c such that the Julia set J_{z²+c z} is non-computable.

In contrast with these results, we show that the filled Julia set of a polynomial is always computable.

REFERENCES

• 1: Eugene Asarin , Oded Maler , Amir Pnueli, Reachability analysis of dynamical systems having piecewise-constant derivatives, Theoretical Computer Science, v.138 n.1, p.35-65, Feb. 6, 1995 [doi>10.1016/0304-3975(94)00228-B]
• 2: S. Banach and S. Mazur. Sur les fonctions calculables. Ann. Polon. Math., 16, 1937.
• 3: I. Binder, M. Braverman, and M. Yampolsky. Filled julia sets with empty interior are computable. Journ. of FoCM, to appear, 2007.
• 4: E. Bishop and D.S. Bridges. Constructive Analysis. Springer-Verlag, Berlin, 1985.
• 5: Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: V. Brattka. Plottable real number functions. In Marc Daumas and et al., editors, RNC'5 Real Numbers and Computers, pages 13--30. INRIA, September 2003.
• 7: Vasco Brattka , Klaus Weihrauch, Computability on subsets of Euclidean space I: closed and compact subsets, Theoretical Computer Science, v.219 n.1-2, p.65-93, May 28, 1999 [doi>10.1016/S0304-3975(98)00284-9]
• 8: M. Braverman. Hyperbolic Julia sets are poly-time computable. Electr. Notes Theor. Comput. Sci., 120:17--30, 2005.
• 9: Mark Braverman, On the Complexity of Real Functions, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.155-164, October 23-25, 2005 [doi>10.1109/SFCS.2005.58]
• 10: M. Braverman. Parabolic julia sets are polynomial time computable. Nonlinearity, 19(6):1383--1401, 2006.
• 11: M. Braverman and M. Yampolsky. Computability of Julia sets. e-print: http://www.arxiv.org/abs/math.DS/0610340, 2006.
• 12: M. Braverman and M. Yampolsky. Non-computable Julia sets. Journ. Amer. Math. Soc., 19(3):551--578, 2006.
• 13: X. Buff and A. Chéritat. The Brjuno function continuously estimates the size of quadratic Siegel disks. Annals of Math., 164(1):265--312, 2006.
• 14: P. Collins. On the computability of reachable and invariant sets. In IEEE Conf. on Decision and Control, pages 4187--4192, 2005.
• 15: A. Douady and J.H. Hubbard. Etude dynamique des polynomes complexes: I-II. Technical Report 84-02,85-04, Pub. Math. d'Orsay, 1984.
• 16: Peter Hertling, An effective Riemann mapping theorem, Theoretical Computer Science, v.219 n.1-2, p.225-265, May 28, 1999 [doi>10.1016/S0304-3975(98)00290-4]
• 17: A. Katok and B. Hasselblatt. Introduction to the modern theory of dynamical systems. Cambridge University Press, Cambridge, 1995.
• 18: Ker-I Ko, Complexity theory of real functions, Birkhauser Boston Inc., Cambridge, MA, 1991
• 19: Pascal Koiran , Michel Cosnard , Max Garzon, Computability with low-dimensional dynamical systems, Theoretical Computer Science, v.132 n.1-2, p.113-128, Sept. 26, 1994 [doi>10.1016/0304-3975(94)90229-1]
• 20: Pascal Koiran , Cristopher Moore, Closed-form analytic maps in one and two dimensions can simulate universal Turing machines, Theoretical Computer Science, v.210 n.1, p.217-223, Jan. 6, 1999 [doi>10.1016/S0304-3975(98)00117-0]
• 21: D. Lacombe. Classes récursivement fermés et fonctions majorantes. C. R. Acad. Sci. Paris, 240:716--718, 1955.
• 22: S. Marmi, P. Moussa, and J.C. Yoccoz. The Brjuno functions and their regularity properties. Commun. Math. Phys., 186:265--293, 1997.
• 23: S. Mazur. Computable analysis, volume 33. Rosprawy Matematyczne, Warsaw, 1963.
• 24: J. Milnor. Dynamics in one complex variable. Introductory lectures. Princeton University Press, 3rd edition, 2006.
• 25: C. Moore. Unpredictability and undecidability in dynamical systems. Phys. Rev. Lett., 64:2354--2357, 1990.
• 26: R. Rettinger. A fast algorithm for julia sets of hyperbolic rational functions. Electr. Notes Theor. Comput. Sci., 120:145--157, 2005.
• 27: Robert Rettinger , Klaus Weihrauch, The computational complexity of some julia sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780570]
• 28: A.M. Turing. On computable numbers, with an application to the entscheidungs problem. Proceedings, London Mathematical Society, pages 230--265, 1936.
• 29: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 30: A. Yao. Classical physics and the Church-Turing Thesis. Technical Report TR02-062, Electronic Colloquium on Computational Complexity (ECCC), 2002.
• 31: Ning Zhong, Recursively enumerable subsets of Rq in two computing models: Blum-Shub-Smale machine and Turing machine, Theoretical Computer Science, v.197 n.1-2, p.79-94, May 15, 1998 [doi>10.1016/S0304-3975(97)00008-X]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
Julia sets, computability, dynamical systems, real computation