Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Non-computable Julia sets

Authors: M. Braverman and M. Yampolsky
Journal: J. Amer. Math. Soc. 19 (2006), 551-578
MSC (2000): Primary 37F50; Secondary 68Q17
Published electronically: December 22, 2005
MathSciNet review: 2220099
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that under the definition of computability which is natural from the point of view of applications, there exist non-computable quadratic Julia sets.

References [Enhancements On Off] (What's this?)

  • Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636
  • Artur Avila, Xavier Buff, and Arnaud Chéritat, Siegel disks with smooth boundaries, Acta Math. 193 (2004), no. 1, 1–30. MR 2155030, DOI
  • [BBY1]BBY1 I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at [BBY2]BBY2 I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear.
  • Errett Bishop and Douglas Bridges, Constructive analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. MR 804042
  • [Brv1]thesis M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Proc. CCA 2004., Electr. Notes Theor. Comput. Sci. 120: 17-30 (2005). [Brv2]Brv2 M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at
  • A. D. Brjuno, Analytic form of differential equations. I, II, Trudy Moskov. Mat. Obšč. 25 (1971), 119–262; ibid. 26 (1972), 199–239 (Russian). MR 0377192
  • [BC1]BC2 X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242. [BC2]BC X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
  • Adrien Douady, Does a Julia set depend continuously on the polynomial?, Complex dynamical systems (Cincinnati, OH, 1994) Proc. Sympos. Appl. Math., vol. 49, Amer. Math. Soc., Providence, RI, 1994, pp. 91–138. MR 1315535, DOI
  • A. Douady and J. H. Hubbard, Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 84, Université de Paris-Sud, Département de Mathématiques, Orsay, 1984 (French). MR 762431
  • Adrien Douady and John Hamal Hubbard, On the dynamics of polynomial-like mappings, Ann. Sci. École Norm. Sup. (4) 18 (1985), no. 2, 287–343. MR 816367
  • A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 86756, DOI
  • Ker-I Ko, Complexity theory of real functions, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1137517
  • K. Ko, Polynomial-time computability in analysis, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1271–1317. MR 1673610, DOI
  • Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. I, C. R. Acad. Sci. Paris 240 (1955), 2478–2480 (French). MR 72079
  • S. Mazur, Computable analysis, Rozprawy Mat. 33 (1963), 110. MR 153553
  • S. Marmi, P. Moussa, and J.-C. Yoccoz, The Brjuno functions and their regularity properties, Comm. Math. Phys. 186 (1997), no. 2, 265–293. MR 1462766, DOI
  • Yu. V. Matiyasevich, Desyataya problema Gil′berta, Matematicheskaya Logika i Osnovaniya Matematiki [Monographs in Mathematical Logic and Foundations of Mathematics], vol. 26, VO “Nauka”, Moscow, 1993 (Russian, with Russian summary). MR 1247235
  • Curtis T. McMullen, Complex dynamics and renormalization, Annals of Mathematics Studies, vol. 135, Princeton University Press, Princeton, NJ, 1994. MR 1312365
  • John Milnor, Dynamics in one complex variable, Friedr. Vieweg & Sohn, Braunschweig, 1999. Introductory lectures. MR 1721240
  • C. L. Petersen and S. Zakeri, On the Julia set of a typical quadratic polynomial with a Siegel disk, Ann. of Math. (2) 159 (2004), no. 1, 1–52. MR 2051390, DOI
  • Ch. Pommerenke, Boundary behaviour of conformal maps, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 299, Springer-Verlag, Berlin, 1992. MR 1217706
  • [Ret]Ret R. Retinger. A fast algorithm for Julia sets of hyperbolic rational functions, Proc. of CCA 2004, Electr. Notes Theor. Comput. Sci. 120: 145-157 (2005).
  • Robert Rettinger and Klaus Weihrauch, The computational complexity of some Julia sets, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 177–185. MR 2121048, DOI
  • Steffen Rohde and Michel Zinsmeister, Variation of the conformal radius, J. Anal. Math. 92 (2004), 105–115. MR 2072743, DOI
  • Carl Ludwig Siegel, Iteration of analytic functions, Ann. of Math. (2) 43 (1942), 607–612. MR 7044, DOI
  • [Sip]Sip M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. [Tur]Tur A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265.
  • Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407
  • Jean-Christophe Yoccoz, Théorème de Siegel, nombres de Bruno et polynômes quadratiques, Astérisque 231 (1995), 3–88 (French). Petits diviseurs en dimension $1$. MR 1367353

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 37F50, 68Q17

Retrieve articles in all journals with MSC (2000): 37F50, 68Q17

Additional Information

M. Braverman
Affiliation: Department of Computer Science, University of Toronto, Toronto, ON M5S 3G4, Canada

M. Yampolsky
Affiliation: Department of Mathematics, University of Toronto, Toronto, ON M5S 2E4, Canada

Received by editor(s): June 28, 2004
Published electronically: December 22, 2005
Additional Notes: The first author’s research is supported by an NSERC CGS scholarship
The second author’s research is supported by an NSERC operating grant
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.