Journal of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6834(e) ISSN 0894-0347(p)

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
Posted: 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

[BCSS] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York, 1998. MR 1479636 (99a:68070)
[ABC] A. Avila, X. Buff, A. Chéritat. Siegel disks with smooth boundaries. Acta Math. 193 (2004), no. 1, 1-30. MR 2155030
[BBY1] I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at Arxiv.org.
[BBY2] I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear.
[BB] E. Bishop, D.S. Bridges, Constructive Analysis. Springer-Verlag, Berlin, 1985. MR 0804042 (87d:03172)
[Brv1] 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] M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at Arxiv.org.
[Bru] A.D. Brjuno. Analytic form of differential equations, Trans. Mosc. Math. Soc. 25(1971), 119-262. MR 0377192 (51:13365)
[BC1] X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242.
[BC2] X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
[Do] A. Douady. Does a Julia set depend continuously on the polynomial? In Complex dynamical systems: The mathematics behind the Mandelbrot set and Julia sets. ed. R.L. Devaney, Proc. of Symposia in Applied Math., Vol. 49, Amer. Math. Soc., 1994, pp. 91-138. MR 1315535
[DH1] A. Douady, J.H. Hubbard. Etude dynamique des polynômes complexes, I-II. Pub. Math. d'Orsay, 1984. MR 0762431 (87f:58072a), MR 0812271 (87f:58072b)
[DH2] A. Douady, J.H. Hubbard. On the dynamics of polynomial-like mappings. Ann. Sci. École Norm. Sup., 18(1985), 287-343. MR 0816367 (87f:58083)
[Grz] A. Grzegorczyk, Computable functionals, Fund. Math. 42, pp. 168-202, 1955. MR 0086756 (19:238b)
[Ko1] K. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991. MR 1137517 (93i:03057)
[Ko2] K. Ko, Polynomial-time computability in analysis, in ``Handbook of Recursive Mathematics'', Volume 2 (1998), Recursive Algebra, Analysis and Combinatorics, Yu. L. Ershov et al. (Editors), pp. 1271-1317. MR 1673610 (2000e:03169)
[Lac] D. 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; Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris 241 (1955), 13-14, 151-153. MR 0072079 (17:225d), MR 0072080 (17:225e)
[Maz] S. Mazur, Computable analysis, Rosprawy Matematyczne, Warsaw, vol. 33 (1963). MR 0153553 (27:3517)
[MMY] S. Marmi, P. Moussa, J.-C. Yoccoz, The Brjuno functions and their regularity properties, Commun. Math. Phys. 186(1997), 265-293.MR 1462766 (98e:58137)
[Mat] Y. Matiyasevich, Hilbert's Tenth Problem, The MIT Press, Cambridge, London, 1993.MR 1244324 (94m:03002b)
[McM1] C. McMullen. Complex dynamics and renormalization. Annals of Math. Studies, v.135, Princeton Univ. Press, 1994. MR 1312365 (96b:58097)
[Mil] J. Milnor. Dynamics in one complex variable. Introductory lectures. Friedr. Vieweg & Sohn, Braunschweig, 1999. MR 1721240 (2002i:37057)
[PZ] C. Petersen, 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 (2005c:37085)
[Pom] C. Pommerenke, Boundary behaviour of conformal maps, Springer-Verlag, 1992.MR 1217706 (95b:30008)
[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).
[RW] R. Rettinger, K. Weihrauch, The Computational Complexity of Some Julia Sets, in STOC'03, June 9-11, 2003, San Diego, California, USA. MR 2121048 (2005j:68060)
[RZ] S. Rohde, M. Zinsmeister, Variation of the conformal radius, Journ. Anal. Math., 92(2004), pp. 105-115. MR 2072743 (2005g:30008)
[Sie] C. Siegel, Iteration of analytic functions. Ann. of Math. (2) 43, (1942), 607-612.MR 0007044 (4:76c)
[Sip] M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
[Tur] A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265.
[Wei] K. Weihrauch, Computable Analysis, Springer, Berlin, 2000.MR 1795407 (2002b:03129)
[Yoc] J.-C. Yoccoz, Théorème de Siegel, nombres de Bruno et polynômes quadratiques, Petits diviseurs en dimension , S.M.F., Astérisque, 231(1995), 3-88. MR 1367353 (96m:58214)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|